3.8 Specific Constraints具体的约束

在前几节中，我以一种通用的方式介绍了约束传播和局部一致性，但没有说明当我们对约束的语义有一些特定信息时应该做什么。在本节中，我将开发一些可用的技术来考虑约束语义。

3.8.1 Specific Propagators in Solvers 求解器中的特定传播器

所有的约束求解器都将特定的传播算法附加到它们所包含的特定类型的约束上。此外，它们中的大多数允许用户为合并的新约束设计自己的传播器。算术约束是大多数约束求解器的核心，这一事实影响了这些求解器的实现方式。不仅提供了所有基本的算术约束，而且它们为构建新的传播器提供了面向算术的编程可能性。我简要概述了大多数求解程序的共同点。设计约束传播器的艺术还不是一门成熟的科学，不同的求解器可能会有不同的结果，并且很可能在未来几年发展。这个主题已经在一些学术出版物[79、94、117、118、78、110]和约束求解手册中讨论过。请参阅第二部分的第14章。

在大多数算术约束中，域的减少似乎不会对约束的其他变量产生相同的效果，这取决于它是否删除了域中间的一个值，是否增加了它的最小值，是否减少了它的最大值，或者是否实例化了一个值。然后，有必要区分这些不同类型的事件，以便能够准确地传播。约束求解器通常识别的事件有:

