第6章 约束满足问题

1、第第6章章 约束满足问题约束满足问题中国科大中国科大 计算机学院计算机学院第第部分部分 问题求解问题求解本章内容本章内容 6.1 约束满足问题约束满足问题 6.2 约束传播：约束传播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 问题的结构问题的结构例例1、澳大利亚地图染色问题、澳大利亚地图染色问题(1) 澳大利亚地图染色问题：用澳大利亚地图染色问题：用红红绿绿蓝蓝3色标出各省，色标出各省，相邻者颜色不同。相邻者颜色不同。塔斯马尼亚西澳大利亚北领地南澳大利亚昆士兰新南威尔士维多利亚 对应于澳大利亚地图的对应于澳大利亚地图的约束图约束图，

2、相互关联的节点，相互关联的节点用边连接。用边连接。wantsanswqvt 西澳大利亚西澳大利亚 wa wa 北领地北领地 nt nt 南澳大利亚南澳大利亚 sa sa 昆士兰昆士兰 q q 新南威尔士新南威尔士 nsw nsw 维多利亚维多利亚 v v 塔斯马尼亚塔斯马尼亚 t t例例1、澳大利亚地图染色问题、澳大利亚地图染色问题(2) 一组满足约束的完全赋值：一组满足约束的完全赋值： wa=r, nt=g, q=r, sa=b, nsw=g, v=r, t=r 约束满足问题的定义约束满足问题的定义 约束满足问题约束满足问题（constraint satisfying problem, cs

3、p）：）： 由一个变量集合由一个变量集合x1xn和一个约束集合和一个约束集合c1cm定义；定义；每个变量都有一个非空可能值域每个变量都有一个非空可能值域d di i；每个约束指定了包含若干变量的一个子集内各变量的赋值每个约束指定了包含若干变量的一个子集内各变量的赋值范围。范围。 例如：例如：地图染色问题，地图染色问题，n-n-皇后问题。皇后问题。 csp的一个状态的一个状态：对一些或全部变量的赋值：对一些或全部变量的赋值 xi=vi, xj=vj, 。csp问题的解问题的解 一个不违反任何约束的对变量的赋值称为一个不违反任何约束的对变量的赋值称为相容赋值相容赋值或合法赋值或合法赋值。 对每个变

4、量都进行赋值称为对每个变量都进行赋值称为完全赋值完全赋值。 一个一个（一组）（一组）对变量的赋值，若既是相容赋值又是对变量的赋值，若既是相容赋值又是完全赋值，则这个（组）赋值是完全赋值，则这个（组）赋值是csp问题的解问题的解。 某些某些csp问题要求问题的解能使目标函数最大问题要求问题的解能使目标函数最大化化约束优化约束优化。 csp问题常常可以可视化，表示为问题常常可以可视化，表示为约束图约束图，更直观，更直观地显示问题，帮助思考问题的答案。地显示问题，帮助思考问题的答案。csp问题的分类问题的分类 根据变量的类型划分：根据变量的类型划分：离散值域离散值域和和连续值域连续值域。 变量变量离

5、散值域离散值域 有限值域有限值域，如地图染色问题，八皇后问题。，如地图染色问题，八皇后问题。无限值域无限值域，如整数集合或者字符串集合。，如整数集合或者字符串集合。 例如，对于作业规划问题，无法枚举所有可能取值，要例如，对于作业规划问题，无法枚举所有可能取值，要使用使用约束语言约束语言( (线性约束线性约束/ /非线性约束非线性约束) )描述，如描述，如startjobstartjob1 1+5stratjob+5stratjob3 3。 有限值域有限值域csp问题包括问题包括布尔布尔csp问题，它的变量的取值可以是问题，它的变量的取值可以是true或或false。 布尔布尔csp包括一些包括

6、一些典型典型np完全问题完全问题，如，如3-sat问题（命题问题（命题逻辑语句的可满足性问题），逻辑语句的可满足性问题），最坏情况下最坏情况下不能指望低于指不能指望低于指数级时间复杂性解决该问题。数级时间复杂性解决该问题。csp问题的分类问题的分类 变量变量连续值域连续值域 最著名的连续值域最著名的连续值域cspcsp是是线性规划线性规划问题。问题。线性规划线性规划中的约束必须是构成一个凸多边形的中的约束必须是构成一个凸多边形的一组线性不等式。一组线性不等式。线性规划问题可以在变量个数的多项式时间内线性规划问题可以在变量个数的多项式时间内求解。求解。csp问题的分类问题的分类 根据约束的类型划

