6约束满足问题解析.ppt

约束满足问题（约束满足问题（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)，有ViVjCSP定义定义•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  10–D  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 (kj) 是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,Y}CSP启发式算法：值排序启发式算法：值排序•最少约束值（LCV）•选择使相邻变量可用值减少最少的值•优先选用最可能的值（也即为随后的变量赋值提供最大灵活性）来获得一个解V1V2V3V4V5V6GR????四种颜色：D={R,G,B,Y}要给V3赋哪个值？CP实例：白描解释实例：白描解释凹边凹边凸边凸边?假设假设•无阴影•公共面之间无边•一般观察点•只考虑三面顶点特殊观察点一般观察点不允许的边3种可能的边标记种可能的边标记•+：凸边•：凹边•：边界按规定，当沿着箭头方向看时，面在右侧。

4种可能的交点类型种可能的交点类型TVYW1+++2---3-4-5-•存在34342=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+T11S12S12+T12S13......交付约束：S13+T13tS22+T22tS33+T33t......容量约束：S11+T11S21或者S21+T21S11操作(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：：ABCACDBDECDEACEN个皇后个皇后解解CSP的局域搜索的局域搜索•状态=给所有变量的赋值•移动=改变一个变量•评估=变量间的冲突（不满足约束）数V1V2V3V4V5V6abc‘defV1V2V3V4V5V6abcdef一般局域搜索：最少冲突算法一般局域搜索：最少冲突算法•从一次给全部变量的赋值开始•重复直到找到一个解或着到达迭代极限为止：–在冲突变量中随机选择一个变量Vi–置Vi等于违反约束最少的值注：•在很多问题的求解中，远比CSP搜索来得有效•所有爬山类方法都适用•一般形式与WALKSAT相似N个皇后(140106回溯DFS+MRV13.5106向前查看>40106向前查看+MRV817,000最少冲突4,000•MRV启发总是很有效。

•局域搜索是令人吃惊地有效能有效地解N=107时N个皇后问题为什么能容易解决这样的问题？总结总结•定义•标准搜索•改进–回溯–向前查看–约束传播•启发式算法–变量排序–值排序•实例•树结构CSP•解CSP的局域搜索。