通过约束传播信息

5.2.2 通过约束传播信息

迄今为止，我们的搜索算法只有在函数SELECT-UNASSIGNED-VARIABLE选择了一个变量的时候才考虑该变量的约束。但是如果在搜索中早一些或者在搜索开始之前就考虑某些约束，我们能够急剧减小搜索空间。

一、前向检验

在搜索中更好地利用约束条件的一条途径是前向检验。只要变量X被赋值了，前向检验过程考察每个通过约束与X相连的未赋值变量Y，并从Y的值域中删去与X取值矛盾的那些值。图5.6显示了在地图染色搜索中使用前向检验方法的进程。这个例子中需要注意重要的两点。第一，注意在赋值WA = red和Q = green之后，NT和SA的值域都减小到了单个值；我们通过WA和Q传播的信息删除了这些变量上的一些分支。M RV启发式显然可以和前向检验配合，它将自动地选择SA或NT作为下一个赋值的变量。（实际上，我们可以把前向检验视为一个逐步增加地计算MRV启发式完成任务所需信息的高效方法。）第二点需要注意的是，当赋值V = blue之后，SA的值域就变成空的。因此，前向检验已经检测到不完全赋值{WA = red，Q = green，V = blue}与问题约束是矛盾的，因此算法会立刻回溯。

图5.6 用前向检验方法解决地图染色搜索的进程。首先赋值WA=red；然后前向检验在它的邻居变量NT和SA的值域中删除red。赋值Q=green之后，green从NT，SA和NSW的值域中删除。赋值V=blue之后，blue从NSW和SA的值域中删除，这时SA就没有合法的取值了

二、约束传播

虽然前向检验能检验出许多矛盾，它还是不能检验出所有的矛盾。例如，考虑图5.6中的第三行。它显示出当WA是red、Q是green的时候，NT和SA都被迫是blue。但是因为这两个区域相邻，因此不能染同样的颜色。前向检验并不能检测出这样的矛盾，因为它看得不够远。约束传播是将一个变量的约束内容传播到其它变量上的一般术语；既然这样，我们需要将约束从WA和Q传播到NT和SA， （就像前向检验做的那样）再传播到NT和SA之间的约束上以检测矛盾。同时我们还想快速地完成这件事情：如果我们在传播约束上花费更多的时间，减少搜索量也就没有益处了。

弧相容的思想提供了一个实际比前向检验更强的约束传播的快速方法。这里，“弧”是指约束图中的有向弧，诸如SA和NSW之间的弧。给定SA和NSW的当前值域，如果对于SA的每个取值x，NSW都有某个取值y能和x保持相容，那么这条弧就是相容的。在图中的第三行，SA和NSW的当前值域分别是{blue}和{red，blue}。令SA = blue，就有一个对NSW的相容赋值，即NSW = red；因此，从SA到NSW的弧是相容的。另一方面，从NSW到SA的反向弧则不是相容的：当赋值NSW = blue之后，对SA没有相容的赋值。可以通过删除NSW值域内的blue值使弧变成相容的。

我们也可以在搜索过程的同一阶段中对从SA到NT的弧应用弧相容。图5.6中的第三行表明这两个变量的值域都是{blue}。结果就是必须从SA的值域中删去blue，它的值域变成了空的。因此，应用弧相容能够更早地检测到前向检验不能发现的矛盾。

弧相容检验不仅可以用作开始搜索过程之前的预处理，也可以在搜索过程中每次赋值后用作一个传播约束步骤（像前向检验一样）。（后一个算法有时也称为MAC，即保持弧相容。）在每种情况下，这个过程必须反复应用直到不再有矛盾。这是因为，任何时候从某个变量的值域中删除一个值以消除弧不相容，指向这个变量的弧都可能会产生新的弧不相容。弧相容的完整算法，AC-3，用一个队列来记录需要检验不相容性的弧。（参见图5.7。）每条弧 (Xi, Xj) 依次从队列中删除并被检验；如果任何一个Xi值域中的值需要被删除，那么每个指向Xi的弧 (Xk, Xi) 都必须重新插入队列中准备检验。弧相容检验的复杂度可以分析如下：二元CSP至多有O(n2)条弧；每条弧只能插入队列d次，因为Xi至多有d 个值可删除；检验一条弧的相容性可以在 O(d2)时间内完成；因此在最坏情况下算法的总时间为O(n2d3)。虽然这个开销实在要比前向检验大不少，但额外的开销往往是值得的。[22]

图5.7 弧相容算法AC-3。应用了AC-3后，要么每条弧都是弧相容的，要么有变量的值域为空，后者说明该CSP问题不能满足弧相容（因此该CSP无法解决）。该算法的发明者（Mackworth，1977）使用“AC-3”这个名字，是因为这是他论文中的第三个版本

