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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章、约束满足问题,Ch3&4：通过搜索状态空间求解问题,把状态看作一个黑盒子，只能由问题特定的例行程序来访问,后继函数、启发函数和目标测试。,约束满足问题：利用状态的结构以及通用的、而不是问题特定的启发式来定义搜索算法。,第五章、约束满足问题,约束满足问题（CSP）,CSP问题的回溯搜索,约束满足问题的局部搜索,问题的结构,约束满足问题,CSP由一个变量集合和一个约束集合组成,问题的一个状态是由对一些或全部变量的一个赋值定义的,完全赋值：每个变量都参与的赋值,问题的解是满足所有约束的完全赋值，或更进一步，使目标函数最大化。,将问题形式化为CSP,CSP问题的增量形式化,初始状态,后继函数：给任何未赋值的变量赋值（满足约束）,目标测试,路径耗散,CSP（续）,经常用深度优先搜索算法求解,变量,离散或连续,值域：有限或无限,约束,线性或非线性,一元或多元：通过引入辅助变量，转为二元约束。,绝对vs偏好,第五章、约束满足问题,约束满足问题（CSP）,CSP问题的回溯搜索,约束满足问题的局部搜索,问题的结构,一个简单的回溯算法,以递归深度优先算法为模型,变量和取值顺序,var,SELECT-UNASSIGNED-VARIBLE(VARIBLEcsp,assignment,csp),选择“合法”取值最少的变量，称为最少剩余式（MRV）,在初始时选择涉及对其它未赋值变量的约束数最大的变量来试图降低未来选择的分支因子（度启发式）。,变量被选定后，如何决定它的取值顺序？,最少约束值启发式：优先选择的值是在约束图中排除邻居变量的可选值最少的。,向前检验,只要变量X被赋值，向前检验考察每个通过约束和X相连的未赋值变量Y，并从Y的值域中删除与X的取值矛盾的值。,约束传播：将一个变量的约束传播到其它变量上,前向检验看得不够远,比前向检验更强的约束传播的方法：弧相容（MAC）,弧相容算法AC-3的时间复杂度是O(n,2,d,3,)。,推广到k相容,弧相容算法AC-3,k相容,如果对于任何k1个变量的相容赋值，第k个变量总能被赋予一个与前k1个变量相容的值，那么该CSP问题是k相容的。,弧相容2相容,处理特殊约束：应用专门算法,删除约束中只有单值值域的变量，然后将这些变量的取值从其余变量的值域中删去（重复该过程）。,例子：WA=red,NSW=red，高阶约束。,智能回溯：向后看,对历时回溯的改进,历时回溯：重新访问的是时间最近的决策点,例子：按照Q,NSW,V,T,SA,WA,NT的顺序访问节点，并且假设Q=r,NSW=g,V=b,T=r,在SA时出现矛盾，如何回溯？,回溯到导致失败的变量集合中的一个变量：冲突集,提前发现失败,第五章、约束满足问题,约束满足问题（CSP）,CSP问题的回溯搜索,约束满足问题的局部搜索,问题的结构,基本思想,完全状态的形式化,初始状态给每个变量赋值，后继函数一次改变一个变量的取值。,在为变量选择新值时，可能的启发式函数：,导致与其它变量的冲突最小的值,用最小冲突算法解决八皇后问题的一个两步的解。每步选择一个皇后，在它,所在的列中重新分配位置。算法将皇后移到最小冲突的方格中。,例子：八皇后问题,第五章、约束满足问题,约束满足问题（CSP）,CSP问题的回溯搜索,约束满足问题的局部搜索,问题的结构,问题的结构：利用来找到问题的解,假设一个CSP问题的变量个数为n，所有变量的值域大小,d，则问题的可能的完全赋值的数量为O(d,n,)。,将约束图分解为连通分支的并集以降低问题的复杂度,例子：澳大利亚地图中Tasmania与大陆不相连,然而，完全独立的子问题很少见。,考虑约束图是树的情景，即任何两个变量最多通过一条路径连通。,树状结构的CSP问题的求解,任选一个节点作为根节点，从根节点到叶节点按顺序排列，每个节点的父节点都在它前面。按顺序把它们标为X,1,，,，X,n,。,令j从n到2，在弧(X,i,X,j,)上应用弧相容算法，其中X,i,是X,j,的父节点，从DOMAIN,X,i,中删除必要的值。,令j从1到n，赋给X,j,与X,i,的值相容的值。,赋值不需要回溯,被删掉的值不会危及已处理过的弧的相容性,基于删除节点的,先对某些变量赋值，使剩下的变量构成一棵树。,例子：澳大利亚的约束图，给SA赋值，并从其它变量的值域中删去与该值不相容的值。,一般算法,从VARIABLEScsp中选泽一个子集S，使得约束图在删除S之后成为一颗树。S称为环割集。,对于满足S所有约束条件的S中变量的每个可能的赋值，,从剩余变量的值域中删除与S的赋值不相容的值，并且,如果去掉S后的剩余CSP有解，把解和S的赋值一起返回。,算法的时间复杂度,如果环割集的大小为c，那么总的运行时间为O(d,c,(n-c)d,2,)。,寻找最小环割集是个NP难题,基于合并节点,把约束图分解为相关联的子问题集,独立求解每个子问题,合并结果,澳大利亚约束图的分解,一个树分解须满足：,每个原始问题中的变量至少在一个子问题中出现,如果两个变量在原问题中由一个约束相连，那么它们至少同时出现在同一个子问题中（连同约束）,如果一个变量出现在树中的两个子问题中，它必须出现在,连接这些子问题的路径上,的所有子问题里。,任何给定的变量在每个子问题中必须取值相同,从各个子问题的解得到全局的解,把每个子问题视为一个大变量，它的值域是问题所有可能的解的集合。,例如：上图最左边的子问题的值域大小为6。,总结,约束满足问题（CSP）；用图表示它的结构,CSP问题的回溯搜索；深度优先搜索的一种形式,从三个方面优化搜索,约束满足问题的局部搜索,最小冲突启发式,问题的结构,割集调整将问题化为树状结构,树分解将问题化为子问题的树,HW,5.12,5.13,