7、分：根据约束的类型划分： 线性线性或或非线性约束非线性约束。 一元一元或或多元约束多元约束。 一元约束：只限制一个变量的取值一元约束：只限制一个变量的取值 二元约束与二元约束与2 2个变量相关个变量相关 高阶约束：涉及高阶约束：涉及3 3个或更多变量。个或更多变量。通过引入辅助变量，转为二元约束。通过引入辅助变量，转为二元约束。 绝对绝对约束约束 vs 偏好约束偏好约束。 我们仅讨论绝对约束。我们仅讨论绝对约束。高阶约束的例子高阶约束的例子 算式算式t w o+t w o f o u r例例2、密码算术问题。、密码算术问题。每个字母表示不同的数字。目标是找到每个字母表示不同的数字。目标是找到能

8、使如下加法式子成立的数字，附加的约束条件是最前面的数能使如下加法式子成立的数字，附加的约束条件是最前面的数字不能为字不能为0。高阶约束的例子高阶约束的例子 算式算式t w o+t w o f o u r f=1。 如不考虑如不考虑o/u有进位：有进位： r/u/o均为偶数，均为偶数，r=4, 6, 8，o=2?, 3?, 4!。 r=8/o=4，则，则t=7（由（由o/r/u/w共同限制）。共同限制）。 t=7，则，则u=6/w=3，由此得到一组解，由此得到一组解1468 | 734。 考虑考虑o/u有进位：有进位： r=0, 2, 4, 6, 8，o=5, 6, 7, 8, 9。 若若r=0

9、/o=5(有进位有进位)，则，则t=7/w=6/u=3，由此得，由此得到一组解到一组解=1530 | 765。 四列算式约束：四列算式约束： o+o=r+10*x1 x1+w+w=u+10*x2 x2+t+t=o+10*x3 x3=f 对应的对应的约束超图约束超图如右图。如右图。 六个变量互不相等约六个变量互不相等约束可化为两两不等约束可化为两两不等约束额的二元约束。束额的二元约束。高阶约束的例子高阶约束的例子各算式约束ftwuorx3x1x2约束：互不相等，两两不等每个约束在图中用方块表示，每个约束在图中用方块表示，连接至它所约束的变量。连接至它所约束的变量。csp问题求解的复杂度问题求解的

10、复杂度 csp问题的求解目标是找到问题的求解目标是找到相容的完全赋值相容的完全赋值，最，最朴素的想法是依次取变量的赋值组合并检查其是朴素的想法是依次取变量的赋值组合并检查其是否满足约束条件。否满足约束条件。 若若csp问题的任何一个变量的最大值域为问题的任何一个变量的最大值域为d，那，那么可能的完全赋值数量为么可能的完全赋值数量为o(dn)。 指数级指数级计算量。计算量。本章内容本章内容 6.1 约束满足问题约束满足问题 6.2 约束传播：约束传播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 问题的结构问题的结构约束传播约束传播 约束

11、传播：约束传播：使用约束来使用约束来减小一个变量的合法取值范减小一个变量的合法取值范围围，从而影响到，从而影响到与此变量有约束关系的另一变量与此变量有约束关系的另一变量的的取值。取值。 弧相容：弧相容：依次检验约束图中各个相关节点对依次检验约束图中各个相关节点对。注意，。注意，弧是有向弧。弧是有向弧。 例如，给定例如，给定sa/nsw当前值域，如果对于当前值域，如果对于sa的每个取值的每个取值x，nsw都有某个都有某个y和和x相容，则相容，则sa到到nsw的弧是相容的；的弧是相容的；反过来是反过来是nsw到到sa的弧相容。的弧相容。wantsanswqvt弧相容弧相容 在地图染色约束的赋值过程

12、中：第在地图染色约束的赋值过程中：第4行行sa=blue，nsw=red, blue，则，则sa的取值有一个的取值有一个nsw=red与之相容；反过来与之相容；反过来nsw=blue，则，则sa为空值，即不相容，为空值，即不相容，通过删除通过删除nsw值域中值域中的的blue可使其相容。可使其相容。 弧相容检测也能较早发现矛盾，如第弧相容检测也能较早发现矛盾，如第4行行sa和和nt值域均为值域均为blue，则必须删去，则必须删去sa=blue，其值域变为空。，其值域变为空。 用弧相容能够更早地检测到矛盾。用弧相容能够更早地检测到矛盾。wantqnswvsargbrgbrgbrgbrgbrgb

13、gbrgbrgb rgb gb b r brgb bwa=redwa=redq=greenq=greenv=bluev=blue蓝色字体为赋蓝色字体为赋值结果值结果弧相容算法思想弧相容算法思想1. 用队列记录需要检验不相容的弧。用队列记录需要检验不相容的弧。2. 每条弧每条弧xi, xj依次从队列中删除并被检验。依次从队列中删除并被检验。如果如果xi值域中的任何一个值需要删除，则每个值域中的任何一个值需要删除，则每个指指向向xi的弧的弧xk, xi都必须重新插入队列进行检验。都必须重新插入队列进行检验。 因为指向这个变量的弧可能产生新的不相容（原因为指向这个变量的弧可能产生新的不相容（原来可能

