赋值与限制
排程、标记和地图着色可以用带有可能取值的变量,以及限制哪些组合被允许的条件来描述。约束满足问题(CSP)要求找出满足所有限制的完整赋值;它不一定要给赋值附加目标函数。
定义 1.2.1
(有限二元约束网络)
网络有有限个变量,每个变量有有限的定义域,并带有二元约束。二元关系 指定允许的值对;反方向使用转置关系。解要从每个原始定义域中选一个值,并满足每个约束。为简化讨论,同一对变量上的多个约束先取关系的交集,再应用以下程序。
支持与弧一致性
定义 1.2.2
(支持、修订与弧一致性)
对约束的有向弧 ,若存在 使 ,就称 在 中有支持。修订 ,就是从 中删除所有没有这种支持的值。方向很重要:修订反方向的弧,删除的是 中的值。若每条有向约束弧上的每个剩余值都有支持,网络就是弧一致的。定义域为空表示失败;没有约束的变量不需要邻点的支持。
反复修订仍能删值的弧。定义域一旦缩小,相邻的弧可能失去支持,必须重新考虑。实现中可以用队列保存受影响的弧;数学上的停止条件是:相关改变发生后,所有有向弧都已检查。
命题 1.2.3
(修订不会删去任何解)
设网络 由网络 修订一条有向弧得到。则 与 有相同的解,这里的解指从每个当前定义域中选一个值并满足所有约束。因此,若反复修订使某个定义域变空,原网络就没有解。
证明
(解自己提供支持)
缩小定义域不会产生新的解,所以 的每个解都是 的解。反过来,设 的某个解使用 ,而正在修订 。同一个解给 指定某个 ,并满足 ,所以 支持 , 不会被删除,这个解在 中保留下来。对修订次数归纳,原解集在剩余取值中被保留;若某个定义域变空,就不存在解。这里假设修订期间约束本身没有改变。
证明透视
为什么删除无支持的值是安全的
论证只用到解的一个性质:解给 指定的值落在当前定义域内,而这个值就是支持。因此支持是针对当前定义域 检验的;由归纳,它仍然包含每个解所用的值,所以即使每次修订都依赖之前的删除,整串修订依然可靠。修订只检验一个必要条件:一个值要出现在解中,沿一条弧必须有支持。反过来不成立,下面的三角形就是例子:每条弧上的每个值都有支持,却没有解。论证还依赖于约束是二元的且没有改变;沿各对弧得到的支持,并不能合起来成为对涉及三个变量的约束的支持。
定理 1.2.4
(传播终止于最大的弧一致网络)
反复修订有向弧,直到没有修订能删去值为止,过程至多删除 次就会终止。所得定义域是弧一致的,并且与修订次序无关:它是原定义域的所有弧一致子定义域选择中最大的一个。
证明
(每次删除都使一个有限的量下降)
每次真正的删除都使定义域大小之和至少减一,所以至多删除 次。没有弧能再删值时,每个剩余值在每条有向弧上都有支持,这就是弧一致。至于与次序无关:若子定义域选择 满足 的每个值对每条弧 都在 中有支持,就称它弧一致。两个弧一致选择的并集仍然弧一致,因为在其中一个选择里有支持的值,在并集里同样有支持,所以存在最大的一个 。任何修订都不会删去 中的值:当前定义域满足 时,每个 在 中有支持。最终结果包含 ,且本身弧一致,所以不论次序如何都等于 。
例题
例题 1.2.5
(三个两两不等的变量)
设 、、,要求 、、。修订 会从 中删去 ,因为 只能是 。接着修订 ,从 中删去 ;再修订 ,删去 ,因为 只能是 。定义域变为 ;唯一剩下的赋值满足三个不等式。
例题 1.2.6
(不必分支就发现无解)
设 、、,约束为 与 。修订 删去 ,因为 唯一的取值是 。此时 ,再修订 删去 ,因为 唯一的取值也是 。 变空,所以网络无解。直接推理的结论相同: 迫使 ,而 使 没有可用的取值。无解仅靠传播就发现了。
例题 1.2.7
(先传播,再分支)
设 、,三个变量要求两两不同。每条弧上的每个值都已经有支持:例如 由 和 支持, 由 和 支持。所以传播什么也删不掉,尽管只有 可能出现在解中。对 分支:修订 删去 ,修订 删去 。在 之下,修订 删去 。所有定义域都成为单元素集合:,对原始约束 、、 逐一检查,确认它是解。
反例模式
局部支持不保证有解
取三角形变量 ,各有定义域 ,每条边要求两端取值不同。每条弧上的每个值都得到另一个值的支持,因此网络已经弧一致。但它没有解:若 ,两个邻点都必须是 ,违反 ; 的情形对称。一条弧上选出的支持,未必与另一条弧上的支持相容。
传播之后的搜索
若剩余定义域均非空,选一个仍有多个取值的变量,对其剩余取值逐个分支。每个分支把该变量限制为所选的单元素集合,再进行传播;若某个定义域变空,就舍弃该分支。若所有变量都成为单元素,报告解之前仍要检查所有原始约束。
定理 1.2.8
(传播加分支既可靠又完备)
对有限网络,先传播、再对有多个剩余取值的变量分支并递归的程序必然终止。它报告解,当且仅当解存在,并且每个被报告的赋值都满足所有原始约束。
证明
(每个分支都减少一个值,并保留所有解)
每个分支把至少含两个值的定义域换成单元素集合,传播又只会删值,所以沿每个分支定义域大小之和都严格下降,递归因此终止。被报告的赋值已经对照所有原始约束检查过,所以是解。反过来,设解存在。它经得起安全传播,并给分支变量指定某个剩余取值,因此在该取值对应的分支中保留下来。对定义域大小之和归纳,它会在某个分支中被找到。所以所有剩余分支都失败,就证明无解。
这种有限回溯程序的时间可能随变量个数呈指数增长。弧一致性可以缩小搜索范围,但消除不了这种最坏情形。这里的证明并没有声称某种变量选择或队列次序总是最快。
常见错误
常见错误
(修订了错误的方向)
修订 删除的是 中的值,而不是 中的值。设 、 且 ,修订 什么也删不掉,因为 由 支持;修订 才会删去 。两个方向的弧都要考虑,一个方向不能代替另一个。
常见错误
(只把所有弧扫一遍是不够的)
取 、、,约束为 与 。按 、、、 的次序各修订一次。只有 能删去值:因为 唯一的取值是 ,它删去 ,得到 。此时网络仍然不是弧一致的,因为 在 中已经没有支持。较早的弧 必须再修订一次,删去 。最后的定义域 弧一致,并给出解 。定义域一旦缩小,相邻的弧就要重新放回队列。
练习
快速检查
(在第一个例题中,为什么 在弧 上没有支持?)
看 的定义域。
解答 · 答案
只能取 ,而 违反 。
快速检查
(在二色三角形中,分别为 在弧 和 上给出支持;为什么仍得不到完整的解?)
检查两个支持所用的值彼此是否相容。
解答 · 答案
两条弧都可以用值 支持 ,但同时取 违反 。
快速检查
(若安全修订使某个定义域变空,可以得出什么结论?)
解必须从每个定义域中取一个值。
解答 · 答案
没有解:解必须从每个定义域中取值,而安全修订没有删去任何解所用的值。
快速检查
(三个两两不等的变量各有定义域 ,给出一个解。)
依次给三个变量取三个不同的值。
解答 · 答案
取 ;每条边的两端都不相同。