资源描述：
《人工智能第5章约束满足问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章约束满足问题5.1约束满足问题5.2CSP问题的回溯搜索5.3约束满足问题的局部搜索5.4问题的结构约束满足问题ConstraintSatisfactionProblem,CSP约束满足问题：包含一组变量和一组变量间的约束。变量集合：X1,X2,…,Xn（变量Xi的值域Di）约束集合：C1,C2,…,Cn?????找到所有变量的一个（或多个）赋值，使所有约束都得到满足。约束：用于描述对象的性质、相互关系、任务要求、目标…一元谓词序关系语言形如x-y>c的方程线性方程和不等式布尔组合代数和三角方程约束表示易于理解、编码和实现问题的一个状态由对一些或全部变量的赋值定义例如
2、：{Xi=vi,Xj=vj,…}相容的(合法的)赋值：不违反约束条件完全赋值：每个变量都参与CSP的解是满足所有约束的完全赋值约束满足问题约束满足问题变量集合：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)}e.g.,WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green约束满足问题约束图
3、：节点--变量，弧--约束约束满足问题CSP问题的特点CSP问题的增量形式化：初始状态：空的赋值{}；后继函数：可以给任何未赋值的变量赋一值，且和先前赋值的变量不冲突目标测试：检验当前赋值是否完全路径耗散：每一步耗散为常数完全状态形式化：每个状态是一个满足或不满足约束条件的完全赋值。值域：有限值域无限值域：例如工作安排问题使用约束语言描述约束例如：StartJob1+5≤StartJob3约束类型：一元约束：只限制单个变量的取值，例如：SA≠green二元约束：和两个变量有关，例如：SA≠WA可表示为约束图。变量类型：离散型连续型：线性规划问题CSP问题的特点高阶约束：涉及
4、三个或更多变量例：密码算术可用超约束图表示。变量：FTUWROX1X2X3值域：{0,1,2,3,4,5,6,7,8,9}约束：Alldiff(F,T,U,W,R,O)O+O=R+10·X1X1+W+W=U+10·X2X2+T+T=O+10·X3X3=F高阶的、有限值域的约束可简化为一个二元约束集合：F≠T，F≠U…CSP问题的特点绝对约束:任何违反规则的都排除在解之外偏好约束：指出哪些解是更偏好的CSP问题的特点CSP问题的回溯搜索CSP问题的每一个解必须有一个完全赋值，如有n个变量，解的深度为n搜索树则扩展到n.回溯搜索：深度有限搜索，一次为一个变量赋值1、为一个新生成
5、的变量选择赋值；2、比较，合理吗？3、不合理，回溯CSP问题的回溯搜索三个问题：1、下一步选哪个变量，按什么顺序尝试它的值；2、当前变量与未赋值变量的关系；3、如何避免失败，即当一条路径失败时搜索后面的路径如何避免这种失败。（弧相容）选择合法取值最少的变量--最少剩余值(minimumremainingvalues,MRV)启发式最受约束变量(Mostconstrainedvariable)启发式失败优先启发式变量选择和取值顺序度启发式：选择涉及对其他未赋值变量的约束数最大的变量来降低未来选择的分支因子。变量选择和取值顺序SA的度为5，T的度为0最少约束值启发式：优先选择在
6、约束图中排除邻居变量的可选值最少的。这样能给剩下的变量赋值留下最大的灵活性。变量选择和取值顺序1、前向检验2、约束传播3、处理特殊约束4、智能回溯减小搜索空间：当变量X被赋值，则对每个与X相连的未赋值变量Y进行考察，从Y的值域中删去与X矛盾的值。前向检验当变量X被赋值，则对每个与X相连的未赋值变量Y进行考察，从Y的值域中删去与X矛盾的值。前向检验当变量X被赋值，则对每个与X相连的未赋值变量Y进行考察，从Y的值域中删去与X矛盾的值。前向检验当变量X被赋值，则对每个与X相连的未赋值变量Y进行考察，从Y的值域中删去与X矛盾的值。前向检验约束传播：将一个变量的约束内容传播到其他变量
7、。约束传播有向弧：约束图中连接两个变量弧相容：如果对于变量X的每个取值x，变量Y都有某个取值能和x保持相容，则连接X->Y的弧是相容的。弧相容当X的值有删除，X的邻居需重新检验相容性。应用弧相容能够更早检测到前向检验不能发现的矛盾。可在搜索过程中每次赋值后作传播约束，保持弧相容，即从变量值域中删除某值以消除弧不相容。Mackworth1977AC-3：用一队列记录需检验相容性的弧(Xi,Xj)若Xi的值要删除，则每个指向Xi的弧必须重新插入队列检验。K相容：如果对于任何k-1个变量的相容赋值，第k个变量总能被赋予一