14、就是因为这个值产生了它们之间的相容）。来可能就是因为这个值产生了它们之间的相容）。时间复杂度：时间复杂度：二元二元csp约束至多有约束至多有o(n2)条弧；条弧； 每每条弧至多插入队列条弧至多插入队列d次（次（d个取值），检验一条弧为个取值），检验一条弧为o(d2)，因此算法的最坏情况下为，因此算法的最坏情况下为o(n2d3)。弧相容算法弧相容算法ac-31. function ac-3(csp) returns the csp, possibly with reduced domains2. inputs: csp, a binary csp with variables x1, x2, .

15、, xn3. local variables: queue, a queue of arcs, initially all the arcs in csp4. while queue is not empty do5. (xi, xj) remove-first( queue )6. if rm-inconsistent-values(xi, xj) then7. for each xk in neighborsxi do8. add (xk, xi) to queue1. function rm-inconsistent-values(xi, xj) returns true iff rem

16、ove a value1. removed false2. for each x in domainxi do3. if no value y in domainxj allows (x,y) to satisfy constraint(xi, xj)4. then delete x from domainxi; removed true5. return removed弧相容的使用弧相容的使用 弧相容检验可以用作开始弧相容检验可以用作开始搜索之前搜索之前的的预处理预处理。 弧相容检验也可以在弧相容检验也可以在搜索过程中搜索过程中每次赋值后用作一个每次赋值后用作一个约束传播步骤约束传播步骤。

17、即反复检测某个变量值域中的不相容弧，进行值即反复检测某个变量值域中的不相容弧，进行值删除，直到不再有矛盾。删除，直到不再有矛盾。 称为称为保持弧相容（保持弧相容（mac）。从弧相容推广到从弧相容推广到k相容相容 如果对于如果对于任何任何k1个变量的相容赋值个变量的相容赋值，第，第k个变量总个变量总能被赋予一个与前能被赋予一个与前k1个变量相容的值，那么该个变量相容的值，那么该csp问题是问题是k相容相容的。的。 1相容是指每个单独的变量自己是不矛盾的，也称为相容是指每个单独的变量自己是不矛盾的，也称为节点相容节点相容。 弧相容弧相容2相容。相容。 3相容是指任何一对相邻的变量总可以扩展到第三个

18、相容是指任何一对相邻的变量总可以扩展到第三个邻居变量，也称为邻居变量，也称为路径相容路径相容。 如果一个图是如果一个图是k相容的，也是相容的，也是k-1相容的、相容的、k-2相容相容的，的，直到，直到1相容，那么这个图是相容，那么这个图是强强k相容相容的。的。从弧相容推广到从弧相容推广到k相容相容 如果一个如果一个csp问题有问题有n个结点，而且它是强个结点，而且它是强n相容的，相容的，则不需要回溯就能求解这个问题。则不需要回溯就能求解这个问题。 可以在可以在o(nd)时间内找到解。时间内找到解。 no free lunch：任何建立任何建立n相容的算法在最坏情况相容的算法在最坏情况下必须花费

19、下必须花费n的指数级时间。的指数级时间。 从弧相容到从弧相容到n相容：相容：执行较强的相容性检验会花费更执行较强的相容性检验会花费更多的时间，但是会更有效地降低分支因子和检测出多的时间，但是会更有效地降低分支因子和检测出矛盾的不完全赋值。矛盾的不完全赋值。特殊约束特殊约束 实际问题中出现的实际问题中出现的特殊约束特殊约束，用，用专用算法专用算法处理其效率处理其效率要比要比通用的约束处理算法通用的约束处理算法高很多。高很多。特殊约束特殊约束 例如，例如，alldiff约束约束，变量取值各不相同变量取值各不相同 假设约束涉及假设约束涉及m个变量，所有变量共有个变量，所有变量共有n个取值，个取值，如

20、果如果mn，则此约束不能被满足。，则此约束不能被满足。 引出相应的引出相应的算法算法： 删除约束中只有单值值域的变量，将这些变量的删除约束中只有单值值域的变量，将这些变量的取值从其余变量值域中删去；取值从其余变量值域中删去； 对单值变量重复此过程；对单值变量重复此过程； 如果得到空的值域或剩下的变量数大于取值数，如果得到空的值域或剩下的变量数大于取值数，则产生矛盾。则产生矛盾。特殊约束特殊约束 资源约束资源约束，有时称为，有时称为atmost约束约束。 例如，例如，用用pa1, , pa4表示分配给四项任务的人员个表示分配给四项任务的人员个数，人员数总计不超过数，人员数总计不超过10人的约束记

