约束满足问题解析.pptx

《约束满足问题解析.pptx》由会员分享，可在线阅读，更多相关《约束满足问题解析.pptx（80页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、概要概要CSP定义标准搜索方法改进回溯向前查看约束传播启发式算法变量排序值排序CSP实例树结构CSP解CSP的局域搜索第1页/共80页CSP：定义：定义第2页/共80页第3页/共80页第4页/共80页范例：图形着色范例：图形着色考虑一个图形中的N个结点。把变量V1,VN的值赋给N个结点。值取自R,G,B约束：如果i与j之间有边，则Vi与Vj必不同。第5页/共80页范例：图形着色范例：图形着色第6页/共80页CSP定义定义CSP=V,D,C变量：V=V1,VN例如：图中结点的值域：每个变量能取的d个值的集例如：D=R,G,B约束：C=C1,CK每个约束由一组变量与一列该组变量允许取的值组成例如：

2、(V2,V3),(R,B),(R,G),(B,R),(B,G),(G,R),(G,B)通常隐式地定义约束，即，定义一个函数来测试一组变量是否满足该约束例如：对每条边(i,j)，有ViVj第7页/共80页CSP定义定义CSP的解：每个变量有一个满足所有相关约束的值特点：状态的分解表示：一组变量及其值利用状态的结构和通用启发方式通过确定违反约束的变量与值组合可取消大部分搜索空间第8页/共80页二元二元CSP如果变量V与V出现在一个约束中，则它们是有联系的。V近邻=与V有联系的变量。V域，记为D(V)，为变量V可取值的集。Di=D(Vi)二元CSP问题的约束图：结点是变量连线代表约束与图形着色问题相

3、同第9页/共80页实例：实例：N个皇后个皇后变量：Qi域：Di=1,2,3,4约束Qi Qj，即不能在同一行|Qi Qj|i j|，即不能在对角上(Q1,Q2)的合法值是(1,3)，(1,4)，(2,4)，(3,1)，(4,1)，(4,2)第10页/共80页实例：密算（实例：密算（Cryptarithmetic）S E N D M O R EM O N E Y变量：D,E,M,N,O,R,S,Y域：0,1,2,3,4,5,6,7,8,9约束M 0，S 0，单元约束Y=D E 或Y=D E 10D E，D M，D N 等第11页/共80页更多实例更多实例调度产品设计资产分配电路设计受约束机器人的

4、规划第12页/共80页CSP：标准搜索：标准搜索第13页/共80页搜索空间搜索空间状态：给出k个变量赋值，而第k+1,N个变量未赋值。后续态：通过给第k+1个变量赋值，而保持其它变量不变，来获得一个态的后续态。始态：(V1=?,V2=?,V3=?,V4=?,V5=?,V6=?)终态：所有变量已赋值，且约束也已满足。无任何关于转换代价的概念。即，只想找到一个解，而不担心是怎样找到的。样本状态：(V1=G,V2=B,V3=?,V4=?,V5=?,V6=?)第14页/共80页V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3

5、V4V5V6?坏值值次序：(B,R,G)第15页/共80页深度优先搜索（深度优先搜索（DFS）采用递归方式：对D中每个可能值：为后续态中的下个未赋值变量赋该值赋值后，评估当前态的后续态一旦找到解，就停止V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3V4V5V6?值次序：(B,R,G)第16页/共80页DFS改进：只评估那些赋值，它们不违反任何与目前已赋值相关的约束。不搜索那些明显不可能通往解的分枝。预测合法的赋值。控制变量与值的次序。第17页/共80页CSP：改进：改进第18页/共80页V1V2V3V4V5V6B?

6、V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V5V6BRRBG?值次序：(B,R,G)第19页/共80页回溯回溯DFSV1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V5V6BRRBG?值次序：(B,R,G)不考虑该树枝，因为V2=B与目前已赋值相关的约束不符。回溯到前一个状态，因为不能给V6赋合法的值。第20页/共80页回溯回溯DFS对D中每个可能值x：如果将x赋给下个未赋值变量Vk+1

7、后，不违反与k个已赋值变量相关的任何约束：给Vk+1赋x。赋值后，评估当前态的后续态。如果找不到合法赋值，则回溯到前一个状态。一旦找到解，就停止。第21页/共80页回溯回溯DFS评论评论额外的计算：每步都需评估与当前候选赋值(变量=值)相关的约束。用预测来改进不知情搜索：一个变量的赋值对所有其它变量有什么影响？下一个应赋值的变量是谁？并且应遵循什么次序来评估值？当一条路径失败，怎样避免犯同样错误？第22页/共80页向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6R?B?G?值次序：(R,B,G)第23页/共80页向前查看向前查看对未赋值的变量，

8、跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6ROX?XX?B?G?第24页/共80页向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6RO?XX?BOX?X?G?第25页/共80页向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6ROOXXXBO?X?G?第26页/共80页向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6ROOXXBOOXXG?第27页/共80页向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，

