Skip to content

约束满足问题（CSP）

CSP定义

如下图所示，在传统搜索中我们不关注state内部的情况，这种被称为原子表示。而在CSP方法中，我们使用因子表示，即将状态本身拆解为一组变量和值。

1770852039948

CSP的定义包括：

  • 变量 (Variables, \(X\)): 需要被赋值的对象集合 (\(X_1, ..., X_n\))。
    • 例子：地图着色中的每一个区域。
  • 域 (Domains, \(D\)): 每个变量可以取的值的集合 (\(D_i\))。
    • 例子：{红, 绿, 蓝}。
  • 约束 (Constraints, \(C\)): 限制变量取值的规则 (\(C_m\))。
    • 例子：相邻的区域不能涂相同的颜色 (\(X_1 \neq X_2\))。
  • 目标 (Goal): 找到一个 赋值 (Assignment) ，满足：
    1. 完整性 (Complete): 所有变量都被赋值。
    2. 一致性 (Consistent): 不违反任何约束。

回溯搜索

回溯搜索（Backtracking Search） 是CSP的标准解法。回溯搜索本质上是针对 CSP 优化的 深度优先搜索 (DFS) 。

工作流程:

  1. 每次只选择一个变量进行赋值（而不是生成整个新状态）。
  2. 检查这个赋值是否符合当前的约束。
  3. 如果符合: 继续递归给下一个变量赋值。
  4. 如果不符合: 放弃当前分支，回溯 (Backtrack) 到上一步，尝试域中的下一个值。

核心思想: "Fail fast"（一旦发现走不通立刻回头，而不是走到终点才发现错了）。

约束传播

约束传播 (Constraint Propagation)是用于加速回溯搜索的技术。

其内容顾名思义，我们可以利用约束条件，提早推导出哪些值是不可能的，从而缩小变量的域（Domain）。

常见方法包括：

  • 前向检查 (Forward Checking): 当给变量 \(X\) 赋值后，立即检查所有与 \(X\) 相连的未赋值变量，把它们域中与 \(X\) 冲突的值删掉。如果某个变量的域变为空，则立即回溯。
  • 弧一致性 (Arc Consistency / AC-3): 比前向检查更强。它在赋值前或赋值中，通过连锁反应传播约束，确保每条边（Arc）上的约束都是满足的，能更早地检测出无解的情况。

评论 #