21、为人的约束记为atmost(10, pa1, , pa4)。 如果每个变量的赋值为如果每个变量的赋值为3, 4, 5, 6，就不能，就不能满足满足atmost约束。约束。 通过检验当前值域中的最小值之和就能检测出矛通过检验当前值域中的最小值之和就能检测出矛盾。盾。特殊约束特殊约束 对于大型的整数值的资源限制问题，用整数集合来表示每个对于大型的整数值的资源限制问题，用整数集合来表示每个变量的值域然后通过相容性检验方法逐步削减集合，通常是变量的值域然后通过相容性检验方法逐步削减集合，通常是不可能的。不可能的。 取代办法：值域用上界和下界来表示，并通过取代办法：值域用上界和下界来表示，并通过边界传播

22、边界传播来来管理。管理。 例、例、假设有假设有2次航班，次航班，271和和272，它们分别有，它们分别有165和和385个座个座位。每次航班可承载的初始值域为位。每次航班可承载的初始值域为flight2710, 165，flight2720, 385。 设又增加一个约束，两次航班所承载的总乘客数必须是设又增加一个约束，两次航班所承载的总乘客数必须是420。通过边界传播约束，可以把这两个值域削减到通过边界传播约束，可以把这两个值域削减到flight27135, 165，flight272255, 385。 如果对于每个变量如果对于每个变量x和它的取值的上下界，每个变量和它的取值的上下界，每个变量

23、y都存在都存在某个取值满足某个取值满足x和和y之间的约束，我们称该之间的约束，我们称该csp问题是问题是边界相边界相容容的。的。本章内容本章内容 6.1 约束满足问题约束满足问题 6.2 约束传播：约束传播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 问题的结构问题的结构csp的回溯搜索的回溯搜索 csp问题具有一个性质：问题具有一个性质：可交换性可交换性，变量赋值的，变量赋值的顺序对结果没有影响。顺序对结果没有影响。 所有所有csp搜索算法生成后继节点时，在搜索树搜索算法生成后继节点时，在搜索树每个节点上只考虑每个节点上只考虑单个变

24、量单个变量的可能赋值。的可能赋值。 csp问题的求解：问题的求解：深度优先的回溯搜索深度优先的回溯搜索。每次给一个变量赋值，当没有合法赋值每次给一个变量赋值，当没有合法赋值( (不满不满足约束时足约束时) )就要推翻前一个变量的赋值，重新就要推翻前一个变量的赋值，重新给其赋值，这就是回溯。给其赋值，这就是回溯。简单回溯法生成的搜索树简单回溯法生成的搜索树 澳大利亚地图染色问题的搜索树澳大利亚地图染色问题的搜索树wa=redwa=rednt=greenwa=rednt=bluewa=rednt=greenq=redwa=rednt=greenq=bluewa=greenwa=bluewantsa

25、nswqvt一个简单的回溯算法一个简单的回溯算法（深度优先）（深度优先）1. function backtracking-search( csp ) returns a solution, or failure2. return recursive-backtracking( , csp )1. function recursive-backtracking( assignment, csp ) returns a solution, or failure2. if assignment is complete then return assignment3. varselect-unassi

26、gned-variable(variablescsp, assignment, csp)4. for each value in order-domain-values( var, assignment, csp ) do5. if value is consistent with assignment according to constraintscsp then6. add var=value to assignment7. result recursive-backtracking( assignment, csp )8. if result != failure then retur

27、n result9. remove var=value from assignment10. return failure回溯搜索的通用算法回溯搜索的通用算法 需改善需改善无信息无信息回溯搜索算法的性能。回溯搜索算法的性能。 通用改进方法通用改进方法的思路：的思路：下一步该给下一步该给哪个变量哪个变量赋值，按赋值，按什么顺序什么顺序给该变量给该变量赋值？赋值？每步搜索应该做怎样的推理？每步搜索应该做怎样的推理？当前变量的赋值会当前变量的赋值会对其他未赋值变量产生什么约束，怎样利用这种对其他未赋值变量产生什么约束，怎样利用这种约束以提高效率。约束以提高效率。当遇到某个失败的变量赋值时，怎样当遇到

28、某个失败的变量赋值时，怎样避免同样的避免同样的失败失败？就是说如何找到对这种失败起到关键作用？就是说如何找到对这种失败起到关键作用的某个变量赋值。的某个变量赋值。csp回溯搜索的改进回溯搜索的改进基于变量和赋值次序的启发式基于变量和赋值次序的启发式搜索与推理交错进行搜索与推理交错进行智能回溯：向后看智能回溯：向后看csp回溯搜索的改进回溯搜索的改进基于变量和赋值次序的启发式基于变量和赋值次序的启发式mrv（最少剩余值）启发式（最少剩余值）启发式最少约束值启发式最少约束值启发式度启发式度启发式搜索与推理交错进行搜索与推理交错进行智能回溯：向后看智能回溯：向后看mrv启发式启发式 随机的变量赋值排

