A Systematic Approach to MDD-Based Constraint Programming
A Systematic Approach to MDD-Based Constraint Programming
复制标题
基于 MDD 的约束编程的系统方法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
J. Hooker
中科院分区：
文献类型：
--
作者：
S. Hoda;W. V. Hoeve;J. Hooker
最近引入了固定宽度的MDD，作为域存储的更精细的替代方案，以表示CSP的部分解决方案。在这项工作中，我们提出了一个系统的方法，基于MDD的约束编程。首先，我们介绍了一个通用的计划，在MDDs的约束传播。我们表明，所有以前已知的传播算法MDDs可以表示使用该计划。此外，我们使用该计划来产生算法的一些其他的约束，包括之间，元素，和一元资源约束。最后，我们讨论了我们的MDD为基础的CP求解器的实现，并提供实验证据的MDD为基础的约束编程的好处。
Fixed-width MDDs were introduced recently as a more refined alternative for the domain store to represent partial solutions to CSPs. In this work, we present a systematic approach to MDD-based constraint programming. First, we introduce a generic scheme for constraint propagation in MDDs. We show that all previously known propagation algorithms for MDDs can be expressed using this scheme. Moreover, we use the scheme to produce algorithms for a number of other constraints, including Among, Element, and unary resource constraints. Finally, we discuss an implementation of our MDD-based CP solver, and provide experimental evidence of the benefits of MDD-based constraint programming.