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

第五章 约束满足问题 Ch3 4 通过搜索状态空间求解问题把状态看作一个黑盒子 只能由问题特定的例行程序来访问 后继函数 启发函数和目标测试 约束满足问题 利用状态的结构以及通用的 而不是问题特定的启发式来定义搜索算法 1 第五章 约束满足问题 约束满足问题 CSP CSP问题的回溯搜索约束满足问题的局部搜索问题的结构 2 约束满足问题 CSP由一个变量集合和一个约束集合组成问题的一个状态是由对一些或全部变量的一个赋值定义的完全赋值 每个变量都参与的赋值问题的解是满足所有约束的完全赋值 或更进一步 使目标函数最大化 3 例子 澳大利亚地图的染色 对每个区域染上红 绿或蓝色 使得没有相邻的区域颜色相同 4 将问题形式化为CSP 5 CSP问题的增量形式化 初始状态后继函数 给任何未赋值的变量赋值 满足约束 目标测试路径耗散 6 CSP 续 经常用深度优先搜索算法求解变量离散或连续值域 有限或无限约束线性或非线性一元或多元 通过引入辅助变量 转为二元约束 绝对vs偏好 7 第五章 约束满足问题 约束满足问题 CSP CSP问题的回溯搜索约束满足问题的局部搜索问题的结构 8 CSP问题的回溯搜索 一次为一个变量选择值 当没合法值可以再赋给该变量时就回溯 9 一个简单的回溯算法 以递归深度优先算法为模型 10 讨论 一般的回溯是无信息算法 不期望它对大型问题有效 见课本图5 5 不用领域特定的知识而用通用方法解决以下问题 下步该给哪个变量赋值 按什么顺序来尝试它的值 当前的变量赋值对其它未赋值的变量意味着什么 当一条路径失败时 在后面的路径中能避免同样的失败吗 11 变量和取值顺序 var SELECT UNASSIGNED VARIBLE VARIBLE csp assignment csp 选择 合法 取值最少的变量 称为最少剩余式 MRV 在初始时选择涉及对其它未赋值变量的约束数最大的变量来试图降低未来选择的分支因子 度启发式 变量被选定后 如何决定它的取值顺序 最少约束值启发式 优先选择的值是在约束图中排除邻居变量的可选值最少的 12 通过约束传播信息 在搜索的早些时候 或开始之前就考虑某些约束 从而降低搜索空间 向前检验约束传播处理特殊约束智能回溯 向后看 13 向前检验 只要变量X被赋值 向前检验考察每个通过约束和X相连的未赋值变量Y 并从Y的值域中删除与X的取值矛盾的值 14 约束传播 将一个变量的约束传播到其它变量上 前向检验看得不够远比前向检验更强的约束传播的方法 弧相容 MAC 弧相容算法AC 3的时间复杂度是O n2d3 推广到k相容 弧相容算法AC 3 15 k相容 如果对于任何k 1个变量的相容赋值 第k个变量总能被赋予一个与前k 1个变量相容的值 那么该CSP问题是k相容的 弧相容 2相容 16 处理特殊约束 应用专门算法 删除约束中只有单值值域的变量 然后将这些变量的取值从其余变量的值域中删去 重复该过程 例子 WA red NSW red 高阶约束 17 智能回溯 向后看 对历时回溯的改进历时回溯 重新访问的是时间最近的决策点例子 按照Q NSW V T SA WA NT的顺序访问节点 并且假设 Q r NSW g V b T r 在SA时出现矛盾 如何回溯 回溯到导致失败的变量集合中的一个变量 冲突集提前发现失败 18 HW 5 2 5 6 19 第五章 约束满足问题 约束满足问题 CSP CSP问题的回溯搜索约束满足问题的局部搜索问题的结构 20 基本思想 完全状态的形式化初始状态给每个变量赋值 后继函数一次改变一个变量的取值 在为变量选择新值时 可能的启发式函数 导致与其它变量的冲突最小的值 21 一个用局部搜索解决CSP问题的Min conflicts算法 functionMIN CONFLICTS csp max steps returnsolutionorfailureinputs csp aconstraintsatisfactionproblemmax steps thenumberofstepsallowedbeforegivingupcurrent aninitialcompleteassignmentforcspfori 1tomax stepsdoifcurrentisasolutionforcspthenreturncurrentvar arandomlychosen conflictedvariablefromVARIABLES csp value thevaluevforvarthatminimizesCONFLICTS var v current csp setvar valueincurrentreturnfaiilure Source TomLenaerts courseslides 22 用最小冲突算法解决八皇后问题的一个两步的解 每步选择一个皇后 在它所在的列中重新分配位置 算法将皇后移到最小冲突的方格中 例子 八皇后问题 23 24 局部搜索算法的表现 Mini conflict算法对许多CSP都惊人地有效 尤其在给定了合理的初始状态下 例如八皇后问题 如果不计算皇后的初始状态 算法的运行时间大体上独立于问题的大小 局部搜索算法的另一个优势是当问题改变时可用于联机设置在调度问题中尤其重要 25 第五章 约束满足问题 约束满足问题 CSP CSP问题的回溯搜索约束满足问题的局部搜索问题的结构 26 问题的结构 利用来找到问题的解 假设一个CSP问题的变量个数为n 所有变量的值域大小 d 则问题的可能的完全赋值的数量为O dn 将约束图分解为连通分支的并集以降低问题的复杂度例子 澳大利亚地图中Tasmania与大陆不相连然而 完全独立的子问题很少见 考虑约束图是树的情景 即任何两个变量最多通过一条路径连通 27 树状结构的CSP问题的求解 任选一个节点作为根节点 从根节点到叶节点按顺序排列 每个节点的父节点都在它前面 按顺序把它们标为X1 Xn 令j从n到2 在弧 Xi Xj 上应用弧相容算法 其中Xi是Xj的父节点 从DOMAIN Xi 中删除必要的值 令j从1到n 赋给Xj与Xi的值相容的值 赋值不需要回溯 被删掉的值不会危及已处理过的弧的相容性 28 将一般的约束图简化为树形式 基于删除节点的基于合并节点的 29 基于删除节点的 先对某些变量赋值 使剩下的变量构成一棵树 例子 澳大利亚的约束图 给SA赋值 并从其它变量的值域中删去与该值不相容的值 30 一般算法 从VARIABLES csp 中选泽一个子集S 使得约束图在删除S之后成为一颗树 S称为环割集 对于满足S所有约束条件的S中变量的每个可能的赋值 从剩余变量的值域中删除与S的赋值不相容的值 并且如果去掉S后的剩余CSP有解 把解和S的赋值一起返回 31 算法的时间复杂度 如果环割集的大小为c 那么总的运行时间为O dc n c d2 寻找最小环割集是个NP难题 32 基于合并节点 把约束图分解为相关联的子问题集独立求解每个子问题合并结果 澳大利亚约束图的分解 33 一个树分解须满足 每个原始问题中的变量至少在一个子问题中出现如果两个变量在原问题中由一个约束相连 那么它们至少同时出现在同一个子问题中 连同约束 如果一个变量出现在树中的两个子问题中 它必须出现在连接这些子问题的路径上的所有子问题里 任何给定的变量在每个子问题中必须取值相同 34 从各个子问题的解得到全局的解 把每个子问题视为一个大