因为3SAT问题是包括在CSP问题中的一种特殊情况，我们不指望能找到一个多项式时间复杂度的算法，判断给定的CSP问题是否是相容的。因此，我们推论弧相容并不能揭示每个可能的矛盾。例如，在图5.1中，赋值{WA=red，NSW=red}是矛盾的，但是AC-3不会找到这个矛盾。用k相容的概念可以定义更强的传播形式。如果对于任何k − 1个变量的相容赋值，第k个变量总能被赋予一个和前k−1个变量相容的值，那么这个CSP问题就是k相容的。例如，1相容是指每个单独的变量自己是不矛盾的；也称为节点相容。2相容和弧相容是一样的。3相容是指任何一对相邻的变量总可以扩展到第三个邻居变量；它也称为路径相容。

如果一个图是k相容的，也是k−1相容的、k−2相容的、…，直到1相容，那么这个图是强k相容的。现在假设我们的CSP问题有n个节点而且令它是强n相容的（即k = n时的强k相容）。那么我们不需要回溯就能求解这个问题。首先，我们对变量 X1选择一个相容值。我们保证能够给 X2也选择一个相容值，因为它是2相容的，对X3也如此，因为它是3相容的，等等。对每个变量Xi，我们只需要在值域内的 d个值中找到与X1，…，Xi－1相容的值。我们能保证在 O(nd)时间内找到解。当然，世上没有免费的午餐，任何建立n相容的算法在最坏情况下必须花费n的指数级时间。

在n相容和弧相容之间有广阔的中间地带：执行较强的相容性检验会花费更多的时间，但是会更有效地降低分支因子和检测出矛盾的不完全赋值。计算出能使k相容保证问题不用回溯就可求解的最小k值是可能的（参见第5.4节），但往往是不实用的。实际上，决定合适的相容性检验层次的主要是经验科学。

三、处理特殊约束

在实际问题中经常出现特定类型的约束，用专用算法处理比前面描述的通用方法效率要高得多。例如，Alldiff约束要求涉及的全部变量都必须取不同的值（如密码算术问题）。Alldiff 约束问题的矛盾检测的一个简单形式包括如下工作：如果约束涉及m个变量，它们共有n个可能的不同取值，并且m＞n，那么这个约束不能被满足。

这引出了下面的简单算法：首先，删除约束中只有单值值域的变量，然后将这些变量的取值从其余变量的值域中删去。只要还有单值变量，就重复这个过程。如果得到一个空的值域或者剩下的变量数比剩下的取值数大，那么就产生矛盾。

我们可以用这个方法来检测图5.1中的不完全赋值{WA = red，NSW = red}的矛盾。注意变量SA， NT和Q是通过Alldiff约束有效连接起来的，因为它们之间任何两个都要染不同的颜色。在这个不完全赋值上应用 AC-3 算法，每个变量的值域就缩小为{green，blue}。就是说我们有三个变量但只有两种颜色可选，所以违反了Alldiff约束。因此一个高阶约束的简单相容过程有时候比把弧相容用于二元约束的等价集合效率更高。

也许最重要的高阶约束是资源约束，有时称为atmost约束。例如，用PA1，…，PA4表示分配给四项任务的人员个数。总共分配不超过10人的约束记为a t m o s t(10,PA1,PA2,PA3,PA4)。通过检验当前值域中的最小值之和就能检测出矛盾；例如，如果每个变量的值域为{3，4，5，6}，就不能满足atmost约束。我们也可以通过删除变量值域中与其它变量的值域中的最小值不相容的最大值来保持相容性。因此，在我们的例子中如果每个变量的值域是{2，3，4，5，6}，那么5和6可以从每个变量的值域中删去。

对于大型的整数值的资源限制问题——诸如涉及用上百辆交通工具来运送上千人这样的后勤问题——用整数集合来表示每个变量的值域然后通过相容性检验方法逐步削减集合，通常是不可能的。取代地，值域用上界和下界来表示，并通过边界传播来管理。例如，假设有两次航班，271和272，它们分别有165和385个座位。每次航班可承载的乘客数的初始值域为

Flight 271∈[0，165] 和 Flight272∈[0，385]。

现在假设我们又有一个附加约束，这两次航班所载的总乘客数必须是420：Flight271 ＋ Flight272 ∈[420，420]。通过传播边界约束，我们可以把两个值域削减到

Flight 271∈[35，165] 和 Flight272∈[255，385]。

如果对于每个变量X和它的取值的上下界，每个变量Y都存在某个取值满足X和Y之间的约束，我们称该CSP问题是边界相容的。这种边界传播广泛地应用于实际的约束问题中。

四、智能回溯：向后看

