约束满足问题人工智能课程ppt课件.ppt

《约束满足问题人工智能课程ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、化。3例子：澳大利亚地图的染色对每个区域染上红、绿或蓝色，使得没有相邻的区域颜色相同。4将问题形式化为CSP5CSP问题的增量形式化初始状态后继函数：给任何未赋值的变量赋值（满足约束）目标测试路径耗散6CSP（续）经常用深度优先搜索算法求解变量离散或连续值域：有限或无限约束线性或非线性一元或多元：通过引入辅助变量，转为二元约束。绝对vs偏好7第五章、约束满足问题约束满足问题（CSP）CSP问题的回溯搜索约束满足问题的局部搜索问题的结构8CSP问题的回溯搜索一次为一个变量选择值，当没合法值可以再赋给该变

3、量时就回溯。9一个简单的回溯算法以递归深度优先算法为模型10讨论一般的回溯是无信息算法，不期望它对大型问题有效(见课本图5.5)不用领域特定的知识而用通用方法解决以下问题:下步该给哪个变量赋值，按什么顺序来尝试它的值？当前的变量赋值对其它未赋值的变量意味着什么？当一条路径失败时，在后面的路径中能避免同样的失败吗？11变量和取值顺序var←SELECT-UNASSIGNED-VARIBLE(VARIBLE[csp],assignment,csp)选择“合法”取值最少的变量，称为最少剩余式（MRV）在初始

4、时选择涉及对其它未赋值变量的约束数最大的变量来试图降低未来选择的分支因子（度启发式）。变量被选定后，如何决定它的取值顺序？最少约束值启发式：优先选择的值是在约束图中排除邻居变量的可选值最少的。12通过约束传播信息在搜索的早些时候，或开始之前就考虑某些约束，从而降低搜索空间。向前检验约束传播处理特殊约束智能回溯：向后看13向前检验只要变量X被赋值，向前检验考察每个通过约束和X相连的未赋值变量Y，并从Y的值域中删除与X的取值矛盾的值。14约束传播：将一个变量的约束传播到其它变量上前向检验看得不够远比前向检

5、验更强的约束传播的方法：弧相容（MAC）弧相容算法AC-3的时间复杂度是O(n2d3)。推广到k相容弧相容算法AC-315k相容如果对于任何k－1个变量的相容赋值，第k个变量总能被赋予一个与前k－1个变量相容的值，那么该CSP问题是k相容的。弧相容＝2相容16处理特殊约束：应用专门算法删除约束中只有单值值域的变量，然后将这些变量的取值从其余变量的值域中删去（重复该过程）。例子：{WA=red,NSW=red}，高阶约束。17智能回溯：向后看对历时回溯的改进历时回溯：重新访问的是时间最近的决策点例子：按

6、照Q,NSW,V,T,SA,WA,NT的顺序访问节点，并且假设{Q=r,NSW=g,V=b,T=r}在SA时出现矛盾，如何回溯？回溯到导致失败的变量集合中的一个变量：冲突集提前发现失败18HW5.2,5.619第五章、约束满足问题约束满足问题（CSP）CSP问题的回溯搜索约束满足问题的局部搜索问题的结构20基本思想完全状态的形式化初始状态给每个变量赋值，后继函数一次改变一个变量的取值。在为变量选择新值时，可能的启发式函数：导致与其它变量的冲突最小的值21一个用局部搜索解决CSP问题的Min-confl

7、icts算法functionMIN-CONFLICTS(csp,max_steps)returnsolutionorfailureinputs:csp,aconstraintsatisfactionproblemmax_steps,thenumberofstepsallowedbeforegivingupcurrentaninitialcompleteassignmentforcspfori=1tomax_stepsdoifcurrentisasolutionforcspthenreturncurr

8、entvararandomlychosen,conflictedvariablefromVARIABLES[csp]valuethevaluevforvarthatminimizesCONFLICTS(var,v,current,csp)setvar=valueincurrentreturnfaiilureSource：TomLenaerts’courseslides22用最小冲突算法解决八皇后问题的一个两步的解。每步选择一个皇后，在它所在的列中重新