第6章 约束满足问题.ppt

第6章 约束满足问题,第部分 问题求解,本章内容,6.1 约束满足问题6.2 约束传播：CSP中的推理6.3 CSP的回溯搜索6.4 CSP的局部搜索6.5 问题的结构,例1、澳大利亚地图染色问题(1),澳大利亚地图染色问题：用红绿蓝3色标出各省，相邻者颜色不同。,对应于澳大利亚地图的约束图，相互关联的节点用边连接。,西澳大利亚 WA北领地 NT南澳大利亚 SA昆士兰 Q新南威尔士 NSW维多利亚 V塔斯马尼亚 T,例1、澳大利亚地图染色问题(2),一组满足约束的完全赋值：WA=R,NT=G,Q=R,SA=B,NSW=G,V=R,T=R,约束满足问题的定义,约束满足问题（Constraint Satisfying Problem,CSP）：由一个变量集合X1Xn和一个约束集合C1Cm定义；每个变量都有一个非空可能值域Di；每个约束指定了包含若干变量的一个子集内各变量的赋值范围。例如：地图染色问题，N-皇后问题。CSP的一个状态：对一些或全部变量的赋值 Xi=vi,Xj=vj,。,CSP问题的解,一个不违反任何约束的对变量的赋值称为相容赋值或合法赋值。对每个变量都进行赋值称为完全赋值。一个（一组）对变量的赋值，若既是相容赋值又是完全赋值，则这个（组）赋值是CSP问题的解。某些CSP问题要求问题的解能使目标函数最大化约束优化。CSP问题常常可以可视化，表示为约束图，更直观地显示问题，帮助思考问题的答案。,CSP问题的分类,根据变量的类型划分：离散值域和连续值域。变量离散值域 有限值域，如地图染色问题，八皇后问题。无限值域，如整数集合或者字符串集合。例如，对于作业规划问题，无法枚举所有可能取值，要使用约束语言(线性约束/非线性约束)描述，如StartJob1+5StratJob3。有限值域CSP问题包括布尔CSP问题，它的变量的取值可以是true或false。布尔CSP包括一些典型NP完全问题，如3-SAT问题（命题逻辑语句的可满足性问题），最坏情况下不能指望低于指数级时间复杂性解决该问题。,CSP问题的分类,变量连续值域最著名的连续值域CSP是线性规划问题。线性规划中的约束必须是构成一个凸多边形的一组线性不等式。线性规划问题可以在变量个数的多项式时间内求解。,CSP问题的分类,根据约束的类型划分：线性或非线性约束。一元或多元约束。一元约束：只限制一个变量的取值二元约束与2个变量相关高阶约束：涉及3个或更多变量。通过引入辅助变量，转为二元约束。绝对约束 vs 偏好约束。我们仅讨论绝对约束。,高阶约束的例子,算式T W O+T W O F O U R,例2、密码算术问题。每个字母表示不同的数字。目标是找到能使如下加法式子成立的数字，附加的约束条件是最前面的数字不能为0。,高阶约束的例子,算式T W O+T W O F O U RF=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/O=5(有进位)，则T=7/W=6/U=3，由此得到一组解=1530|765。,四列算式约束：O+O=R+10*X1X1+W+W=U+10*X2X2+T+T=O+10*X3X3=F对应的约束超图如右图。六个变量互不相等约束可化为两两不等约束额的二元约束。,高阶约束的例子,每个约束在图中用方块表示，连接至它所约束的变量。,CSP问题求解的复杂度,CSP问题的求解目标是找到相容的完全赋值，最朴素的想法是依次取变量的赋值组合并检查其是否满足约束条件。若CSP问题的任何一个变量的最大值域为d，那么可能的完全赋值数量为O(dn)。指数级计算量。,本章内容,6.1 约束满足问题6.2 约束传播：CSP中的推理6.3 CSP的回溯搜索6.4 CSP的局部搜索6.5 问题的结构,约束传播,约束传播：使用约束来减小一个变量的合法取值范围，从而影响到与此变量有约束关系的另一变量的取值。弧相容：依次检验约束图中各个相关节点对。注意，弧是有向弧。例如，给定SA/NSW当前值域，如果对于SA的每个取值x，NSW都有某个y和x相容，则SA到NSW的弧是相容的；反过来是NSW到SA的弧相容。,弧相容,在地图染色约束的赋值过程中：第4行SA=blue，NSW=red,blue，则SA的取值有一个NSW=red与之相容；反过来NSW=blue，则SA为空值，即不相容，通过删除NSW值域中的blue可使其相容。弧相容检测也能较早发现矛盾，如第4行SA和NT值域均为blue，则必须删去SA=blue，其值域变为空。用弧相容能够更早地检测到矛盾。,WA=redQ=greenV=blue,蓝色字体为赋值结果,弧相容算法思想,用队列记录需要检验不相容的弧。每条弧Xi,Xj依次从队列中删除并被检验。如果Xi值域中的任何一个值需要删除，则每个指向Xi的弧Xk,Xi都必须重新插入队列进行检验。因为指向这个变量的弧可能产生新的不相容（原来可能就是因为这个值产生了它们之间的相容）。时间复杂度：二元CSP约束至多有O(n2)条弧；每条弧至多插入队列d次（d个取值），检验一条弧为O(d2)，因此算法的最坏情况下为O(n2d3)。,弧相容算法AC-3,function AC-3(csp)returns the CSP,possibly with reduced domains inputs:csp,a binary CSP with variables X1,X2,.,Xn local variables:queue,a queue of arcs,initially all the arcs in csp while queue is not empty do(Xi,Xj)Remove-First(queue)if RM-Inconsistent-Values(Xi,Xj)then for each Xk in NeighborsXi do add(Xk,Xi)to queuefunction RM-Inconsistent-Values(Xi,Xj)returns true iff remove a value removed false for each x in DomainXi do if no value y in DomainXj allows(x,y)to satisfy constraint(Xi,Xj)then delete x from DomainXi;removed true return removed,弧相容的使用,弧相容检验可以用作开始搜索之前的预处理。弧相容检验也可以在搜索过程中每次赋值后用作一个约束传播步骤。即反复检测某个变量值域中的不相容弧，进行值删除，直到不再有矛盾。称为保持弧相容（MAC）。,从弧相容推广到k相容,如果对于任何k1个变量的相容赋值，第k个变量总能被赋予一个与前k1个变量相容的值，那么该CSP问题是k相容的。1相容是指每个单独的变量自己是不矛盾的，也称为节点相容。弧相容2相容。3相容是指任何一对相邻的变量总可以扩展到第三个邻居变量，也称为路径相容。如果一个图是k相容的，也是k-1相容的、k-2相容的，直到1相容，那么这个图是强k相容的。,从弧相容推广到k相容,如果一个CSP问题有n个结点，而且它是强n相容的，则不需要回溯就能求解这个问题。可以在O(nd)时间内找到解。No free Lunch：任何建立n相容的算法在最坏情况下必须花费n的指数级时间。从弧相容到n相容：执行较强的相容性检验会花费更多的时间，但是会更有效地降低分支因子和检测出矛盾的不完全赋值。,特殊约束,实际问题中出现的特殊约束，用专用算法处理其效率要比通用的约束处理算法高很多。,特殊约束,例如，AllDiff约束，变量取值各不相同假设约束涉及m个变量，所有变量共有n个取值，如果mn，则此约束不能被满足。引出相应的算法：删除约束中只有单值值域的变量，将这些变量的取值从其余变量值域中删去；对单值变量重复此过程；如果得到空的值域或剩下的变量数大于取值数，则产生矛盾。,特殊约束,资源约束，有时称为atmost约束。例如，用PA1,PA4表示分配给四项任务的人员个数，人员数总计不超过10人的约束记为atmost(10,PA1,PA4)。如果每个变量的赋值为3,4,5,6，就不能满足atmost约束。通过检验当前值域中的最小值之和就能检测出矛盾。,特殊约束,对于大型的整数值的资源限制问题，用整数集合来表示每个变量的值域然后通过相容性检验方法逐步削减集合，通常是不可能的。取代办法：值域用上界和下界来表示，并通过边界传播来管理。例、假设有2次航班，271和272，它们分别有165和385个座位。每次航班可承载的初始值域为Flight2710,165，Flight2720,385。设又增加一个约束，两次航班所承载的总乘客数必须是420。通过边界传播约束，可以把这两个值域削减到Flight27135,165，Flight272255,385。如果对于每个变量X和它的取值的上下界，每个变量Y都存在某个取值满足X和Y之间的约束，我们称该CSP问题是边界相容的。,本章内容,6.1 约束满足问题6.2 约束传播：CSP中的推理6.3 CSP的回溯搜索6.4 CSP的局部搜索6.5 问题的结构,CSP的回溯搜索,CSP问题具有一个性质：可交换性，变量赋值的顺序对结果没有影响。所有CSP搜索算法生成后继节点时，在搜索树每个节点上只考虑单个变量的可能赋值。CSP问题的求解：深度优先的回溯搜索。每次给一个变量赋值，当没有合法赋值(不满足约束时)就要推翻前一个变量的赋值，重新给其赋值，这就是回溯。,简单回溯法生成的搜索树,澳大利亚地图染色问题的搜索树,一个简单的回溯算法（深度优先）,function BackTracking-Search(csp)returns a solution,or failure return Recursive-BackTracking(,csp)function Recursive-BackTracking(assignment,csp)returns a solution,or failure if assignment is complete then return assignment varSelect-Unassigned-Variable(Variablescsp,assignment,csp)for each value in Order-Domain-Values(var,assignment,csp)do if value is consistent with assignment according to Constraintscsp then add var=value to assignment result Recursive-BackTracking(assignment,csp)if result!=failure then return result remove var=value from assignment return failure,回溯搜索的通用算法,需改善无信息回溯搜索算法的性能。通用改进方法的思路：下一步该给哪个变量赋值，按什么顺序给该变量赋值？每步搜索应该做怎样的推理？当前变量的赋值会对其他未赋值变量产生什么约束，怎样利用这种约束以提高效率。当遇到某个失败的变量赋值时，怎样避免同样的失败？就是说如何找到对这种失败起到关键作用的某个变量赋值。,CSP回溯搜索的改进,基于变量和赋值次序的启发式搜索与推理交错进行智能回溯：向后看,CSP回溯搜索的改进,基于变量和赋值次序的启发式MRV（最少剩余值）启发式最少约束值启发式度启发式搜索与推理交错进行智能回溯：向后看,MRV启发式,随机的变量赋值排序难以产生高效率的搜索。例如：在WA=red/NT=green条件下选取SA赋值比Q要减少赋值次数(1:2)，并且一旦给定SA赋值以后，Q、NSW和V的赋值只有一个选择。,因此，应当选择合法取值最少的变量，即最少剩余值(MRV)启发式，也称为最受约束变量启发式或失败优先启发式。称为失败优先启发式是因为它可以很快找到失败的变量，从而引起搜索的剪枝，避免更多导致同样失败的搜索。,最少约束值启发式,MRV启发式：当有多个变量需要选择时，优先选择在当前约束下取值最少的变量。问题：一旦变量被选定，算法就要决定它的取值的次序。最少约束值启发式：当赋值的变量有多个值选择时，优先的值应是约束图中排除邻居变量的可选值最少的，即优先选择为剩余变量的赋值留下最多选择的赋值。例如，WA=red且NT=green时，如果给Q赋值，可以为blue或red，而Q=blue的选择不好，因为此时SA没有一个可选择的了。,如果要找出问题的所有解，则排序问题无所谓。,度启发式,MRV启发式：当有多个变量需要选择时，优先选择在当前约束下取值最少的变量。问题：对澳大利亚地图着色问题中选择第一个染色问题根本没有帮助，因为初始的时候每个区域都有3种选择。度启发式：选择涉及对其他未赋值变量的约束数量大（与其他变量关联最多）的变量。地图染色例子中，度(SA)=5，其他均为2或3。实际上，一旦选择了SA作为初始节点，应用度启发式求解本问题，则可以不经任何回溯就找到解。,SA=red NT=green Q=blue NSW=green WA=blue V=blue Tred,CSP回溯搜索的改进,基于变量和赋值次序的启发式搜索与推理交错进行智能回溯：向后看,搜索与推理交错进行,一般的回溯算法：只有在选择了一个变量的时候才考虑变量的约束。变量约束的启发式：在搜索的早些时候，或开始之前就考虑某些约束，从而降低搜索空间。约束传播最简单的推理形式：前向检验,前向检验,前向检验：如果X被赋值，前向检验就是检查与X相连的那些变量Y，看看它们是否满足相关约束，并从Y的值域中删去与X取值矛盾的那些赋值。,WA=redQ=greenV=blue,蓝色字体为赋值结果,赋值V=blue引起矛盾，此时SA赋值为空，不满足问题约束，此时算法就要立刻回溯。,前向检验,前向检验可与MRV启发式相结合。实际上，MRV要做的就是向前找合适的变量。注意：这里只是检验一步，即和当前节点是否矛盾。前向检验看得不够远。虽然前向检验能检验出许多矛盾，它还是不能检验出所有的矛盾。被检验节点之间的约束检验还不能进行。改进：约束传播。,CSP回溯搜索的改进,基于变量和赋值次序的启发式搜索与推理交错进行智能回溯：向后看,向后看智能回溯,在回溯算法中，当发现不满足约束即搜索失败时，则回到上一个变量并尝试下一个取值，这称为历时回溯。在很多情况下这样做是效率很低的，因为问题并不决定于上一个（甚至几个）变量的取值。回溯应倒退到导致失败的变量的集合中的一个变量。该集合称为冲突集。变量X的冲突集是通过约束与X相连接的、先前已赋值变量的集合。,冲突集,对于地图染色问题，设有不完全赋值Q=red,NSW=green,V=blue,T=red。,此时，给SA赋值将发现无法满足任何约束，SA的冲突集=Q,NSW,V。,后向跳转,后向跳转：回溯到冲突集中时间最近（最后赋值）的变量。对于前向检验算法，可以很容易得到冲突集。基于X赋值的前向检验从变量Y的值域中删除一个值时，说明X和Y存在冲突，则显然X是Y的冲突集中的一个变量。当到达Y时，可知回溯到哪个变量。对于弧相容检验，因为都是做取值相容的检测，只要在弧相容检验时增加一个变量集合记录即可。,后向跳转,问题：后向跳转只出现在值域中的每个值都和当前的赋值有冲突的情况下，但是前向检验能检测到这个事件并且一旦到达这样的结点就阻止搜索。可以证明：每个被后向跳转剪枝的分支在前向检验算法中也被剪枝。因此，简单的后向跳转在前向检验搜索中，或者在诸如MAC（保持弧相容）这样使用更强的相容性检验的搜索中是多余的。,冲突指导的后向跳转,很多情况下，一个分支发生很久以前就已经注定要失败了。例，考虑不完全赋值WA=red,NSW=red。假设下一个赋值尝试T=red，然后给NT，Q，V，SA赋值。,因为最后的四个变量NT，Q，V，SA没有相容的赋值，因此最终我们尝试了NT的所有可能取值。现在的问题是向哪里回溯？后向跳转行不通：NT确实有和已赋值变量相容的值，但NT没有完整的由前面能导致失败的变量组成的冲突集。,冲突指导的后向跳转,变量冲突集更一般的情况：前面的变量集合使得当前变量连同任何后继变量一起没有相容解。冲突指导的后向跳转处理：令Xj是当前变量，conf(Xj)是其冲突集。如果Xj每个可能取值都失败了，则后向跳转到conf(Xj)中最近的一个变量Xi，令conf(Xi)=conf(Xi)conf(Xj)-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的新的冲突集为WA,NT,NSW。给定了WA,NT,NSW的赋值后，从Q向前是无解的。回溯到NT，NT的冲突集变为WA,NT,NSW-NT+WA=WA,NSW。后向跳转到NSW。,本章内容,6.1 约束满足问题6.2 约束传播：CSP中的推理6.3 CSP的回溯搜索6.4 CSP的局部搜索6.5 问题的结构,约束满足问题的局部搜索,完全状态的形式化：初始状态给每个变量赋值，后继函数一次改变一个变量的取值。在为变量选择新值时，最明显的启发式是：选择与其它变量的冲突最小的值，最小冲突启发式。,用最小冲突算法解决八皇后问题。每一步选择一个皇后，在它所在的列中重新分配位置。算法将皇后移到最小冲突的方格中，最小冲突值有多个方格时则随机地选取一个。,例、八皇后问题,约束满足问题的局部搜索,function MIN-CONFLICTS(csp,max_steps)return solution or failure inputs:csp,a constraint satisfaction problemmax_steps,the number of steps allowed before giving up current an initial complete assignment for csp for i=1 to max_steps do if current is a solution for csp then return currentvar a randomly chosen,conflicted variable from VARIABLES csp value the value v for var that minimizes CONFLICTS(var,v,current,csp)set var=value in current return faiilure,一个用局部搜索解决CSP问题的Min-conflicts算法。,局部搜索算法的表现,Miniconflict算法对许多CSP都惊人地有效，尤其是给定了合理的初始状态时。例如，对于八皇后问题，如果不计算皇后的初始位置，算法的运行时间大体上独立于问题的大小。百万皇后问题，平均50步（给定了初始赋值后）局部搜索算法的另一个优势是当问题改变时可用于联机设置。这在调度问题中尤其重要。例如，恶劣天气导致航班日程表要修改，总是希望以最小改动来修改日程。很容易CSP问题转换成最优化问题。这样，爬山法、模拟退化和遗传算法等都可以用来最优化目标函数。,本章内容,6.1 约束满足问题6.2 约束传播：CSP中的推理6.3 CSP的回溯搜索6.4 CSP的局部搜索6.5 问题的结构,问题的结构,问题的结构，如约束图表示的，可利用来找到问题的解。假设一个CSP问题的变量个数为n，所有变量的值域大小d，则问题的可能的完全赋值的数量为O(dn)。分解方法：将约束图分解为连通域的并集以降低问题的复杂度。例子：澳大利亚地图中Tasmania与大陆不相连。假设每个连通域对应一个子问题CSPi。如果赋值Si是CSPi的一个解，则iSi是iCSPi的一个解。假设总计有n个变量，每个Si有c个变量，则共计n/c个子问题，每个子问题最多花费dc步工作，则总工作量为O(dcn/c)。,约束图是树,问题：完全独立的子问题很少见。考虑约束图是树的情景，即任何两个变量最多通过一条路径连通。,约束图是树,求解算法：任选一个节点作为根节点，从根节点到叶节点按顺序排列，每个节点的父节点都在它前面。按顺序把它们标为X1，Xn。令j从n到2，在弧(Xi,Xj)上应用弧相容算法，其中Xi是Xj的父节点，从DOMAINXi中删除必要的值。令j从1到n，赋给Xj与Xi的值相容的值。,第2步之后的CSP是有向弧相容的；被删掉的值不会危及已处理过的弧的相容性。第3步，赋值不需要回溯。时间复杂度：O(nd2)。,将一般的约束图简化为树形式,将一般的约束图简化为树形式，有2中基本方式：基于删除节点的。基于合并节点的。,基于删除节点的方式,先对某些变量赋值，使剩下的变量构成一棵树。例：澳大利亚的约束图，给SA赋值，并从其它变量的值域中删去与该值不相容的值。,基于删除节点方式的一般算法,从VARIABLEScsp中选泽一个子集S，使得约束图在删除S之后成为一颗树。S称为环割集。对满足S所有约束条件的S中变量的每个可能赋值：从剩余变量的值域中删除与S的赋值不相容的值；如果去掉S后的剩余CSP有解，把解和S的赋值一起返回。,如果环割集的大小为c，那么总的运行时间为O(dc(n-c)d2)。寻找最小环割集是个NP难题。采用一些已有的高效近似算法，即割集调整。,基于合并节点的方式,基于合并节点的方式：建立在构造约束图的树分解的基础上，把约束图分解为相关联的子问题集。独立求解每个子问题合并结果,澳大利亚地图着色问题的约束图的分解,树分解,一个树分解须满足的条件：每个原始问题中的变量至少在一个子问题中出现。如果两个变量在原问题中由一个约束相连，那么它们至少同时出现在同一个子问题中（连同约束）。如果一个变量出现在树中的两个子问题中，它必须出现在连接这些子问题的路径上的所有子问题里。任何给定的变量在每个子问题中必须取值相同。,树分解,从各个子问题的解得到全局的解：把每个子问题视为一个大变量，它的值域是问题所有可能的解的集合。例如：最左边的子问题，有3个变量，有6个解。,树分解,一个给定的约束图允许有多种树分解。在选择不同分解的时候，目标是分解出来的子问题越小越好。图的树分解的树宽比最大的子问题的大小少1。图自身的树宽定义为它所有可能树分解的最小树宽。如果一个图的树宽为w，那么这个问题的时间复杂度是O(ndw+1)。因此，约束图树宽有界的CSP问题是多项式时间内可解的。不幸的是，找到最小树宽的树分解是NP难题。有一些启发式方法。,小结,约束满足问题（CSP），用图表示它的结构CSP问题的回溯搜索；深度优先搜索的一种形式从三个方面优化搜索约束满足问题的局部搜索最小冲突启发式问题的结构割集调整将问题化为树状结构树分解将问题化为子问题的树,课堂练习,澳大利亚地图染色问题，是指用红绿蓝3色标出各省，且相邻者颜色不同。下图给出了澳大利亚地图着色问题的约束图。假设当前所有变量都还没有赋值，按照度启发式，请问应该选择哪一个变量进行赋值？假设已有不完全赋值WA=red，NT=green，下面需要在SA或Q这两个变量之间选择一个进行赋值。如果采用MRV（最少剩余值）启发式来选择变量，请问应该选择哪一个？,假设已有不完全赋值Q=red,NSW=green,V=blue,T=red。此时，给SA赋值将发现无法满足约束条件。请问SA的冲突集是什么？,作业,分别用回溯算法、前向检验算法、MRV和最少约束值启发式算法手工求解密码算术问题。即习题6.5，教材Page 191。Stuart Russell，Peter Norvig著，殷建平等译。Artificial Intelligence A Modern Approach(3rd Edition)。清华大学出版社。,