图5.3中的BACKTRACKING-SEARCH算法当一个分支上的搜索失败时采取一个简单的方针：倒退回前一个变量并且尝试另一个值。这称为历时回溯，因为重新访问的是时间最近的决策点。在这部分，我们将看到一些更好的方式。

考虑我们在图 5.1 的问题中按照固定的变量顺序 Q，NSW，V，T，SA，WA，NT，应用简单回溯算法，假设我们已经进行了不完全赋值{Q = red，NSW = green，V = blue，T = red}。当我们尝试下一个变量SA时，我们发现任何值都不满足约束。我们倒退回T，试着给Tasmania赋一种新的颜色！显然这种做法很愚蠢——对T重染色不能解决South Australia的问题。

一个更智能的回溯方法是倒退回导致失败的变量集合中的一个变量。这个集合称为冲突集；这里，SA的冲突集是{Q，NSW，V}。一般来说，变量X的冲突集是通过约束与X相连接的先前已赋值变量的集合。后向跳转方法回溯到冲突集中时间最近的变量；在这种情况下，后向跳转将跳过 T而尝试V的新值。它可以通过简单地修改BACKTRACKING-SEARCH而实现，令算法在检验可赋值的合法值的时候保存一个冲突集。如果没有找到合法值，那么它利用失败标记返回冲突集中时间最近的变量。

目光敏锐的读者会注意到前向检验算法可以不需要额外的工作就能提供冲突集：当基于X的赋值的前向检验从变量Y的值域中删除一个值时，应该把X加入Y的冲突集里。同时，每当从Y的值域中删除最后一个值的时候，把Y的冲突集中的变量都加到X的冲突集中。这样，当我们到达Y的时候就知道如果回溯应该回到哪个变量。

有眼力的读者还会注意到某些古怪之处：后向跳转只出现在值域中的每个值都和当前的赋值有冲突的情况下；但是前向检验能检测到这个事件并且一旦到达这样的节点就阻止搜索！实际上，可以证明每个被后向跳转剪枝的分支在前向检验算法中也被剪枝。因此，简单的后向跳转在前向检验搜索中，或者说在诸如MAC这样使用更强的相容性检验的搜索中是多余的。

除了上一段中的观察结果，后向跳转背后的思想仍然是好的：基于失败的原因回溯。后向跳转当一个变量的值域为空的时候会注意到失败，但是在很多情况下，一个分支在这发生很久以前就已经注定要失败了。再次考虑不完全赋值{WA = red，NSW = red}（从我们前面的讨论中知道，它是矛盾的）。假设我们下一个尝试T = red，然后给NT，Q，V，SA赋值。我们知道对这最后四个变量没有可行的赋值，因此最终我们用完了 NT 的所有可能取值。现在的问题是向哪里回溯？后向跳转是行不通的，因为NT确实有和前面赋值的变量相容的值——NT没有完整的由前面能导致失败的变量组成的冲突集。然而我们知道，四个变量 NT，Q，V 和 SA放在一起会因为前面的变量集而失败，那些变量一定与这四个变量有直接冲突。这引出了关于诸如NT这样一个变量的冲突集的更深概念：是那个前面的变量集合致使 NT 连同任何后继变量一起没有相容解。在这种情况下，变量集是 WA和 NSW，所以算法会越过Tasmania回溯到 NSW。使用按这种方式定义的冲突集的后向跳转算法称为冲突指导的后向跳转。

我们现在必须解释这些新的冲突集是怎样计算的。实际上方法很简单。一个搜索分支的“终端”失败总是因为一个变量的值域变为空；该变量有一个标准的冲突集。在我们的例子中，SA失败了，它的冲突集是{WA，NT，NSW}。我们后向跳转到Q，Q将SA的冲突集（当然减去Q本身）也就是{NT， NSW}吸收到自己的冲突集里；新的冲突集是{WA，NT，NSW}。就是说，在给定了前面对{WA，NT， NSW}的赋值之后，从Q向前是无解的。因此我们回溯到NT，集合中最近的一个。NT把{WA，NT， NSW} − {NT}吸收到自己的直接冲突集{WA}里，得到{WA，NSW}（如上一段所说的）。现在算法如我们所希望的那样后向跳转到NSW。总结一下：令Xj是当前变量，再令conf (Xj)为其的冲突集。如果Xj的每个可能取值都失败了，后向跳转到conf(Xj)中最近的一个变量Xi，并置

conf (Xi)←conf (Xi) ∪ conf (Xj) − {Xi}

冲突指导的后向跳转使我们回到搜索树中正确的位置，但是不能防止我们在另一个分支上犯同样的错误。约束学习可以通过添加从这些冲突中归纳的一条新约束，实际修改CSP问题。