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） 更多实例 调度 产品设计 资产分配 电路设计 受约束机器人的规划 … CSP：标准有哪些信誉好的足球投注网站 有哪些信誉好的足球投注网站空间 状态：给出k个变量赋值，而第k+1,…,N个变量未赋值。 后续态：通过给第k+1个变量赋值，而保持其它变量不变，来获得一个态的后续态。 始态： (V1=?,V2=?,V3=?,V4=?,V5=?,V6=?) 终态：所有变量已赋值，且约束也已满足。 无任何关于转换代价的概念。即，只想找到一个解，而不担心是怎样找到的。 深度优先有哪些信誉好的足球投注网站（DFS） 采用递归方式： 对D中每个可能值： 为后续态中的下个未赋值变量赋该值 赋值后，评估当前态的后续态 一旦找到解，就停止 DFS 改进： 只评估那些赋值，它们不违反任何与目前已赋值相关的约束。 不有哪些信誉好的足球投注网站那些明显不可能通往解的分枝。 预测合法的赋值。 控制变量与值的次序。 CSP：改进 回溯DFS 回溯DFS 对D中每个可能值x： 如果将x赋给下个未赋值变量Vk+1后，不违反与k个已赋值变量相关的任何约束： 给Vk+1赋x。 赋值后，评估当前态的后续态。 如果找不到合法赋值，则回溯到前一个状态。 一旦找到解，就停止。 回溯DFS评论 额外的计算：每步都需评估与当前候选赋值(变量=值)相关的约束。 用预测来改进不知情有哪些信誉好的足球投注网站： 一个变量的赋值对所有其它变量有什么影响？ 下一个应赋值的变量是谁？并且应遵循什么次序来评估值？ 当一条路径失败，怎样避免犯同样错误？ 向前查看 对未赋值的变量，跟踪余下的合法值。 当变量无合法值时，回溯。 向前查看 对未赋值的变量，跟踪余下的合法值。 当变量无合法值时，回溯。 向前查看 对未赋值的变量，跟踪余下的合法值。 当变量无合法值时，回溯。 向前查看 对未赋值的变量，跟踪余下的合法值。 当变量无合法值时，回溯。 向前查看 对未赋值的变量，跟踪余下的合法值。 当变量无合法值时，回溯。 向前查看 对未赋值的变量，跟踪余下的合法值。 当变量无合法值时，回溯。 约束传播（CP） 向前查看不检查所有不一致性，因为它只能查看那些与该当前赋值变量相关的约束。 能查看得更远些吗？ 约束传播 V=在有哪些信誉好的足球投注网站的当前层次，需赋值的变量。 将D(V)中的一个值赋给V 对与V相连的每个变量V’： 去掉D(V’ )中与已赋值变量不一致的值 对与V’ 相连的每个变量V”： 去掉D(V”)中不再可能的候选值 对与V” 相连的每个变量： ……直到不再有能被去掉的值为止 注： 清理D(V’ )是属于已有的向前查看 清理D(V”)…则是属于新的约束传播 解图形着色问题的CP Propagate(node, color) 从node的所有近邻的值域中去掉color 对每个近邻N: if 第1步后，D(N)中只剩一种颜色，即D(N)={c}： Propagate(N, c) 注： 在设置V2后，无需更多有哪些信誉好的足球投注网站，只需一步CP就直接得到一个解。 一些问题甚至可无需任何有哪些信誉好的足球投注网站，直接由CP来解。 更一般的CP：边一致性 A=活跃边(Vi,Vj)的队列 当A不空时，重复执