6约束满足问题解析

– Qi Qj，即不能在同一 行 – |Qi Qj| |i j|，即不 能在对角上
• (Q1,Q2)的合法值是 (1,3)，(1,4)，(2,4)， (3,1)，(4,1)，(4,2)
实例：密算（Cryptarithmetic）
• 变量：D,E,M,N,O,R,S,Y • 域：{0,1,2,3,4,5,6,7,8,9} • 约束
• 通常隐式地定义约束，即，定义一个函数来测试 一组变量是否满足该约束
– 例如：对每条边(i,j)，有ViVj
CSP定义
• CSP的解：每个变量有一个满足所有相关 约束的值 • 特点：
– 状态的分解表示：一组变量及其值 – 利用状态的结构和通用启发方式 – 通过确定违反约束的变量与值组合可取消大部 分搜索空间
坏值
深度优先搜索（DFS）
V1 V2 V3 V4 V5 V6 ? V1 V2 V3 V4 V5 V6 B ? ? ? ? ? ? ? ? ? ? 值次序： (B,R,G)
V1 V2 V3 V4 V5 V6 R ? ? ? ? ?
V1 V2 V3 V4 V5 V6 G ? ? ? ? ?
V1 V2 V3 V4 V5 V6 B B ? ? ? ?
二元CSP
• 如果变量V与V’出现在一个约束中，则它们是有联 系的。 • V近邻=与V有联系的变量。 • V域，记为D(V)，为变量V可取值的集。 • Di=D(Vi)
• 二元CSP问题的约束图：
– 结点是变量 – 连线代表约束 – 与图形着色问题相同
实例：N个皇后
• 变量：Qi • 域：Di={1,2,3,4} • 约束
– M 0，S 0，单元约束 – Y = D E 或Y = D E 10 – D E，D M，D N 等
S E N D MO R E M O N E Y
更多实例
• • • • • • 调度 产品设计 资产分配 电路设计 受约束机器人的规划 …
CSP：标准搜索
搜索空间
值次序： (B,R,G)
V1 V2 V3 V4 V5 V6 B ? ? ? ? ?
V1 V2 V3 V4 V5 V6
V1 V2 V3 V4 V5 V6 B R ? ? ? ?
B
Bห้องสมุดไป่ตู้
?
?
?
?
V1 V2 V3 V4 V5 V6
B R R B ? ?
V1 V2 V3 V4 V5 V6
B
R
R
B
G
?
回溯DFS
• 如果找不到合法赋值，则回溯到前一个状 态。 • 一旦找到解，就停止。
回溯DFS评论
• 额外的计算：每步都需评估与当前候选赋 值(变量=值)相关的约束。 • 用预测来改进不知情搜索：
– 一个变量的赋值对所有其它变量有什么影响？ – 下一个应赋值的变量是谁？并且应遵循什么次 序来评估值？ – 当一条路径失败，怎样避免犯同样错误？
约束满足问题（CSP）
概要
• CSP定义 • 标准搜索 • 方法改进
– 回溯 – 向前查看 – 约束传播
• 启发式算法
– 变量排序 – 值排序
• CSP实例 • 树结构CSP • 解CSP的局域搜索
CSP：定义
范例：图形着色
• • • • 考虑一个图形中的N个结点。 把变量V1,…,VN的值赋给N个结点。 值取自{R,G,B} 约束：如果i与j之间有边，则Vi与Vj必不同。
V1 V2 V3 V4 V5 V6 ? ? ? ? ? ?
值次序： (B,R,G)
V1 V2 V3 V4 V5 V6
B ? ? ? ? ?
V1 V2 V3 V4 V5 V6
R ? ? ? ? ?
V1 V2 V3 V4 V5 V6
G ? ? ? ? ?
V1 V2 V3 V4 V5 V6 B B ? ? ? ?
V1 V2 V3 V4 V5 V6 ? ? ? ? ? ? 值次序： (B,R,G)
V1 V2 V3 V4 V5 V6 B ? ? ? ? ?
V1 V2 V3 V4 V5 V6 B B ? ? ? ?
V1 V2 V3 V4 V5 V6
B R ? ? ? ?
不考虑该树枝，因为 V2=B与目前已赋值 相关的约束不符。
样本状态： (V1=G,V2=B,V3=?,V4=?,V5=?,V6=?)
• 状态：给出k个变量赋值，而第k+1,…,N个变量未 赋值。 • 后续态：通过给第k+1个变量赋值，而保持其它变 量不变，来获得一个态的后续态。 • 始态： (V1=?,V2=?,V3=?,V4=?,V5=?,V6=?) • 终态：所有变量已赋值，且约束也已满足。 • 无任何关于转换代价的概念。即，只想找到一个 解，而不担心是怎样找到的。
范例：图形着色
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)}]
向前查看
• 对未赋值的变量，跟踪余下的合法值。 • 当变量无合法值时，回溯。
值次序：(R,B,G) V1 V2 V3 V4 V5 V6 R B ? ? ? ? ? ? ? ? ? ? ? ?
G
?
?
?
?
?
?
向前查看
• 对未赋值的变量，跟踪余下的合法值。 • 当变量无合法值时，回溯。
V1 V2 V3 V4 V5 V6
B
R
R
B
?
?
回溯到前一个状态， 因为不能给V6赋合法 的值。
V1 V2 V3 V4 V5 V6 B R R B G ?
回溯DFS
• 对D中每个可能值x：
– 如果将x赋给下个未赋值变量Vk+1后，不违反与 k个已赋值变量相关的任何约束：
• 给Vk+1赋x。 • 赋值后，评估当前态的后续态。
• 采用递归方式：
对D中每个可能值： 为后续态中的下个未赋值变量赋该值 赋值后，评估当前态的后续态 一旦找到解，就停止
DFS
• 改进：
– 只评估那些赋值，它们不违反任何与目前已赋 值相关的约束。 – 不搜索那些明显不可能通往解的分枝。 – 预测合法的赋值。 – 控制变量与值的次序。
CSP：改进
V1 V2 V3 V4 V5 V6 ? ? ? ? ? ?