6约束满足问题解析.pptx

约束满足问题（约束满足问题（CSP）概要概要CSP定义标准搜索方法改进回溯向前查看约束传播启发式算法变量排序值排序CSP实例树结构CSP解CSP的局域搜索CSP：定义：定义范例：图形着色范例：图形着色考虑一个图形中的N个结点。把变量V1,VN的值赋给N个结点。值取自R,G,B约束：如果i与j之间有边，则Vi与Vj必不同。范例：图形着色范例：图形着色CSP定义定义CSP=V,D,C变量：V=V1,VN例如：图中结点的值域：每个变量能取的d个值的集例如：D=R,G,B约束：C=C1,CK每个约束由一组变量与一列该组变量允许取的值组成例如：(V2,V3),(R,B),(R,G),(B,R),(B,G),(G,R),(G,B)通常隐式地定义约束，即，定义一个函数来测试一组变量是否满足该约束例如：对每条边(i,j)，有ViVjCSP定义定义CSP的解：每个变量有一个满足所有相关约束的值特点：状态的分解表示：一组变量及其值利用状态的结构和通用启发方式通过确定违反约束的变量与值组合可取消大部分搜索空间二元二元CSP如果变量V与V出现在一个约束中，则它们是有联系的。V近邻=与V有联系的变量。V域，记为D(V)，为变量V可取值的集。Di=D(Vi)二元CSP问题的约束图：结点是变量连线代表约束与图形着色问题相同实例：实例：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)实例：密算（实例：密算（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 等更多实例更多实例调度产品设计资产分配电路设计受约束机器人的规划CSP：标准搜索：标准搜索搜索空间搜索空间状态：给出k个变量赋值，而第k+1,N个变量未赋值。后续态：通过给第k+1个变量赋值，而保持其它变量不变，来获得一个态的后续态。始态：(V1=?,V2=?,V3=?,V4=?,V5=?,V6=?)终态：所有变量已赋值，且约束也已满足。无任何关于转换代价的概念。即，只想找到一个解，而不担心是怎样找到的。样本状态：(V1=G,V2=B,V3=?,V4=?,V5=?,V6=?)V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3V4V5V6?坏值值次序：(B,R,G)深度优先搜索（深度优先搜索（DFS）采用递归方式：对D中每个可能值：为后续态中的下个未赋值变量赋该值赋值后，评估当前态的后续态一旦找到解，就停止V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3V4V5V6?值次序：(B,R,G)DFS改进：只评估那些赋值，它们不违反任何与目前已赋值相关的约束。不搜索那些明显不可能通往解的分枝。预测合法的赋值。控制变量与值的次序。CSP：改进：改进V1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V5V6BRRBG?值次序：(B,R,G)回溯回溯DFSV1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V5V6BRRBG?值次序：(B,R,G)不考虑该树枝，因为V2=B与目前已赋值相关的约束不符。回溯到前一个状态，因为不能给V6赋合法的值。回溯回溯DFS对D中每个可能值x：如果将x赋给下个未赋值变量Vk+1后，不违反与k个已赋值变量相关的任何约束：给Vk+1赋x。赋值后，评估当前态的后续态。如果找不到合法赋值，则回溯到前一个状态。一旦找到解，就停止。回溯回溯DFS评论评论额外的计算：每步都需评估与当前候选赋值(变量=值)相关的约束。用预测来改进不知情搜索：一个变量的赋值对所有其它变量有什么影响？下一个应赋值的变量是谁？并且应遵循什么次序来评估值？当一条路径失败，怎样避免犯同样错误？向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6R?B?G?值次序：(R,B,G)向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6ROX?XX?B?G?向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6RO?XX?BOX?X?G?向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6ROOXXXBO?X?G?向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6ROOXXBOOXXG?向前查看向前查看对未赋值的变量，跟踪余下的合法值。当变量无合法值时，回溯。V1V2V3V4V5V6ROOXBOOXGOX无合法值能赋给V6，因此需要回溯约束传播（约束传播（CP）向前查看不检查所有不一致性，因为它只能查看那些与该当前赋值变量相关的约束。能查看得更远些吗？V1V2V3V4V5V6ROOXXBOOXXG?在该处已可看出，此路径不通向解，因为域中剩余值在赋给V5与V6后不能保持一致性。约束传播约束传播V=在搜索的当前层次，需赋值的变量。将D(V)中的一个值赋给V对与V相连的每个变量V：去掉D(V)中与已赋值变量不一致的值对与V 相连的每个变量V”：去掉D(V”)中不再可能的候选值对与V”相连的每个变量：直到不再有能被去掉的值为止注：清理D(V)是属于已有的向前查看清理D(V”)则是属于新的约束传播解图形着色问题的解图形着色问题的CPPropagate(node,color)1.从node的所有近邻的值域中去掉color2.对每个近邻N:if 第1步后，D(N)中只剩一种颜色，即D(N)=c：Propagate(N,c)V1V2V3V4V5V6ROX?XX?B?G?在传播(V1,R)后：V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在传播(V2,B)后：传播次序：23546365354注：在设置V2后，无需更多搜索，只需一步CP就直接得到一个解。一些问题甚至可无需任何搜索，直接由CP来解。V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在传播(V2,B)后：更一般的更一般的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的一个近邻更一般的更一般的CP：k一致性一致性查看含有k个变量组之间的一致性，而不是变量偶对（边）之间一致性。权衡：CP时间随k增加而迅速增加搜索时间随k增加可能会下降，但可能不会像上面那样快完全约束传播，时间开销是问题尺寸的指数CSP：启发方式：启发方式变量与值的启发式算法变量与值的启发式算法目前，是以一个固定次序来选择下一个变量和下一个值。问题：有更好的方法来选择下一个变量吗？有更好的方法来选择下一个赋给当前变量的值吗？CSP启发式算法：变量排序启发式算法：变量排序1V1V2V3V4V5V6V7R?CSP启发式算法：变量排序启发式算法：变量排序1最多约束变量（MCV）选择一个贡献最多约束数的变量，会对其它变量有极大的影响。因此，有希望修剪掉大部分搜索。这要求：在约束图形中找到与最多变量相连接的变量。V1V2V3V4V5V6V7R?变量V5影响5个变量。变量V2、V3或V4只影响较少的变量。CSP启发式算法：变量排序启发式算法：变量排序2V1V2V3V4V5V6V7ROXXX?OBO?X?G?CSP启发式算法：变量排序启发式算法：变量排序2最少余下值（MRV）选择一个候选值最少的变量，由此，极可能导致一个早期失败（失败优先启发方式）。V1V2V3V4V5V6V7ROXXX?OBO?X?G?变量V5是最受约束的变量，并且最可能用来剪枝搜索树。CSP启发式算法：值排序启发式算法：值排序V1V2V3V4V5V6GR?四种颜色：D=R,G,B,YCSP启发式算法：值排序启发式算法：值排序最少约束值（LCV）选择使相邻变量可用值减少最少的值优先选用最可能的值（也即为随后的变量赋值提供最大灵活性）来获得一个解V1V2V3V4V5V6GR?四种颜色：D=R,G,B,Y要给V3赋哪个值？CP实例：白描解释实例：白描解释凹边凹边凸边凸边?假设假设无阴影公共面之间无边一般观察点只考虑三面顶点特殊观察点一般观察点不允许的边3种可能的边标记种可能的边标记+：凸边：凹边：边界按规定，当沿着箭头方向看时，面在右侧。4种可能的交点类型种可能的交点类型TVYW1+2-3-4-5-存在34342=208种可能的边标记与交点类型的组合。例如，在一个Y交点处，有43种可能的边标记组合。但仅有5种实际上可能的组合。1+2-3-4-5-CSP形式形式域D=18种交点构形的字典。约束：连接两交点的线必须是,+,中的某单一标记。问题：把值赋给所有交点，从而所有边都被标记。用约束传播来求解：Waltz标记算法。+-+-+-+VYTW仅有18种可能的交点构形Huffman-Clowes交点字典+-+-+BA+-+CCBDA+-D(B,A)+-+-+BA+-+CCBDA+-D(C,B)+-+-+BA+-+CCBDA+-D(D,C)+-+-+BA+-+CCBDA+-D(A,D)+-+-+BA+-+CCBDA+-D(B,A)+-+-+BA+-+CCBDA+-D+-标记标记扩展：处理阴影与切点接触。有10种交点类型，且大得多的合法构形。关键点：随边的增加，计算呈线性增长。例子：调度例子：调度需完成一组N项任务J1,JN。每项任务j是由顺序执行的一组Lj项操作Oj1,OjLj组成。每项操作Oji有一个已知的时间段Tji。操作可能需要从一项有M个资源R1,RM的库中使用资源。一个资源不能同时被两项操作使用。所有的任务必须在时间t之前完成。问题：用离散时间0,T来安排每项操作的起始时间Sji。4项任务4个资源10项操作优先约束：S11+T11S12S12+T12S13.交付约束：S13+T13tS22+T22tS33+T33t.容量约束：S11+T11S21或者S21+T21S11操作(1,1)和(2,1)享用同一资源R1。因此，要么(1,1)在(2,1)之前全部完成，要么(2,1)在(1,1)之前完成。一般的一般的CSP解解重复直到所有变量已被赋值为止：采用一个一致性实施程序向前查看约束传播if 无解：回溯到前一个变量else选择下一个需赋值的变量利用变量排序启发选择一个值赋给该变量利用值排序启发CSP：树结构：树结构CSP重要特例：约束树重要特例：约束树约束图形是一棵树：两变量由一条路径相连。能用变量数的线性时间来求解。V2V1V4V5V7V3V6V8将变量排序，使得在序列中一个结点的父结点总出现在该结点之前如果父域中所有的值与所有子域中的值相一致，则很容易从树根开始来选择一致性的值。根约束树算法约束树算法1.由叶向上到根：由叶开始，对每个变量Vi：Vj=parent(Vi)去掉D(Vj)中所有与D(Vi)不一致的值x2.从根向下到叶：给根赋一个值对每个变量Vi：选择D(Vi)中一个值x，它应与赋给parent(Vi)的值是一致的注：由叶向上到根，只访问每个变量一次：N为去掉不一致值，在最坏场合，需查看每对赋值：d2总时间复杂性：O(Nd2)类树类树一旦为V6选择一个值后，约束图形就变成约束树。不知道要选那个值。因此，尝试所有可能值。更一般场合更一般场合G去掉由p个变量组成的连接群G，从而把图形转换成一个可有效求解的树问题。G称为循环割集（cycle cutset）不知道怎样为G中变量赋值：对于每次可能的为G中变量的一致性赋值：将树算法应用于其余变量总体算法称为割集调节（cutset conditioning）G去掉由p个变量组成的连接群G，从而把图形转换成一个可有效求解的树问题。G称为循环割集不知道怎样为G中变量赋值：对于每次可能的为G中变量的一致性赋值：将树算法应用于其余变量总体算法称为割集调节（cutset conditioning）注：为实现一次为G中变量的一致性赋值，在最坏场合下，需查看G中所有可能赋值：dp树算法：(N-p)d2总时间复杂性：O(N-p)dp+2)不幸的是，不可能用多项式时间来找到p的极小值。CSP：解：解CSP的局域搜索的局域搜索解解CSP的局域搜索技术的局域搜索技术这些问题能够表达为CSP已经用局域搜索方法（爬山法、模拟退火法、禁忌算法、遗传算法）来求解过这些问题局域搜索方法什么时候适用？局域搜索解对一些问题很有效除CSP外，还需优化代价函数在线更新CSP解SAT：ABCACDBDECDEACEN个皇后个皇后解解CSP的局域搜索的局域搜索状态=给所有变量的赋值移动=改变一个变量评估=变量间的冲突（不满足约束）数V1V2V3V4V5V6abcdefV1V2V3V4V5V6abcdef一般局域搜索：最少冲突算法一般局域搜索：最少冲突算法从一次给全部变量的赋值开始重复直到找到一个解或着到达迭代极限为止：在冲突变量中随机选择一个变量Vi置Vi等于违反约束最少的值注：在很多问题的求解中，远比CSP搜索来得有效所有爬山类方法都适用一般形式与WALKSAT相似N个皇后(140106回溯DFS+MRV13.5106向前查看40106向前查看+MRV817,000最少冲突4,000MRV启发总是很有效。局域搜索是令人吃惊地有效。能有效地解N=107时N个皇后问题。为什么能容易解决这样的问题？总结总结定义标准搜索改进回溯向前查看约束传播启发式算法变量排序值排序实例树结构CSP解CSP的局域搜索