29、序难以产生高效率的搜索。随机的变量赋值排序难以产生高效率的搜索。 例如：例如：在在wa=red/nt=green条件下选取条件下选取sa赋值比赋值比q要减少赋要减少赋值次数值次数(1:2)，并且一旦给定，并且一旦给定sa赋值以后，赋值以后，q、nsw和和v的赋的赋值只有一个选择。值只有一个选择。wantsanswqvt因此，应当选择合法取值最少的变量，即因此，应当选择合法取值最少的变量，即最少剩余值最少剩余值(mrv)启启发式发式，也称为，也称为最受约束变量最受约束变量启发式启发式或或失败优先启发式失败优先启发式。称为称为失败优先启发式失败优先启发式是因为它可以很快找到失败的变量，从是因为它可

30、以很快找到失败的变量，从而引起搜索的剪枝，避免更多导致同样失败的搜索。而引起搜索的剪枝，避免更多导致同样失败的搜索。最少约束值启发式最少约束值启发式 mrv启发式启发式当有多个变量需要选择时，优先选择在当前约当有多个变量需要选择时，优先选择在当前约束下取值最少的变量。束下取值最少的变量。 问题：问题：一旦变量被选定，算法就要决定它的取值的次序。一旦变量被选定，算法就要决定它的取值的次序。 最少约束值启发式：最少约束值启发式：当赋值的变量有多个值选择时，优先的当赋值的变量有多个值选择时，优先的值应是约束图中排除邻居变量的可选值最少的，即优先选择值应是约束图中排除邻居变量的可选值最少的，即优先选择

31、为剩余变量的赋值留下最多选择的赋值。为剩余变量的赋值留下最多选择的赋值。 例如，例如，wa=red且且nt=green时，如果给时，如果给q赋值，可以为赋值，可以为blue或或red，而，而q=blue的选择不好，因为此时的选择不好，因为此时sa没有一个没有一个可选择的了。可选择的了。wantsanswqvt 如果要找出问题的所有如果要找出问题的所有解，则排序问题无所谓。解，则排序问题无所谓。度启发式度启发式 mrv启发式：启发式：当有多个变量需要选择时，优先选择在当前约当有多个变量需要选择时，优先选择在当前约束下取值最少的变量。束下取值最少的变量。 问题：问题：对澳大利亚地图着色问题中选择第

32、一个染色问题根对澳大利亚地图着色问题中选择第一个染色问题根本没有帮助，因为初始的时候每个区域都有本没有帮助，因为初始的时候每个区域都有3种选择。种选择。 度启发式度启发式：选择涉及对其他未赋值变量的约束数量大：选择涉及对其他未赋值变量的约束数量大（与其（与其他变量关联最多）他变量关联最多）的变量。的变量。地图染色例子中，度地图染色例子中，度(sa)=5(sa)=5，其他均为，其他均为2 2或或3 3。实际上，一旦选择了实际上，一旦选择了sasa作为初始节点，应用度启发式求解作为初始节点，应用度启发式求解本问题，则可以不经任何回溯就找到解。本问题，则可以不经任何回溯就找到解。wantsanswq

33、vtsa=red nt=green q=blue nsw=green wa=blue v=blue tredcsp回溯搜索的改进回溯搜索的改进基于变量和赋值次序的启发式基于变量和赋值次序的启发式搜索与推理交错进行搜索与推理交错进行智能回溯：向后看智能回溯：向后看搜索与推理交错进行搜索与推理交错进行一般的回溯算法：一般的回溯算法：只有在选择了一个变量的时候才只有在选择了一个变量的时候才考虑变量的约束。考虑变量的约束。变量约束的启发式变量约束的启发式：在搜索的早些时候，或开始之在搜索的早些时候，或开始之前就考虑某些约束，从而降低搜索空间。前就考虑某些约束，从而降低搜索空间。 约束传播约束传播 最简

34、单的推理形式：最简单的推理形式：前向检验前向检验前向检验前向检验 前向检验：前向检验：如果如果x被赋值，前向检验就是检查与被赋值，前向检验就是检查与x相相连的那些变量连的那些变量y，看看它们是否满足相关约束，并从，看看它们是否满足相关约束，并从y的值域中删去与的值域中删去与x取值矛盾的那些赋值。取值矛盾的那些赋值。wantqnswvsargbrgbrgbrgbrgbrgb gbrgbrgb rgb gb b r brgb b b r -wa=redwa=redq=greenq=greenv=bluev=blue蓝色字体为赋蓝色字体为赋值结果值结果 赋值赋值v=blue引起矛盾，此时引起矛盾，此