约束解决程序中使用这些事件的方式通常与该解决程序处理的传播体系结构类型绑定。我在这里给出的描述只是如何使用这些事件的一个说明性示例。如果我们遵循类似于AC3的传播模式，那么事件类型的使用将导致算法3.1的修改版本，该版本将考虑对域执行的约简的类型Mtype(请参见算法3.10)。修改后的函数修改具有参数(xi,c，(xj,Mtype)，Changes)，其中(xi,c)是由于D(xj)中的Mtype改变而需要修改的圆弧。除了一个布尔值表示域是否已经更改外，function modify还返回它在D(xi)(第4行)上执行的更改类型的集合更改。域D(xi)上类型Mtype的每一次修改都需要在挂起事件的列表Q中添加4元组(xj,c'，xi,Mtype)(第6-7行)。Q中(xj,c,xi,Mtype)的存在意味着，由于D(xi)中Mtype的改变，xj应该在c上进行修改。我假设每个约束都与一个函数init-propag相关联，该函数执行约束上的第一次传播，并将与在某些域中执行的事件相关的所有4元组追加到列表Q中(第1行)。

这种区分类型的事件的好处是双重的。首先，它允许根据事件的类型以不同的方式处理约束传播(第4行)。

举例说明从{1..100}中删掉100和50的区别。如果从D(x2)中删除的值是50，那么常规的Reverse将执行大约5000个约束检查，而一个特定的Reverse知道删除50是一个RemValue事件，对于这个事件不应该做任何事情，因为唯一可以更改D(x1)的事件是DecMax和Instantiate。

事件信息的第二个优点是，在某些情况下，我们知道传播约束是没有用的，因为给定的事件不能改变约束的其他变量。例如,约束x1≤x2的上面的示例中,RemValue没有影响。我们可以为每种类型的事件构建这样一个集合，而不是为所有涉及xi的约束设置一个集合。只包含涉及xi的约束，而xi上的Mtype事件需要传播这些约束。算法3.10中的第6行为:

在极端情况下，域被减小，使得约束c成为必要。也就是说，对于X(c)上的任何有效的值组合，c都是满足的。(见[118,110]或3.3.1节)只要域不放松，c就可以从网络的约束集合中移除。

还有第三种方法可以在域中传播更改时节省工作。它存储的不仅有域D (xi)在调用Reverse过程中类型的改变,还有被移除的Δi集的值。函数Reverse的从D (xj)被移出的额外参数Δj导致修订。除了Changes，Revise 返回集合Δi从D(xi)中移出的值。Δi和其他信息一起放在Q中。算法3.10中的第3-7变为：

Van Hentenryck等人已经在AC5传播模式中提出了这种功能[117]。这明显地降低了在函数或反函数约束上的arc一致性的复杂度。

这四种类型的事件允许为基本约束构建有效的传播器。但是，只要约束不是算术的，或者没有函数、反函数或其他属性，就很难用这种体系结构实现传播器。

3.8.2 Classes of Specific Constraints: Global Constraints特定约束的类:全局约束

当试图将实际问题表示为约束网络时，“约束模式”是普遍存在的。例如，我们经常需要说一组变量必须取不同的值。模式的大小是不固定的，也就是说，集合中可以有任意数量的变量。在CHIP[50]中引入的alldifferent约束不是单个约束，而是一类完整的约束。任何指定其变量必须取不同值的约束都是alldifferent约束。传统的智慧是将这些由布尔函数定义的约束类命名为“全局约束”，该函数的域包含任意长度的值元组。给定全局约束的实例c是一个具有固定变量格式的约束，其中包含定义全局约束的函数所接受的所有长度为|X(c)|的元组。在过去的几年里，关于这个问题的文献变得相当冗长。Beldiceanu等人提出了一个广泛的全局约束清单[9]。

将全局约束合并到约束求解器中，以便用户能够方便地使用它们来表示相应的约束模式，这是非常有趣的。因为这些全局约束可以与任何大小的方案一起使用，所以有一种方法传播它们而不使用通用的弧一致性算法是很重要的。(请记住，对于涉及r变量的约束，最佳通用弧一致性算法在O(erdr)中—请参见3.3.1节。)

针对GAC的通用算法在全局约束上的组合爆炸，第一个替代方案是用“更简单”的约束来分解它。

注意，根据定义，分解中的附加变量的域必须是多项式大小的。

一些全局约束G会分解δk来保存GAC。但是有一些约束条件，例如alldifferent，我们不知道有任何这样的分解。对于这些约束，有时可以构建一个专门的算法，在多项式时间内对全局约束的所有实例强制GAC。例如,Knuth Raghunathan,R´egin,找到了FAC alldifferent约束和最大匹配问题的两偶图(77、106)之间的关系,这是多项式的。

在[20]中，Bessiereetal放宽了分解的定义。只要GAC是多项式的，它们就允许使用无界约束进行分解。一个全局约束G的分解是GAC-polytime，如果对于G的任意实例c和X(c)上的任意域，在分解上强制GAC是多项式。这扩大了可分解的全局约束集。然而，有一些全局约束，我们不知道有任何GAC-polytime分解可以保留GAC。计算复杂度的工具帮助我们决定何时给定的全局约束没有机会允许GAC-polytime分解保留GAC。事实上，如果在全局约束G上强制GAC是NP困难的，则不存在任何GAC-polytime分解来保持GAC(假设P不等于NP)。例如，对NValue强制GAC是np困难的。这告诉我们，没有办法找到GAC-polytime分解，GAC总是在这个分解上删除原始NValue约束的所有GAC不一致值。

分解仅限于多项式时间的变换，也仅限于多项式空间的变换。如果我们去掉这些限制，任何全局约束都允许通过隐藏变量编码转换成二进制网络，其中唯一的附加变量具有指数大小的域[45,108]。这个变换上的GAC等价于原约束上的GAC，即使在它上面强制GAC是np困难的。

有时可以将全局约束表示为更简单的约束的组合，而不是连接。析取不是由约束求解器自然处理的。Van Hentenryck等人提出了构造析取作为一种部分传播约束析取的方法[70]。给定约束 c = c1 ∨ c2 ∨ ...∨ ck，构造析取独立于其他约束逐个传播约束ci，最终修剪与所有ci一致的值。Lhomme对这种技术进行了改进[84]。Bacchus和Walsh提出了一个约束代数，我们可以将元约束定义为由更简单的约束[4]组成的逻辑表达式。它们提供了传播它们的方法和保证GAC的条件。

当在全局约束上强制GAC太昂贵时，另一种可能是强制较弱的一致性级别，如BC(Z)或RC。BC(Z)和RC在由算术表达式(尤其是线性约束)组成的约束上明显比GAC便宜。BC(Z)和RC也用于GAC太昂贵的其他约束类。在[80],Leconte表明,RC可以执行alldifferent约束成本渐近低于R´egin GAC算法([106])。Puget提出了一种BC(Z)算法，适用于所有不同的情况，复杂度更低[103]。在Regin[107]定义的全局基数约束(gcc)中，Quimper等人表明，如果基数是变量而不是固定的间隔，GAC是NP-hard的[104]。Katriel和Thiel为gcc提出了一个BC(Z)算法，即使基数是变量，该算法也在多项式时间内运行[75]。在这种情况下，BC(Z)是多项式传播约束的一种方法。

3.8.3 Creating Propagators Automatically

Apt和Montfroy提出生成一组约简规则[3]，作为传播特定约束的专用算法的替代。对于任何约束，都存在一组模拟弧一致性的规则。但是，它的大小可以是指数形式的变量的约束。

为了避免这种组合爆炸，Dao等人提出将他们的注意力限制在变量xij以区间Iij取值而不是以域Sij[39]的任意子集取值的规则上。这减少了可能性的空间，并允许将生成规则的任务表示为由单纯形求解的线性程序。

在为约束cadhoc构建传播器时，另一种避免组合爆炸的方法是考虑约束的内部结构，在相同的规则下分解许多满足条件的元组。巴特´ak提出分解特设二进制约束cadhoc (xi, x j)成矩形[5]。

3.8.4 Priorities in the Propagation List传播列表中的优先级

在约束求解器中提高传播效率的一种简单方法是对不同约束的不同传播事件进行优先级排序。我们在3.3.3节看到，圆弧一致性算法的传播列表可以启发式排序。对于二进制约束的通用AC算法来说，主要的标准是将期望修剪更多的约束放在首位。约束求解器包含不同类型的约束和不同类型的传播事件，这些约束可能具有不同的复杂性。Laburthe等[78]和Schulte和Stuckey[110]提出了维护具有多个优先级的传播列表。其思想是根据传播事件的时间复杂度将其置于列表的不同级别。当第i层不是空的时候，第i-1层中的事件不会弹出。简单算术约束上的实例化事件是放在第一级的事件。在昂贵的全局约束上传播GAC被放在最后一层。在相同的约束条件下传播BC(Z)将放在某个中间级别。CHOCO求解器使用具有7个优先级的传播列表[78]。