第6章 约束满足问题.ppt

《第6章 约束满足问题.ppt》由会员分享，可在线阅读，更多相关《第6章 约束满足问题.ppt（66页珍藏版）》请在优知文库上搜索。

1、第第6章章 约束满足问题约束满足问题第第部分部分 问题求解问题求解本章内容本章内容 6.1 约束满足问题约束满足问题 6.2 约束传播：约束传播：CSP中的推理中的推理 6.3 CSP的回溯搜索的回溯搜索 6.4 CSP的局部搜索的局部搜索 6.5 问题的结构问题的结构例例1、澳大利亚地图染色问题、澳大利亚地图染色问题(1)澳大利亚地图染色问题：用澳大利亚地图染色问题：用红红绿绿蓝蓝3色标出各省，色标出各省，相邻者颜色不同。相邻者颜色不同。塔斯马尼亚西澳大利亚北领地南澳大利亚昆士兰新南威尔士维多利亚 对应于澳大利亚地图的对应于澳大利亚地图的约束图约束图，相互关联的节点，相互关联的节点用边连接。

2、用边连接。WANTSANSWQVT 西澳大利亚西澳大利亚 WA WA 北领地北领地 NT NT 南澳大利亚南澳大利亚 SA SA 昆士兰昆士兰 Q Q 新南威尔士新南威尔士 NSW NSW 维多利亚维多利亚 V V 塔斯马尼亚塔斯马尼亚 T T例例1、澳大利亚地图染色问题、澳大利亚地图染色问题(2)一组满足约束的完全赋值：一组满足约束的完全赋值：WA=R,NT=G,Q=R,SA=B,NSW=G,V=R,T=R 约束满足问题的定义约束满足问题的定义 约束满足问题约束满足问题（Constraint Satisfying Problem,CSP）：）：由一个变量集合由一个变量集合X1Xn和一个约束集

3、合和一个约束集合C1Cm定义；定义；每个变量都有一个非空可能值域每个变量都有一个非空可能值域D Di i；每个约束指定了包含若干变量的一个子集内各变量的赋值每个约束指定了包含若干变量的一个子集内各变量的赋值范围。范围。例如：例如：地图染色问题，地图染色问题，N-N-皇后问题。皇后问题。CSP的一个状态的一个状态：对一些或全部变量的赋值：对一些或全部变量的赋值 Xi=vi,Xj=vj,。CSP问题的解问题的解 一个不违反任何约束的对变量的赋值称为一个不违反任何约束的对变量的赋值称为相容赋值相容赋值或合法赋值或合法赋值。对每个变量都进行赋值称为对每个变量都进行赋值称为完全赋值完全赋值。一个一个（一

4、组）（一组）对变量的赋值，若既是相容赋值又是对变量的赋值，若既是相容赋值又是完全赋值，则这个（组）赋值是完全赋值，则这个（组）赋值是CSP问题的解问题的解。某些某些CSP问题要求问题的解能使目标函数最大问题要求问题的解能使目标函数最大化化约束优化约束优化。CSP问题常常可以可视化，表示为问题常常可以可视化，表示为约束图约束图，更直观，更直观地显示问题，帮助思考问题的答案。地显示问题，帮助思考问题的答案。CSP问题的分类问题的分类 根据变量的类型划分：根据变量的类型划分：离散值域离散值域和和连续值域连续值域。变量变量离散值域离散值域 有限值域有限值域，如地图染色问题，八皇后问题。，如地图染色问题

5、，八皇后问题。无限值域无限值域，如整数集合或者字符串集合。，如整数集合或者字符串集合。例如，对于作业规划问题，无法枚举所有可能取值，要例如，对于作业规划问题，无法枚举所有可能取值，要使用使用约束语言约束语言(线性约束线性约束/非线性约束非线性约束)描述，如描述，如StartJobStartJob1 1+5StratJob+5StratJob3 3。有限值域有限值域CSP问题包括问题包括布尔布尔CSP问题，它的变量的取值可以是问题，它的变量的取值可以是true或或false。布尔布尔CSP包括一些包括一些典型典型NP完全问题完全问题，如，如3-SAT问题（命题问题（命题逻辑语句的可满足性问题），

