人工智能第5章约束满足问题

0871-50313012020年4月25日星期六1/[e-mail]信息学院人工智能——一种现代方法第五章约束满足问题5.1约束满足问题5.2CSP问题的回溯搜索5.3约束满足问题的局部搜索5.4问题的结构0871-50313012020年4月25日星期六2/[e-mail]信息学院人工智能——一种现代方法约束满足问题ConstraintSatisfactionProblem,CSP约束满足问题：包含一组变量和一组变量间的约束。变量集合：X1,X2,…,Xn（变量Xi的值域Di）约束集合：C1,C2,…,Cn􃸼􃸼􃸼􃸼􃸼找到所有变量的一个（或多个）赋值，使所有约束都得到满足。0871-50313012020年4月25日星期六3/[e-mail]信息学院人工智能——一种现代方法约束：用于描述对象的性质、相互关系、任务要求、目标…一元谓词序关系语言形如x-yc的方程线性方程和不等式布尔组合代数和三角方程约束表示易于理解、编码和实现0871-50313012020年4月25日星期六4/[e-mail]信息学院人工智能——一种现代方法问题的一个状态由对一些或全部变量的赋值定义例如：{Xi=vi,Xj=vj,…}相容的(合法的)赋值：不违反约束条件完全赋值：每个变量都参与CSP的解是满足所有约束的完全赋值约束满足问题0871-50313012020年4月25日星期六5/[e-mail]信息学院人工智能——一种现代方法约束满足问题变量集合：WA,NT,Q,NSW,V,SA,T值域:Di={red,green,blue}约束：相邻区域颜色不同例如,WA≠NT,或(WA,NT)组合{(red,green),(red,blue),(green,red),(green,blue),(blue,red),(blue,green)}0871-50313012020年4月25日星期六6/[e-mail]信息学院人工智能——一种现代方法e.g.,WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green约束满足问题0871-50313012020年4月25日星期六7/[e-mail]信息学院人工智能——一种现代方法约束图：节点--变量，弧--约束约束满足问题0871-50313012020年4月25日星期六8/[e-mail]信息学院人工智能——一种现代方法CSP问题的特点CSP问题的增量形式化：初始状态：空的赋值{}；后继函数：可以给任何未赋值的变量赋一值，且和先前赋值的变量不冲突目标测试：检验当前赋值是否完全路径耗散：每一步耗散为常数完全状态形式化：每个状态是一个满足或不满足约束条件的完全赋值。0871-50313012020年4月25日星期六9/[e-mail]信息学院人工智能——一种现代方法值域：有限值域无限值域：例如工作安排问题使用约束语言描述约束例如：StartJob1+5≤StartJob3约束类型：一元约束：只限制单个变量的取值，例如：SA≠green二元约束：和两个变量有关，例如：SA≠WA可表示为约束图。变量类型：离散型连续型：线性规划问题CSP问题的特点0871-50313012020年4月25日星期六10/[e-mail]信息学院人工智能——一种现代方法高阶约束：涉及三个或更多变量例：密码算术可用超约束图表示。变量：FTUWROX1X2X3值域：{0,1,2,3,4,5,6,7,8,9}约束：Alldiff(F,T,U,W,R,O)•O+O=R+10·X1••X1+W+W=U+10·X2••X2+T+T=O+10·X3•X3=F高阶的、有限值域的约束可简化为一个二元约束集合：F≠T，F≠U…CSP问题的特点0871-50313012020年4月25日星期六11/[e-mail]信息学院人工智能——一种现代方法绝对约束:任何违反规则的都排除在解之外偏好约束：指出哪些解是更偏好的CSP问题的特点0871-50313012020年4月25日星期六12/[e-mail]信息学院人工智能——一种现代方法CSP问题的回溯搜索CSP问题的每一个解必须有一个完全赋值，如有n个变量，解的深度为n搜索树则扩展到n.回溯搜索：深度有限搜索，一次为一个变量赋值1、为一个新生成的变量选择赋值；2、比较，合理吗？3、不合理，回溯0871-50313012020年4月25日星期六13/[e-mail]信息学院人工智能——一种现代方法0871-50313012020年4月25日星期六14/[e-mail]信息学院人工智能——一种现代方法0871-50313012020年4月25日星期六15/[e-mail]信息学院人工智能——一种现代方法0871-50313012020年4月25日星期六16/[e-mail]信息学院人工智能——一种现代方法0871-50313012020年4月25日星期六17/[e-mail]信息学院人工智能——一种现代方法0871-50313012020年4月25日星期六18/[e-mail]信息学院人工智能——一种现代方法CSP问题的回溯搜索三个问题：1、下一步选哪个变量，按什么顺序尝试它的值；2、当前变量与未赋值变量的关系；3、如何避免失败，即当一条路径失败时搜索后面的路径如何避免这种失败。（弧相容）0871-50313012020年4月25日星期六19/[e-mail]信息学院人工智能——一种现代方法选择合法取值最少的变量--最少剩余值(minimumremainingvalues,MRV)启发式最受约束变量(Mostconstrainedvariable)启发式失败优先启发式变量选择和取值顺序0871-50313012020年4月25日星期六20/[e-mail]信息学院人工智能——一种现代方法度启发式：选择涉及对其他未赋值变量的约束数最大的变量来降低未来选择的分支因子。变量选择和取值顺序SA的度为5，T的度为00871-50313012020年4月25日星期六21/[e-mail]信息学院人工智能——一种现代方法最少约束值启发式：优先选择在约束图中排除邻居变量的可选值最少的。这样能给剩下的变量赋值留下最大的灵活性。变量选择和取值顺序0871-50313012020年4月25日星期六22/[e-mail]信息学院人工智能——一种现代方法1、前向检验2、约束传播3、处理特殊约束4、智能回溯减小搜索空间：0871-50313012020年4月25日星期六23/[e-mail]信息学院人工智能——一种现代方法当变量X被赋值，则对每个与X相连的未赋值变量Y进行考察，从Y的值域中删去与X矛盾的值。前向检验0871-50313012020年4月25日星期六24/[e-mail]信息学院人工智能——一种现代方法当变量X被赋值，则对每个与X相连的未赋值变量Y进行考察，从Y的值域中删去与X矛盾的值。前向检验0871-50313012020年4月25日星期六25/[e-mail]信息学院人工智能——一种现代方法当变量X被赋值，则对每个与X相连的未赋值变量Y进行考察，从Y的值域中删去与X矛盾的值。前向检验0871-50313012020年4月25日星期六26/[e-mail]信息学院人工智能——一种现代方法当变量X被赋值，则对每个与X相连的未赋值变量Y进行考察，从Y的值域中删去与X矛盾的值。前向检验0871-50313012020年4月25日星期六27/[e-mail]信息学院人工智能——一种现代方法约束传播：将一个变量的约束内容传播到其他变量。约束传播0871-50313012020年4月25日星期六28/[e-mail]信息学院人工智能——一种现代方法有向弧：约束图中连接两个变量弧相容：如果对于变量X的每个取值x，变量Y都有某个取值能和x保持相容，则连接X-Y的弧是相容的。弧相容0871-50313012020年4月25日星期六29/[e-mail]信息学院人工智能——一种现代方法0871-50313012020年4月25日星期六30/[e-mail]信息学院人工智能——一种现代方法当X的值有删除，X的邻居需重新检验相容性。0871-50313012020年4月25日星期六31/[e-mail]信息学院人工智能——一种现代方法应用弧相容能够更早检测到前向检验不能发现的矛盾。可在搜索过程中每次赋值后作传播约束，保持弧相容，即从变量值域中删除某值以消除弧不相容。0871-50313012020年4月25日星期六32/[e-mail]信息学院人工智能——一种现代方法Mackworth1977AC-3：用一队列记录需检验相容性的弧(Xi,Xj)若Xi的值要删除，则每个指向Xi的弧必须重新插入队列检验。0871-50313012020年4月25日星期六33/[e-mail]信息学院人工智能——一种现代方法K相容：如果对于任何k-1个变量的相容赋值，第k个变量总能被赋予一个和前k-1个变量相容的值，则该CSP问题是k相容的。强K相容：k相容，k-1相容，…，1相容。N个节点若是强N相容的，则不需要回溯就能求解该CSP问题。0871-50313012020年4月25日星期六34/[e-mail]信息学院人工智能——一种现代方法历时回溯：当一个分支搜索失败就倒退回前一个变量并尝试另一个值。重新访问的是时间最近的决策点。0871-50313012020年4月25日星期六35/[e-mail]信息学院人工智能——一种现代方法倒退回导致失败的变量集合（冲突集）中的一个变量。智能回溯：向后看变量X的冲突集是通过约束和X相连接的先前已赋值变量的集合。冲突指导的后向跳转：设Xj是当前变量，其冲突集conf(Xj)当Xj的每个可能取值都失败，后向跳转到conf(Xj)中最近一个变量Xi，并置conf(Xi)conf(Xi)Uconf(Xj)-{Xi}0871-50313012020年4月25日星期六36/[e-mail]信息学院人工智能——一种现代方法SA失败回溯到Q，Q的冲突集此时为{NT,NSW,WA}再回溯到NT，NT的冲突集此时为{NSW,WA}回溯到NSW0871-50313012020年4月25日星期六37/[e-mail]信息学院人工智能——一种现代方法局部搜索算法可求解CSP问题，其中CSP问题使用完全状态形式化：初始状态每个变量都赋值，后续函数一次改变一个变量取值。最小冲突启发式:选择会造成和其他变量的冲突最小的值。0871-50313012020年4月25日星期六38/[e-mail]信息学院人工智能——一种现代方法相容性检验的平均次数0871-50313012020年4月25日星期六39/[e-mail]信息学院人工智能——一种现代方法CSP的实现基本过程：1、为问题选择适当的状态及操作