35、时sa赋值为空，不满足赋值为空，不满足问题约束，此时算法就要立刻回溯。问题约束，此时算法就要立刻回溯。前向检验前向检验 前向检验可与前向检验可与mrv启发式启发式相结合。相结合。 实际上，实际上，mrv要做的就是向前找合适的变量。要做的就是向前找合适的变量。 注意：注意：这里只是检验一步这里只是检验一步，即和当前节点是否矛盾。，即和当前节点是否矛盾。 前向检验看得不够远。虽然前向检验能检验出许前向检验看得不够远。虽然前向检验能检验出许多矛盾，它还是不能检验出所有的矛盾。多矛盾，它还是不能检验出所有的矛盾。 被检验节点之间的约束检验还不能进行。被检验节点之间的约束检验还不能进行。 改进：改进：约

36、束传播约束传播。csp回溯搜索的改进回溯搜索的改进基于变量和赋值次序的启发式基于变量和赋值次序的启发式搜索与推理交错进行搜索与推理交错进行智能回溯：向后看智能回溯：向后看向后看智能回溯向后看智能回溯 在回溯算法中，当发现不满足约束即搜索失败时，在回溯算法中，当发现不满足约束即搜索失败时，则回到上一个变量并尝试下一个取值，这称为则回到上一个变量并尝试下一个取值，这称为历时历时回溯回溯。 在很多情况下这样做是效率很低的，因为问题并在很多情况下这样做是效率很低的，因为问题并不决定于上一个不决定于上一个（甚至几个）（甚至几个）变量的取值。变量的取值。 回溯应倒退到回溯应倒退到导致失败的变量的集合导致失

37、败的变量的集合中的一个变量。中的一个变量。 该集合称为该集合称为冲突集冲突集。 变量变量x的的冲突集冲突集是通过约是通过约束与束与x相连接的、先前已赋相连接的、先前已赋值变量的集合。值变量的集合。冲突集冲突集 对于地图染色问题，设有不完全赋值对于地图染色问题，设有不完全赋值q=red, nsw=green, v=blue, t=red 。wantsanswqvt 此时，给此时，给sa赋值将发现无法满足任何约束，赋值将发现无法满足任何约束，sa的的冲突集冲突集=q, nsw, v。后向跳转后向跳转 后向跳转：后向跳转：回溯到回溯到冲突集冲突集中时间最近中时间最近（最后赋值）（最后赋值）的变量。的

38、变量。 对于对于前向检验前向检验算法，可以很容易得到冲突集。算法，可以很容易得到冲突集。基于基于x x赋值的前向检验从变量赋值的前向检验从变量y y的值域中删除一个值时，说的值域中删除一个值时，说明明x x和和y y存在冲突，则显然存在冲突，则显然x x是是y y的冲突集中的一个变量。的冲突集中的一个变量。当到达当到达y y时，可知回溯到哪个变量。时，可知回溯到哪个变量。 对于对于弧相容检验弧相容检验，因为都是做取值相容的检测，只要在弧相，因为都是做取值相容的检测，只要在弧相容检验时增加一个变量集合记录即可。容检验时增加一个变量集合记录即可。后向跳转后向跳转 问题：问题：后向跳转后向跳转只出现

39、在值域中的每个值都和当前只出现在值域中的每个值都和当前的赋值有冲突的情况下，但是的赋值有冲突的情况下，但是前向检验前向检验能检测到这能检测到这个事件并且一旦到达这样的结点就阻止搜索。个事件并且一旦到达这样的结点就阻止搜索。 可以证明：可以证明：每个被每个被后向跳转后向跳转剪枝的分支在剪枝的分支在前向检前向检验验算法中也被剪枝。算法中也被剪枝。 因此，因此，简单的后向跳转简单的后向跳转在在前向检验前向检验搜索中，或者搜索中，或者在诸如在诸如mac（保持弧相容保持弧相容）这样使用更强的相容）这样使用更强的相容性检验的搜索中是性检验的搜索中是多余的多余的。冲突指导的后向跳转冲突指导的后向跳转 很多情

40、况下，一个分支发生很久以前就已经注定要失败了。很多情况下，一个分支发生很久以前就已经注定要失败了。 例，例，考虑不完全赋值考虑不完全赋值wa=red, nsw=red。 假设下一个赋值尝试假设下一个赋值尝试t=red，然后给，然后给nt，q，v，sa赋值。赋值。wantsanswqvt因为最后的四个变量因为最后的四个变量nt，q，v，sa没有相容的赋值，因没有相容的赋值，因此最终我们尝试了此最终我们尝试了nt的所有可能取值。的所有可能取值。现在的问题是向哪里回溯？现在的问题是向哪里回溯？后向跳转行不通后向跳转行不通：nt确实确实有有和已赋值变量相容的值，但和已赋值变量相容的值，但nt没有没有完