6、逻辑语句的可满足性问题），最坏情况下最坏情况下不能指望低于指不能指望低于指数级时间复杂性解决该问题。数级时间复杂性解决该问题。CSP问题的分类问题的分类 变量变量连续值域连续值域 最著名的连续值域最著名的连续值域CSPCSP是是线性规划线性规划问题。问题。线性规划线性规划中的约束必须是构成一个凸多边形的中的约束必须是构成一个凸多边形的一组线性不等式。一组线性不等式。线性规划问题可以在变量个数的多项式时间内线性规划问题可以在变量个数的多项式时间内求解。求解。CSP问题的分类问题的分类 根据约束的类型划分：根据约束的类型划分：线性线性或或非线性约束非线性约束。一元一元或或多元约束多元约束。一元约束

7、：只限制一个变量的取值一元约束：只限制一个变量的取值 二元约束与二元约束与2 2个变量相关个变量相关 高阶约束：涉及高阶约束：涉及3 3个或更多变量。个或更多变量。通过引入辅助变量，转为二元约束。通过引入辅助变量，转为二元约束。绝对绝对约束约束 vs 偏好约束偏好约束。我们仅讨论绝对约束。我们仅讨论绝对约束。高阶约束的例子高阶约束的例子 算式算式T W O+T W O F O U R例例2、密码算术问题。、密码算术问题。每个字母表示不同的数字。目标是找到每个字母表示不同的数字。目标是找到能使如下加法式子成立的数字，附加的约束条件是最前面的数能使如下加法式子成立的数字，附加的约束条件是最前面的数

8、字不能为字不能为0。高阶约束的例子高阶约束的例子 算式算式T W O+T W O F O U R F=1。如不考虑如不考虑O/U有进位：有进位：R/U/O均为偶数，均为偶数，R=4,6,8，O=2?,3?,4!。R=8/O=4，则，则T=7（由（由O/R/U/W共同限制）。共同限制）。T=7，则，则U=6/W=3，由此得到一组解，由此得到一组解1468|734。考虑考虑O/U有进位：有进位：R=0,2,4,6,8，O=5,6,7,8,9。若若R=0/O=5(有进位有进位)，则，则T=7/W=6/U=3，由此得，由此得到一组解到一组解=1530|765。四列算式约束：四列算式约束：O+O=R+1

9、0*X1 X1+W+W=U+10*X2 X2+T+T=O+10*X3 X3=F 对应的对应的约束超图约束超图如右图。如右图。六个变量互不相等约六个变量互不相等约束可化为两两不等约束可化为两两不等约束额的二元约束。束额的二元约束。高阶约束的例子高阶约束的例子各算式约束FTWUORX3X1X2约束：互不相等，两两不等每个约束在图中用方块表示，每个约束在图中用方块表示，连接至它所约束的变量。连接至它所约束的变量。CSP问题求解的复杂度问题求解的复杂度 CSP问题的求解目标是找到问题的求解目标是找到相容的完全赋值相容的完全赋值，最，最朴素的想法是依次取变量的赋值组合并检查其是朴素的想法是依次取变量的赋

10、值组合并检查其是否满足约束条件。否满足约束条件。若若CSP问题的任何一个变量的最大值域为问题的任何一个变量的最大值域为d，那，那么可能的完全赋值数量为么可能的完全赋值数量为O(dn)。指数级指数级计算量。计算量。本章内容本章内容 6.1 约束满足问题约束满足问题 6.2 约束传播：约束传播：CSP中的推理中的推理 6.3 CSP的回溯搜索的回溯搜索 6.4 CSP的局部搜索的局部搜索 6.5 问题的结构问题的结构约束传播约束传播 约束传播：约束传播：使用约束来使用约束来减小一个变量的合法取值范减小一个变量的合法取值范围围，从而影响到，从而影响到与此变量有约束关系的另一变量与此变量有约束关系的另

