ch5 约束满足问题 人工智能课程 北大计算机研究所

1、第五章、约束满足问题pCh3&4：通过搜索状态空间求解问题l把状态看作一个黑盒子，只能由问题特定的例行程序来访问后继函数、启发函数和目标测试。p约束满足问题：利用状态的结构以及通用的、而不是问题特定的启发式来定义搜索算法。第五章、约束满足问题p约束满足问题（CSP）pCSP问题的回溯搜索p约束满足问题的局部搜索p问题的结构约束满足问题pCSP由一个变量集合和一个约束集合组成p问题的一个状态是由对一些或全部变量的一个赋值定义的l完全赋值：每个变量都参与的赋值p问题的解是满足所有约束的完全赋值，或更进一步，使目标函数最大化。例子：澳大利亚地图的染色p对每个区域染上红、绿或蓝色，使得没有相邻的区域颜

2、色相同。将问题形式化为CSPCSP问题的增量形式化p初始状态p后继函数：给任何未赋值的变量赋值（满足约束）p目标测试p路径耗散CSP（续）p经常用深度优先搜索算法求解p变量l离散或连续l值域：有限或无限p约束l线性或非线性l一元或多元：通过引入辅助变量，转为二元约束。l绝对vs偏好第五章、约束满足问题p约束满足问题（CSP）pCSP问题的回溯搜索p约束满足问题的局部搜索p问题的结构CSP问题的回溯搜索p一次为一个变量选择值，当没合法值可以再赋给该变量时就回溯。一个简单的回溯算法以递归深度优先算法为模型讨论p一般的回溯是无信息算法，不期望它对大型问题有效 (见课本图5.5)p不用领域特定的知识而

3、用通用方法解决以下问题:l下步该给哪个变量赋值，按什么顺序来尝试它的值？l当前的变量赋值对其它未赋值的变量意味着什么？l当一条路径失败时，在后面的路径中能避免同样的失败吗？变量和取值顺序pvarSELECT-UNASSIGNED-VARIBLE (VARIBLEcsp, assignment, csp)l选择“合法”取值最少的变量，称为最少剩余式（MRV）l在初始时选择涉及对其它未赋值变量的约束数最大的变量来试图降低未来选择的分支因子（度启发式）。p变量被选定后，如何决定它的取值顺序？l最少约束值启发式：优先选择的值是在约束图中排除邻居变量的可选值最少的。通过约束传播信息p在搜索的早些时候，或

4、开始之前就考虑某些约束，从而降低搜索空间。l向前检验l约束传播l处理特殊约束l智能回溯：向后看向前检验p只要变量X被赋值，向前检验考察每个通过约束和X相连的未赋值变量Y，并从Y的值域中删除与X的取值矛盾的值。约束传播：将一个变量的约束传播到其它变量上p前向检验看得不够远p比前向检验更强的约束传播的方法：弧相容（MAC）p弧相容算法AC-3的时间复杂度是O(n2d3)。p推广到k相容弧相容算法AC-3k相容p如果对于任何k1个变量的相容赋值，第k个变量总能被赋予一个与前k1个变量相容的值，那么该CSP问题是k相容的。p弧相容2相容处理特殊约束：应用专门算法p删除约束中只有单值值域的变量，然后将这

5、些变量的取值从其余变量的值域中删去（重复该过程）。l例子：WA=red, NSW=red，高阶约束。智能回溯：向后看p对历时回溯的改进l历时回溯：重新访问的是时间最近的决策点p例子：按照Q,NSW,V,T,SA,WA,NT的顺序访问节点，并且假设Q=r,NSW=g,V=b,T=rl在SA时出现矛盾，如何回溯？l回溯到导致失败的变量集合中的一个变量：冲突集p提前发现失败HWp5.2,5.6第五章、约束满足问题p约束满足问题（CSP）pCSP问题的回溯搜索p约束满足问题的局部搜索p问题的结构基本思想p完全状态的形式化p初始状态给每个变量赋值，后继函数一次改变一个变量的取值。p在为变量选择新值时，可

6、能的启发式函数：l导致与其它变量的冲突最小的值一个用局部搜索解决CSP问题的Min-conflicts算法function MIN-CONFLICTS(csp, max_steps) return solution or failureinputs: csp, a constraint satisfaction problemmax_steps, the number of steps allowed before giving upcurrent an initial complete assignment for cspfor i = 1 to max_steps doif current

7、 is a solution for csp then return currentvar a randomly chosen, conflicted variable from VARIABLEScspvalue the value v for var that minimizes CONFLICTS(var,v,current,csp)set var = value in currentreturn faiilureSource：Tom Lenaerts course slides用最小冲突算法解决八皇后问题的一个两步的解。每步选择一个皇后，在它所在的列中重新分配位置。算法将皇后移到最小冲

8、突的方格中。例子：八皇后问题局部搜索算法的表现pMiniconflict算法对许多CSP都惊人地有效，尤其在给定了合理的初始状态下。l例如八皇后问题，如果不计算皇后的初始状态，算法的运行时间大体上独立于问题的大小。p局部搜索算法的另一个优势是当问题改变时可用于联机设置l在调度问题中尤其重要第五章、约束满足问题p约束满足问题（CSP）pCSP问题的回溯搜索p约束满足问题的局部搜索p问题的结构问题的结构：利用来找到问题的解p假设一个CSP问题的变量个数为n，所有变量的值域大小d，则问题的可能的完全赋值的数量为O(dn)。p将约束图分解为连通分支的并集以降低问题的复杂度l例子：澳大利亚地图中Tasm

9、ania与大陆不相连p然而，完全独立的子问题很少见。p考虑约束图是树的情景，即任何两个变量最多通过一条路径连通。树状结构的CSP问题的求解p任选一个节点作为根节点，从根节点到叶节点按顺序排列，每个节点的父节点都在它前面。按顺序把它们标为X1，Xn。p令j从n到2，在弧(Xi, Xj)上应用弧相容算法，其中Xi是Xj的父节点，从DOMAINXi中删除必要的值。p令j从1到n，赋给Xj与Xi的值相容的值。l赋值不需要回溯被删掉的值不会危及已处理过的弧的相容性将一般的约束图简化为树形式p基于删除节点的p基于合并节点的基于删除节点的p先对某些变量赋值，使剩下的变量构成一棵树。p例子：澳大利亚的约束图，

10、给SA赋值，并从其它变量的值域中删去与该值不相容的值。一般算法p从VARIABLEScsp中选泽一个子集S，使得约束图在删除S之后成为一颗树。S称为环割集。p对于满足S所有约束条件的S中变量的每个可能的赋值，l从剩余变量的值域中删除与S的赋值不相容的值，并且l如果去掉S后的剩余CSP有解，把解和S的赋值一起返回。算法的时间复杂度p如果环割集的大小为c，那么总的运行时间为O(dc(n-c)d2)。p寻找最小环割集是个NP难题基于合并节点p把约束图分解为相关联的子问题集p独立求解每个子问题p合并结果澳大利亚约束图的分解一个树分解须满足：p每个原始问题中的变量至少在一个子问题中出现p如果两个变量在原问题中由一个约束相连，那么它们至少同时出现在同一个子问题中（连同约束）p如果一个变量出现在树中的两个子问题中，它必须出现在连接这些子问题的路径上的所有子问题里。任何给定的变量在每个子问题中必须取值相同从各个子问题的解得到全局的解p把每个子问题视为一个大