41、整的由前面能导致失败的变量组成的冲突集。完整的由前面能导致失败的变量组成的冲突集。冲突指导的后向跳转冲突指导的后向跳转 变量冲突集更一般的情况：变量冲突集更一般的情况：前面的变量集合前面的变量集合使得使得当当前变量前变量连同连同任何后继变量任何后继变量一起没有相容解。一起没有相容解。 冲突指导的后向跳转处理：冲突指导的后向跳转处理： 令令xj是当前变量，是当前变量，conf(xj)是其冲突集。是其冲突集。 如果如果xj每个可能取值都失败了，则后向跳转到每个可能取值都失败了，则后向跳转到conf(xj)中最近的一个变量中最近的一个变量xi，令，令conf(xi)=conf(xi)conf(xj)

42、 - xi。 从从xi向前是无解的，从向前是无解的，从xi回到某个以前的变量赋回到某个以前的变量赋值。值。冲突指导的后向跳转冲突指导的后向跳转 例，例，考虑不完全赋值考虑不完全赋值wa=red, nsw=red。 假设下一个赋值尝试假设下一个赋值尝试t=red，然后给，然后给nt，q，v，sa赋值。赋值。 因为最后四个变量因为最后四个变量nt，q，v，sa没有相容的赋值，回溯。没有相容的赋值，回溯。 sa的冲突集是的冲突集是wa, nt, q，后向跳转到，后向跳转到q。 q将将sa的冲突集（减去的冲突集（减去q）吸收到自己的冲突集里，则）吸收到自己的冲突集里，则q的新的冲突集为的新的冲突集为w

43、a, nt, nsw。 给定了给定了wa, nt, nsw的赋值后，从的赋值后，从q向前是无解的。向前是无解的。 回溯到回溯到nt，nt的冲突集变为的冲突集变为wa, nt, nsw - nt+ wa = wa, nsw。 后向跳转到后向跳转到nsw。wantsanswqvt本章内容本章内容 6.1 约束满足问题约束满足问题 6.2 约束传播：约束传播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 问题的结构问题的结构约束满足问题的局部搜索约束满足问题的局部搜索 完全状态的形式化：完全状态的形式化：初始状态给每个变量赋值，后初始状态给每

44、个变量赋值，后继函数一次继函数一次改变改变一个变量的取值。一个变量的取值。 在为变量选择新值时，最明显的启发式是：在为变量选择新值时，最明显的启发式是： 选择与其它变量的冲突最小的值，选择与其它变量的冲突最小的值，最小冲突启发最小冲突启发式式。 用最小冲突算法解决八皇后问题。用最小冲突算法解决八皇后问题。 每一步选择一个皇后，在它所在的列中重新分配位置。每一步选择一个皇后，在它所在的列中重新分配位置。 算法将皇后移到算法将皇后移到最小冲突最小冲突的方格中，最小冲突值有多个的方格中，最小冲突值有多个方格时则随机地选取一个。方格时则随机地选取一个。例、八皇后问题例、八皇后问题约束满足问题的局部搜索

45、约束满足问题的局部搜索1.function min-conflicts(csp, max_steps) return solution or failure2. inputs: csp, a constraint satisfaction problem3.max_steps, the number of steps allowed before giving up4. current an initial complete assignment for csp5. for i = 1 to max_steps do6. if current is a solution for csp the

46、n return current7.var a randomly chosen, conflicted variable from 8. variables csp 9.value the value v for var that minimizes 10. conflicts( var, v, current, csp )11.set var = value in current12. return faiilure 一个用局部搜索解决一个用局部搜索解决csp问题的问题的min-conflicts算法算法。局部搜索算法的表现局部搜索算法的表现 miniconflict算法对许多算法对许多cs

47、p都惊人地有效，尤其是给定都惊人地有效，尤其是给定了了合理的初始状态合理的初始状态时。时。 例如，对于八皇后问题，如果不计算皇后的初始位置，算例如，对于八皇后问题，如果不计算皇后的初始位置，算法的运行时间大体上独立于问题的大小。法的运行时间大体上独立于问题的大小。 百万皇后问题，平均百万皇后问题，平均50步（给定了初始赋值后）步（给定了初始赋值后） 局部搜索算法的另一个优势是当问题改变时可用于局部搜索算法的另一个优势是当问题改变时可用于联机设置联机设置。 这在这在调度问题调度问题中尤其重要。中尤其重要。 例如，恶劣天气导致航班日程表要修改，总是希望以最小例如，恶劣天气导致航班日程表要修改，总是

