《人工智能第5章约束满足问题.ppt》由会员分享，可在线阅读，更多相关《人工智能第5章约束满足问题.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、13 二月 20231/16信 息 学 院人工智能 一种现代方法第五章第五章 约束满足问题约束满足问题5.1 5.1 约束满足问题约束满足问题 5.2 CSP5.2 CSP问题的回溯搜索问题的回溯搜索5.3 5.3 约束满足问题的局部搜索约束满足问题的局部搜索5.4 5.4 问题的结构问题的结构 13 二月 20232/16信 息 学 院人工智能 一种现代方法约束满足问题约束满足问题 Constraint Satisfaction Problem,CSP约束满足问题：包含一组变量和一组变量间的约束。约束满足问题：包含一组变量和一组变量间的约束。变量集合：变量集合：X1,X2,Xn （变量（变量
2、Xi的值域的值域Di）约束集合：约束集合：C1,C2,Cn 找到所有变量的一个（或多个）赋值，使所有约束都找到所有变量的一个（或多个）赋值，使所有约束都得到满足。得到满足。13 二月 20233/16信 息 学 院人工智能 一种现代方法约束：用于描述对象的性质、相互关系、任务要求、目标约束：用于描述对象的性质、相互关系、任务要求、目标一元谓词一元谓词序关系语言序关系语言形如形如x-yc的方程的方程线性方程和不等式线性方程和不等式布尔组合布尔组合代数和三角方程代数和三角方程约束表示易于理解、编码和实现约束表示易于理解、编码和实现13 二月 20234/16信 息 学 院人工智能 一种现代方法问题
3、的一个状态由对一些或全部变量的赋值定义问题的一个状态由对一些或全部变量的赋值定义例如：例如：Xi=vi,Xj=vj,相容的相容的(合法的合法的)赋值：不违反约束条件赋值：不违反约束条件完全赋值：每个变量都参与完全赋值：每个变量都参与CSP的解是满足所有约束的完全赋值的解是满足所有约束的完全赋值约束满足问题约束满足问题 13 二月 20235/16信 息 学 院人工智能 一种现代方法约束满足问题约束满足问题 变量集合：WA,NT,Q,NSW,V,SA,T 值域:Di=red,green,blue约束：相邻区域颜色不同例如,WA NT,或(WA,NT)组合(red,green),(red,blue
4、),(green,red),(green,blue),(blue,red),(blue,green)13 二月 20236/16信 息 学 院人工智能 一种现代方法e.g.,WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green约束满足问题约束满足问题 13 二月 20237/16信 息 学 院人工智能 一种现代方法约束图：节点约束图：节点-变量，弧变量，弧-约束约束约束满足问题约束满足问题 13 二月 20238/16信 息 学 院人工智能 一种现代方法CSP问题的特点CSP问题的增量形式化：问题的增量形式化：初始状态：空的赋值初始状态：空
5、的赋值；后继函数：可以给任何未赋值的变后继函数：可以给任何未赋值的变量赋一值，且和先前赋值的量赋一值，且和先前赋值的变量不冲突变量不冲突目标测试：检验当前赋值是否完全目标测试：检验当前赋值是否完全路径耗散：每一步耗散为常数路径耗散：每一步耗散为常数完全状态形式化：完全状态形式化：每个状态是一个满足或不满足约每个状态是一个满足或不满足约束条件的完全赋值。束条件的完全赋值。13 二月 20239/16信 息 学 院人工智能 一种现代方法值域值域：有限值域有限值域无限值域：例如工作安排问题无限值域：例如工作安排问题 使用约束语言描述约束使用约束语言描述约束例如：例如：StartJob1+5 Star
6、tJob3约束类型：约束类型：一元约束：只限制单个变量的取值，例如：一元约束：只限制单个变量的取值，例如：SA green二元约束：和两个变量有关，例如：二元约束：和两个变量有关，例如：SA WA 可表示为约束图。可表示为约束图。变量类型：变量类型：离散型离散型连续型：线性规划问题连续型：线性规划问题CSP问题的特点13 二月 202310/16信 息 学 院人工智能 一种现代方法高阶约束：涉及三个或更多变量高阶约束：涉及三个或更多变量例：密码算术例：密码算术 可用超约束图表示。可用超约束图表示。变量：F T U W R O X1 X2 X3值域：0,1,2,3,4,5,6,7,8,9约束：A
7、lldiff(F,T,U,W,R,O)O+O=R+10 X1X1+W+W=U+10 X2X2+T+T=O+10 X3X3=F高阶的、有限值域的约束可简化为一个二元约束集合：高阶的、有限值域的约束可简化为一个二元约束集合：F T，FUCSP问题的特点13 二月 202311/16信 息 学 院人工智能 一种现代方法绝对约束绝对约束:任何违反规则的都排除在解之外任何违反规则的都排除在解之外偏好约束：指出哪些解是更偏好的偏好约束：指出哪些解是更偏好的CSP问题的特点13 二月 202312/16信 息 学 院人工智能 一种现代方法CSPCSP问题的回溯搜索问题的回溯搜索 CSP问题的每一个解必须有一
8、个完全赋值，如问题的每一个解必须有一个完全赋值，如有有n个变量，解的深度为个变量，解的深度为n搜索树则扩展到搜索树则扩展到n.回溯搜索：深度有限搜索，一次为一个变量赋值回溯搜索：深度有限搜索，一次为一个变量赋值 1、为一个新生成的变量选择赋值；、为一个新生成的变量选择赋值；2、比较，合理吗？、比较，合理吗？3、不合理，回溯、不合理，回溯13 二月 202313/16信 息 学 院人工智能 一种现代方法13 二月 202314/16信 息 学 院人工智能 一种现代方法13 二月 202315/16信 息 学 院人工智能 一种现代方法13 二月 202316/16信 息 学 院人工智能 一种现代方
9、法13 二月 202317/16信 息 学 院人工智能 一种现代方法13 二月 202318/16信 息 学 院人工智能 一种现代方法CSP问题的回溯搜索 三个问题：三个问题：1、下一步选哪个变量，按什么顺序尝试它的值；、下一步选哪个变量，按什么顺序尝试它的值；2、当前变量与未赋值变量的关系；、当前变量与未赋值变量的关系；3、如何避免失败，即当一条路径失败时搜索后面的路径如、如何避免失败，即当一条路径失败时搜索后面的路径如何避免这种失败。（弧相容）何避免这种失败。（弧相容）13 二月 202319/16信 息 学 院人工智能 一种现代方法选择合法取值最少的变量选择合法取值最少的变量-最少剩余值
10、最少剩余值(minimum remaining values,MRV)启发式启发式 最受约束变量最受约束变量(Most constrained variable)启发式启发式 失败优先启发式失败优先启发式变量选择和取值顺序变量选择和取值顺序13 二月 202320/16信 息 学 院人工智能 一种现代方法度启发式：选择涉及对其他未赋值变量的约束度启发式：选择涉及对其他未赋值变量的约束数最大的变量来降低未来选择的分支因子。数最大的变量来降低未来选择的分支因子。变量选择和取值顺序变量选择和取值顺序SA的度为的度为5，T的度为的度为013 二月 202321/16信 息 学 院人工智能 一种现代方法
11、最少约束值启发式：优先选择在约束图中排除邻最少约束值启发式：优先选择在约束图中排除邻居变量的可选值最少的。这样能给剩下的变量赋居变量的可选值最少的。这样能给剩下的变量赋值留下最大的灵活性。值留下最大的灵活性。变量选择和取值顺序变量选择和取值顺序13 二月 202322/16信 息 学 院人工智能 一种现代方法1、前向检验、前向检验2、约束传播、约束传播3、处理特殊约束、处理特殊约束4、智能回溯、智能回溯减小搜索空间：减小搜索空间：13 二月 202323/16信 息 学 院人工智能 一种现代方法当变量当变量X被赋值，则对每个与被赋值，则对每个与X相连的未赋值变量相连的未赋值变量Y进行考察，从进
12、行考察，从Y的值域中删去与的值域中删去与X矛盾的值。矛盾的值。前向检验前向检验13 二月 202324/16信 息 学 院人工智能 一种现代方法当变量当变量X被赋值，则对每个与被赋值，则对每个与X相连的未赋值变量相连的未赋值变量Y进行考察，从进行考察，从Y的值域中删去与的值域中删去与X矛盾的值。矛盾的值。前向检验前向检验13 二月 202325/16信 息 学 院人工智能 一种现代方法当变量当变量X被赋值，则对每个与被赋值，则对每个与X相连的未赋值变量相连的未赋值变量Y进行考察，从进行考察，从Y的值域中删去与的值域中删去与X矛盾的值。矛盾的值。前向检验前向检验13 二月 202326/16信
13、息 学 院人工智能 一种现代方法当变量当变量X被赋值，则对每个与被赋值，则对每个与X相连的未赋值变量相连的未赋值变量Y进行考察，从进行考察，从Y的值域中删去与的值域中删去与X矛盾的值。矛盾的值。前向检验前向检验13 二月 202327/16信 息 学 院人工智能 一种现代方法约束传播：将一个变量的约束内容传播到其他变量。约束传播：将一个变量的约束内容传播到其他变量。约束传播约束传播13 二月 202328/16信 息 学 院人工智能 一种现代方法有向弧：约束图中连接两个变量有向弧：约束图中连接两个变量弧相容：如果对于变量弧相容：如果对于变量X的每个取值的每个取值x，变量，变量Y都有某个取值能和
14、都有某个取值能和x保持相容，则连接保持相容，则连接X-Y的的弧是相容的。弧是相容的。弧相容弧相容13 二月 202329/16信 息 学 院人工智能 一种现代方法13 二月 202330/16信 息 学 院人工智能 一种现代方法当当X的值有删除，的值有删除，X的邻居需重新检验相容性。的邻居需重新检验相容性。13 二月 202331/16信 息 学 院人工智能 一种现代方法应用弧相容能够更早检测到前向检验不能发现的矛盾。应用弧相容能够更早检测到前向检验不能发现的矛盾。可在搜索过程中每次赋值后作传播约束，保持弧相容，即从变可在搜索过程中每次赋值后作传播约束，保持弧相容，即从变量值域中删除某值以消除
15、弧不相容。量值域中删除某值以消除弧不相容。13 二月 202332/16信 息 学 院人工智能 一种现代方法Mackworth 1977AC-3：用一队列记录需：用一队列记录需检验相容性的弧检验相容性的弧(Xi,Xj)若若Xi的值要删除，则每的值要删除，则每个指向个指向Xi的弧必须重新的弧必须重新插入队列检验。插入队列检验。13 二月 202333/16信 息 学 院人工智能 一种现代方法K相容：如果对于任何相容：如果对于任何k-1个变量的相容赋值，第个变量的相容赋值，第k个变量总能被个变量总能被赋予一个和前赋予一个和前k-1个变量相容的值，则该个变量相容的值，则该CSP问题是问题是k相容的。
16、相容的。强强K相容：相容：k相容，相容，k-1相容，相容，1相容。相容。N个节点若是强个节点若是强N相容的，则不需要回溯就能求解该相容的，则不需要回溯就能求解该CSP问题。问题。13 二月 202334/16信 息 学 院人工智能 一种现代方法历时回溯：当一个分支搜索失败就倒退回前一历时回溯：当一个分支搜索失败就倒退回前一个变量并尝试另一个值。重新访问的是时间最个变量并尝试另一个值。重新访问的是时间最近的决策点。近的决策点。13 二月 202335/16信 息 学 院人工智能 一种现代方法 倒退回导致失败的变量集合（冲突集）中的倒退回导致失败的变量集合（冲突集）中的一个变量。一个变量。智能回溯
17、：向后看智能回溯：向后看变量变量X的冲突集是通过约束和的冲突集是通过约束和X相连接的相连接的先前已赋值变量的集合。先前已赋值变量的集合。冲突指导的后向跳转：冲突指导的后向跳转：设设Xj是当前变量，其冲突集是当前变量，其冲突集conf(Xj)当当Xj的每个可能取值都失败，后向跳转的每个可能取值都失败，后向跳转到到conf(Xj)中最近一个变量中最近一个变量Xi，并置，并置conf(Xi)conf(Xi)U conf(Xj)-Xi13 二月 202336/16信 息 学 院人工智能 一种现代方法SA失败回溯到失败回溯到Q，Q的冲突集此时为的冲突集此时为NT,NSW,WA再回溯到再回溯到NT，NT的
18、冲突集此时为的冲突集此时为NSW,WA回溯到回溯到NSW 13 二月 202337/16信 息 学 院人工智能 一种现代方法局部搜索算法可求解局部搜索算法可求解CSP问题，其中问题，其中CSP问题问题使用完全状态形式化：初始状态每个变量都赋使用完全状态形式化：初始状态每个变量都赋值，后续函数一次改变一个变量取值。值，后续函数一次改变一个变量取值。最小冲突启发式最小冲突启发式:选择会造成和其他变量的冲突最小的值。选择会造成和其他变量的冲突最小的值。13 二月 202338/16信 息 学 院人工智能 一种现代方法相容性检验的平均次数相容性检验的平均次数13 二月 202339/16信 息 学 院
19、人工智能 一种现代方法CSP 的实现基本过程：基本过程：1、为问题选择适当的状态及操作形式化描述方法、为问题选择适当的状态及操作形式化描述方法;2、从某个初始状态出发每次使用一个操作、从某个初始状态出发每次使用一个操作;3、递增建立操作序列、递增建立操作序列;4、一直到达到目标。、一直到达到目标。13 二月 202340/16信 息 学 院人工智能 一种现代方法问题的结构问题的结构将将CSP问题分解成独立的子问题。问题分解成独立的子问题。约束图中寻找连通域。约束图中寻找连通域。E.g.n=80,d=2280节点节点,10百万节点百万节点/s，需，需4十亿年十亿年 4*220节点，需节点，需0.
20、4s13 二月 202341/16信 息 学 院人工智能 一种现代方法树状结构的树状结构的CSP问题：问题：任何两个变量最多通过一条路径连通。任何两个变量最多通过一条路径连通。树状结构的树状结构的CSP问题可以在变量个数的线性时间内求解问题可以在变量个数的线性时间内求解.13 二月 202342/16信 息 学 院人工智能 一种现代方法树状结构的树状结构的CSP问题可以在变量个数的线性时间内求解：问题可以在变量个数的线性时间内求解：1.任选一节点作为树的根节点，从根节点到叶节点顺序排任选一节点作为树的根节点，从根节点到叶节点顺序排列：每个节点的父节点在它前面。列：每个节点的父节点在它前面。2.
21、j=n to 2：弧弧(Xi,Xj)上应用弧相容算法，删除上应用弧相容算法，删除Xj冲突值冲突值3.j=1 to n：赋给：赋给Xj跟跟Xi的值相容的任何值。的值相容的任何值。X1X6X213 二月 202343/16信 息 学 院人工智能 一种现代方法约束图约束图树树割集调整：对其中某些变量赋值，并从其他变量的值域中割集调整：对其中某些变量赋值，并从其他变量的值域中删除不相容值，使剩下的变量能形成树。删除不相容值，使剩下的变量能形成树。13 二月 202344/16信 息 学 院人工智能 一种现代方法约束图约束图树树原变量至少在一个子问题中出现原变量至少在一个子问题中出现若两个原变量有约束，则应至少若两个原变量有约束，则应至少同时出现在一个子问题。同时出现在一个子问题。若一个变量出现在两个子问题中，若一个变量出现在两个子问题中，它必须出现在连接这些子问题的它必须出现在连接这些子问题的路径上的所有子问题中。路径上的所有子问题中。树分解：树分解：