9、回溯。V1V2V3V4V5V6ROOXBOOXGOX无合法值能赋给V6，因此需要回溯第28页/共80页约束传播（约束传播（CP）向前查看不检查所有不一致性，因为它只能查看那些与该当前赋值变量相关的约束。能查看得更远些吗？V1V2V3V4V5V6ROOXXBOOXXG?在该处已可看出，此路径不通向解，因为域中剩余值在赋给V5与V6后不能保持一致性。第29页/共80页约束传播约束传播V=在搜索的当前层次，需赋值的变量。将D(V)中的一个值赋给V对与V相连的每个变量V：去掉D(V)中与已赋值变量不一致的值对与V 相连的每个变量V”：去掉D(V”)中不再可能的候选值对与V”相连的每个变量：直到不再有能

10、被去掉的值为止注：清理D(V)是属于已有的向前查看清理D(V”)则是属于新的约束传播第30页/共80页解图形着色问题的解图形着色问题的CPPropagate(node,color)1.从node的所有近邻的值域中去掉color2.对每个近邻N:if 第1步后，D(N)中只剩一种颜色，即D(N)=c：Propagate(N,c)第31页/共80页V1V2V3V4V5V6ROX?XX?B?G?在传播(V1,R)后：第32页/共80页V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在传播(V2,B)后：传播次序：23546365354第33页/共80页注：在设置V2后，无需更多搜索，只需一

11、步CP就直接得到一个解。一些问题甚至可无需任何搜索，直接由CP来解。V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在传播(V2,B)后：第34页/共80页更一般的更一般的CP：边一致性：边一致性A=活跃边(Vi,Vj)的队列当A不空时，重复执行：(Vi,Vj)A的下一个组元对D(Vi)中每个x：如果D(Vj)中无y能使(x,y)满足Vi,与Vj间的约束，则从D(Vi)中去掉x如果D(Vi)有改变：添加所有(Vk,Vi)对到A中，其中Vk(kj)是Vi的一个近邻第35页/共80页更一般的更一般的CP：k一致性一致性查看含有k个变量组之间的一致性，而不是变量偶对（边）之间一致性。权衡：

12、CP时间随k增加而迅速增加搜索时间随k增加可能会下降，但可能不会像上面那样快完全约束传播，时间开销是问题尺寸的指数第36页/共80页CSP：启发方式：启发方式第37页/共80页变量与值的启发式算法变量与值的启发式算法目前，是以一个固定次序来选择下一个变量和下一个值。问题：有更好的方法来选择下一个变量吗？有更好的方法来选择下一个赋给当前变量的值吗？第38页/共80页CSP启发式算法：变量排序启发式算法：变量排序1V1V2V3V4V5V6V7R?第39页/共80页CSP启发式算法：变量排序启发式算法：变量排序1最多约束变量（MCV）选择一个贡献最多约束数的变量，会对其它变量有极大的影响。因此，有希

13、望修剪掉大部分搜索。这要求：在约束图形中找到与最多变量相连接的变量。V1V2V3V4V5V6V7R?变量V5影响5个变量。变量V2、V3或V4只影响较少的变量。第40页/共80页CSP启发式算法：变量排序启发式算法：变量排序2V1V2V3V4V5V6V7ROXXX?OBO?X?G?第41页/共80页CSP启发式算法：变量排序启发式算法：变量排序2最少余下值（MRV）选择一个候选值最少的变量，由此，极可能导致一个早期失败（失败优先启发方式）。V1V2V3V4V5V6V7ROXXX?OBO?X?G?变量V5是最受约束的变量，并且最可能用来剪枝搜索树。第42页/共80页CSP启发式算法：值排序启发式

14、算法：值排序V1V2V3V4V5V6GR?四种颜色：D=R,G,B,Y第43页/共80页CSP启发式算法：值排序启发式算法：值排序最少约束值（LCV）选择使相邻变量可用值减少最少的值优先选用最可能的值（也即为随后的变量赋值提供最大灵活性）来获得一个解V1V2V3V4V5V6GR?四种颜色：D=R,G,B,Y要给V3赋哪个值？第44页/共80页CP实例：白描解释实例：白描解释凹边凹边凸边凸边?第45页/共80页假设假设无阴影公共面之间无边一般观察点只考虑三面顶点特殊观察点一般观察点不允许的边第46页/共80页3种可能的边标记种可能的边标记+：凸边：凹边：边界按规定，当沿着箭头方向看时，面在右侧。

15、第47页/共80页4种可能的交点类型种可能的交点类型TVYW第48页/共80页1+2-3-4-5-第49页/共80页存在34342=208种可能的边标记与交点类型的组合。例如，在一个Y交点处，有43种可能的边标记组合。但仅有5种实际上可能的组合。1+2-3-4-5-第50页/共80页第51页/共80页CSP形式形式域D=18种交点构形的字典。约束：连接两交点的线必须是,+,中的某单一标记。问题：把值赋给所有交点，从而所有边都被标记。用约束传播来求解：Waltz标记算法。第52页/共80页+-+-+-+VYTW仅有18种可能的交点构形Huffman-Clowes交点字典第53页/共80页+-+-