11、一变量的的取值。取值。弧相容：弧相容：依次检验约束图中各个相关节点对依次检验约束图中各个相关节点对。注意，。注意，弧是有向弧。弧是有向弧。例如，给定例如，给定SA/NSW当前值域，如果对于当前值域，如果对于SA的每个取值的每个取值x，NSW都有某个都有某个y和和x相容，则相容，则SA到到NSW的弧是相容的；的弧是相容的；反过来是反过来是NSW到到SA的弧相容。的弧相容。WANTSANSWQVT弧相容弧相容 在地图染色约束的赋值过程中：第在地图染色约束的赋值过程中：第4行行SA=blue，NSW=red,blue，则，则SA的取值有一个的取值有一个NSW=red与之相容；反过来与之相容；反过来N

12、SW=blue，则，则SA为空值，即不相容，为空值，即不相容，通过删除通过删除NSW值域中值域中的的blue可使其相容。可使其相容。弧相容检测也能较早发现矛盾，如第弧相容检测也能较早发现矛盾，如第4行行SA和和NT值域均为值域均为blue，则必须删去，则必须删去SA=blue，其值域变为空。，其值域变为空。用弧相容能够更早地检测到矛盾。用弧相容能够更早地检测到矛盾。WANTQNSWVSARGBRGBRGBRGBRGBRGB GBRGBRGB RGB GB B R BRGB BWA=redWA=redQ=greenQ=greenV=blueV=blue蓝色字体为赋蓝色字体为赋值结果值结果弧相容算

13、法思想弧相容算法思想1.用队列记录需要检验不相容的弧。用队列记录需要检验不相容的弧。2.每条弧每条弧Xi,Xj依次从队列中删除并被检验。依次从队列中删除并被检验。如果如果Xi值域中的任何一个值需要删除，则每个值域中的任何一个值需要删除，则每个指指向向Xi的弧的弧Xk,Xi都必须重新插入队列进行检验。都必须重新插入队列进行检验。因为指向这个变量的弧可能产生新的不相容（原因为指向这个变量的弧可能产生新的不相容（原来可能就是因为这个值产生了它们之间的相容）。来可能就是因为这个值产生了它们之间的相容）。时间复杂度：时间复杂度：二元二元CSP约束至多有约束至多有O(n2)条弧；条弧；每每条弧至多插入队列

14、条弧至多插入队列d次（次（d个取值），检验一条弧为个取值），检验一条弧为O(d2)，因此算法的最坏情况下为，因此算法的最坏情况下为O(n2d3)。弧相容算法弧相容算法AC-31.function AC-3(csp)returns the CSP,possibly with reduced domains2.inputs:csp,a binary CSP with variables X1,X2,.,Xn3.local variables:queue,a queue of arcs,initially all the arcs in csp4.while queue is not empty d

15、o5.(Xi,Xj)Remove-First(queue)6.if RM-Inconsistent-Values(Xi,Xj)then7.for each Xk in NeighborsXi do8.add(Xk,Xi)to queue1.function RM-Inconsistent-Values(Xi,Xj)returns true iff remove a value1.removed false2.for each x in DomainXi do3.if no value y in DomainXj allows(x,y)to satisfy constraint(Xi,Xj)4.

16、then delete x from DomainXi;removed true5.return removed弧相容的使用弧相容的使用 弧相容检验可以用作开始弧相容检验可以用作开始搜索之前搜索之前的的预处理预处理。弧相容检验也可以在弧相容检验也可以在搜索过程中搜索过程中每次赋值后用作一个每次赋值后用作一个约束传播步骤约束传播步骤。即反复检测某个变量值域中的不相容弧，进行值即反复检测某个变量值域中的不相容弧，进行值删除，直到不再有矛盾。删除，直到不再有矛盾。称为称为保持弧相容（保持弧相容（MAC）。从弧相容推广到从弧相容推广到k相容相容 如果对于如果对于任何任何k1个变量的相容赋值个变量的相容赋值，第，第k个变量总个变量总能被赋予一个与前能被赋予一个与前k1个变量相容的值，那么该个变量相容的值，那么该CSP问题是问题是k相容相容的。的。1相容是指每个单独的变量自己是不矛盾的，也称为相容是指每个单独的变量自己是不矛盾的，也称为节点相容节点相容。弧相容弧相容2相容。相容。3相容是指任何一对相邻的变量总可以扩展到第三个相容是指任何一对相邻的变量总可以扩展到第三个邻居变量，也称为邻居变量，也称