48、希望以最小改动来修改日程。改动来修改日程。 很容易很容易csp问题转换成问题转换成最优化最优化问题。这样，问题。这样，爬山法、模拟退爬山法、模拟退化和遗传算法等化和遗传算法等都可以用来最优化目标函数。都可以用来最优化目标函数。本章内容本章内容 6.1 约束满足问题约束满足问题 6.2 约束传播：约束传播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 问题的结构问题的结构问题的结构问题的结构 问题的结构，如约束图表示的，可利用来找到问题的解。问题的结构，如约束图表示的，可利用来找到问题的解。 假设一个假设一个csp问题的变量个数为问题的变

49、量个数为n，所有变量的值域大小，所有变量的值域大小 d，则问题的可能的完全赋值的数量为则问题的可能的完全赋值的数量为o(dn)。 分解方法：分解方法：将约束图分解为将约束图分解为连通域的并集连通域的并集以降低问题的复杂以降低问题的复杂度。度。 例子：澳大利亚地图中例子：澳大利亚地图中tasmania与大陆不相连。与大陆不相连。 假设每个连通域对应一个子问题假设每个连通域对应一个子问题cspi。如果赋值。如果赋值si是是cspi的的一个解，则一个解，则isi是是icspi的一个解。的一个解。 假设总计有假设总计有n个变量，每个个变量，每个si有有c个变量，则共计个变量，则共计n/c个子个子问题，

50、每个子问题最多花费问题，每个子问题最多花费dc步工作，则总工作量为步工作，则总工作量为o(dcn/c)。约束图是约束图是树树 问题：问题：完全独立的子问题很少见完全独立的子问题很少见。 考虑约束图是考虑约束图是树树的情景，即任何两个变量最多通过的情景，即任何两个变量最多通过一条路径连通。一条路径连通。约束图是约束图是树树求解算法：求解算法：1. 任选一个节点作为根节点，从根节点到叶节点按顺序排列，任选一个节点作为根节点，从根节点到叶节点按顺序排列，每个节点的父节点都在它前面。按顺序把它们标为每个节点的父节点都在它前面。按顺序把它们标为x1，xn。2. 令令j从从n到到2，在弧，在弧(xi, x

51、j)上应用上应用弧相容弧相容算法，其中算法，其中xi是是xj的的父节点，从父节点，从domainxi中删除必要的值。中删除必要的值。3. 令令j从从1到到n，赋给，赋给xj与与xi的值相容的值。的值相容的值。 第第2步之后的步之后的csp是是有向弧相容有向弧相容的；的； 被删掉的值不会危及已处理过的弧的相容性。被删掉的值不会危及已处理过的弧的相容性。 第第3步，赋值不需要回溯。步，赋值不需要回溯。 时间复杂度：时间复杂度：o(nd2)。将一般的约束图简化为树形式将一般的约束图简化为树形式 将一般的约束图简化为树形式，有将一般的约束图简化为树形式，有2中基本方式：中基本方式： 基于删除节点的。基

52、于删除节点的。 基于合并节点的。基于合并节点的。基于删除节点的方式基于删除节点的方式 先对某些变量赋值，使剩下的变量构成一棵树。先对某些变量赋值，使剩下的变量构成一棵树。 例：例：澳大利亚的约束图，给澳大利亚的约束图，给sa赋值，并从其它变赋值，并从其它变量的值域中删去与该值不相容的值。量的值域中删去与该值不相容的值。基于删除节点方式的一般算法基于删除节点方式的一般算法1.从从variablescsp中选泽一个子集中选泽一个子集s，使得约束图在删除，使得约束图在删除s之后成为一颗树。之后成为一颗树。s称为称为环割集环割集。2.对满足对满足s所有约束条件的所有约束条件的s中变量的中变量的每个可能赋值每个可能赋值：a)从从剩余变量剩余变量的值域中删除与的值域中删除与s的赋值不相容的值；的赋值不相容的值；b)如果去掉如果去掉s后的剩余后的剩余csp有解，把有解，把解和解和s的赋值的赋值一起返回。一起返回。 如果环割集的大小为如果环割集的大小为c，那么总的运行时间为，那么总的运行时间为o(dc(n-c)d2)。 寻找最小环割集是个寻找最小环割集是个np难题难题。 采用一些已有的高效近似算法，即采用一些已有的高效近似算法，即割集调整割集调整。基于合并节点的方式基于合并节点的方式 基于合并节点的方式：基于合并节点的方式：建立在构造约束图的建立在构造约束图的树分解树分解的基础上，的基础上