16、+BA+-+CCBDA+-D(B,A)第54页/共80页+-+-+BA+-+CCBDA+-D(C,B)第55页/共80页+-+-+BA+-+CCBDA+-D(D,C)第56页/共80页+-+-+BA+-+CCBDA+-D(A,D)第57页/共80页+-+-+BA+-+CCBDA+-D(B,A)第58页/共80页+-+-+BA+-+CCBDA+-D+-第59页/共80页标记标记扩展：处理阴影与切点接触。有10种交点类型，且大得多的合法构形。关键点：随边的增加，计算呈线性增长。第60页/共80页例子：调度例子：调度需完成一组N项任务J1,JN。每项任务j是由顺序执行的一组Lj项操作Oj1,OjLj

17、组成。每项操作Oji有一个已知的时间段Tji。操作可能需要从一项有M个资源R1,RM的库中使用资源。一个资源不能同时被两项操作使用。所有的任务必须在时间t之前完成。问题：用离散时间0,T来安排每项操作的起始时间Sji。第61页/共80页4项任务4个资源10项操作第62页/共80页优先约束：S11+T11S12S12+T12S13.交付约束：S13+T13tS22+T22tS33+T33t.第63页/共80页容量约束：S11+T11S21或者S21+T21S11操作(1,1)和(2,1)享用同一资源R1。因此，要么(1,1)在(2,1)之前全部完成，要么(2,1)在(1,1)之前完成。第64页/

18、共80页一般的一般的CSP解解重复直到所有变量已被赋值为止：采用一个一致性实施程序向前查看约束传播if 无解：回溯到前一个变量else选择下一个需赋值的变量利用变量排序启发选择一个值赋给该变量利用值排序启发第65页/共80页CSP：树结构：树结构CSP第66页/共80页重要特例：约束树重要特例：约束树约束图形是一棵树：两变量由一条路径相连。能用变量数的线性时间来求解。第67页/共80页V2V1V4V5V7V3V6V8将变量排序，使得在序列中一个结点的父结点总出现在该结点之前如果父域中所有的值与所有子域中的值相一致，则很容易从树根开始来选择一致性的值。根第68页/共80页约束树算法约束树算法1.

19、由叶向上到根：由叶开始，对每个变量Vi：Vj=parent(Vi)去掉D(Vj)中所有与D(Vi)不一致的值x2.从根向下到叶：给根赋一个值对每个变量Vi：选择D(Vi)中一个值x，它应与赋给parent(Vi)的值是一致的注：由叶向上到根，只访问每个变量一次：N为去掉不一致值，在最坏场合，需查看每对赋值：d2总时间复杂性：O(Nd2)第69页/共80页类树类树一旦为V6选择一个值后，约束图形就变成约束树。不知道要选那个值。因此，尝试所有可能值。第70页/共80页更一般场合更一般场合G第71页/共80页去掉由p个变量组成的连接群G，从而把图形转换成一个可有效求解的树问题。G称为循环割集（cyc

20、le cutset）不知道怎样为G中变量赋值：对于每次可能的为G中变量的一致性赋值：将树算法应用于其余变量总体算法称为割集调节（cutset conditioning）G第72页/共80页去掉由p个变量组成的连接群G，从而把图形转换成一个可有效求解的树问题。G称为循环割集不知道怎样为G中变量赋值：对于每次可能的为G中变量的一致性赋值：将树算法应用于其余变量总体算法称为割集调节（cutset conditioning）注：为实现一次为G中变量的一致性赋值，在最坏场合下，需查看G中所有可能赋值：dp树算法：(N-p)d2总时间复杂性：O(N-p)dp+2)不幸的是，不可能用多项式时间来找到p的极小

21、值。第73页/共80页CSP：解：解CSP的局域搜索的局域搜索第74页/共80页解解CSP的局域搜索技术的局域搜索技术这些问题能够表达为CSP已经用局域搜索方法（爬山法、模拟退火法、禁忌算法、遗传算法）来求解过这些问题局域搜索方法什么时候适用？局域搜索解对一些问题很有效除CSP外，还需优化代价函数在线更新CSP解SAT：ABCACDBDECDEACEN个皇后个皇后第75页/共80页解解CSP的局域搜索的局域搜索状态=给所有变量的赋值移动=改变一个变量评估=变量间的冲突（不满足约束）数V1V2V3V4V5V6abcdefV1V2V3V4V5V6abcdef第76页/共80页一般局域搜索：最少冲突

22、算法一般局域搜索：最少冲突算法从一次给全部变量的赋值开始重复直到找到一个解或着到达迭代极限为止：在冲突变量中随机选择一个变量Vi置Vi等于违反约束最少的值注：在很多问题的求解中，远比CSP搜索来得有效所有爬山类方法都适用一般形式与WALKSAT相似第77页/共80页N个皇后(140106回溯DFS+MRV13.5106向前查看40106向前查看+MRV817,000最少冲突4,000MRV启发总是很有效。局域搜索是令人吃惊地有效。能有效地解N=107时N个皇后问题。为什么能容易解决这样的问题？第78页/共80页总结总结定义标准搜索改进回溯向前查看约束传播启发式算法变量排序值排序实例树结构CSP解CSP的局域搜索第79页/共80页感谢您的观看。第80页/共80页