约束满足问题（CSP）

CSP定义

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

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）上的约束都是满足的，能更早地检测出无解的情况。

变量排序启发式

回溯搜索的效率在很大程度上取决于变量选择顺序——先给哪个变量赋值，可能导致搜索空间产生巨大差异。

最少剩余值（MRV）

最少剩余值（Minimum Remaining Values, MRV） 启发式，也称为"最受约束变量"或"失败优先"启发式，其策略是：

优先选择域中剩余合法值最少的变量。

直觉很简单：如果一个变量只剩 1 个合法值，那它必须取那个值；如果一个变量只剩 2 个合法值而另一个还剩 10 个，先处理前者能更快地发现矛盾。

形式化地，在回溯搜索的每一步中，我们选择：

\[ X^* = \arg\min_{X_i \in \text{unassigned}} |D_i| \]

其中 \(D_i\) 是变量 \(X_i\) 当前的有效域（经过约束传播后的剩余值集合）。

MRV 的有效性

MRV 之所以被称为"失败优先"，是因为它优先处理最容易失败的变量。这看似违反直觉，但实际上可以尽早触发回溯，避免在注定失败的分支上浪费大量时间。实验表明，MRV 在大多数 CSP 问题上都能显著减少搜索节点数。

度启发式

度启发式（Degree Heuristic） 用于在 MRV 产生平局时打破平衡。其策略是：

优先选择与最多未赋值变量存在约束关系的变量。

形式化地，变量 \(X_i\) 的"度"定义为它与其他未赋值变量之间的约束条数。度启发式选择度最大的变量：

\[ X^* = \arg\max_{X_i \in \text{unassigned}} \text{deg}(X_i) \]

直觉是：度最大的变量对其他变量的约束最多，先处理它可以最大程度地缩小后续变量的域。

在地图着色问题中，度启发式会优先选择与最多相邻（且尚未着色）区域相连的区域。

值排序

变量排序决定了"先给谁赋值"，而值排序（Value Ordering）决定了"先尝试哪个值"。

最少约束值（LCV）

最少约束值（Least Constraining Value, LCV） 启发式的策略是：

优先尝试对其他未赋值变量施加约束最少的值。

具体来说，对于当前选定的变量 \(X_i\)，我们对其域 \(D_i\) 中的每个值 \(v\) 计算：如果给 \(X_i\) 赋值 \(v\)，会使得多少个邻居变量的域缩小。选择使邻居域缩小最少的那个值。

\[ v^* = \arg\min_{v \in D_i} \sum_{X_j \in \text{neighbors}(X_i)} |\text{eliminated}(X_j, v)| \]

其中 \(\text{eliminated}(X_j, v)\) 表示因 \(X_i = v\) 而从 \(X_j\) 的域中移除的值的数量。

变量排序 vs 值排序的哲学差异

注意 MRV 和 LCV 的策略方向是相反的：

• MRV（变量排序）：失败优先 —— 先处理最难的变量，尽早发现死路。
• LCV（值排序）：成功优先 —— 先尝试最有希望成功的值，尽量避免死路。

两者结合时效果最好：先选择最受约束的变量（MRV），再从最不约束他人的值开始尝试（LCV）。

局部搜索求解 CSP

除了回溯搜索外，我们还可以用局部搜索（Local Search）方法来求解 CSP。局部搜索从一个完整但可能不一致的赋值出发，通过反复修改变量的值来减少冲突。

最小冲突算法

最小冲突算法（Min-Conflicts） 是最经典的 CSP 局部搜索方法：

function MIN-CONFLICTS(csp, max_steps):
    current ← 对所有变量随机赋一个初始值
    for i = 1 to max_steps:
        if current 满足所有约束:
            return current
        var ← 随机选择一个存在冲突的变量
        value ← 选择使 var 冲突数最少的值
        将 var 的值设为 value
    return failure

算法的核心步骤：

1. 随机初始化：给所有变量随机赋值（不管是否满足约束）。
2. 选择冲突变量：随机选取一个当前赋值违反了某条约束的变量。
3. 最小化冲突：将该变量的值改为使冲突总数最小的值（如果存在平局则随机选一个）。
4. 重复直到找到解或达到最大迭代次数。

最小冲突的效率

最小冲突算法的一个惊人特点是，对于许多 CSP 问题（包括 \(n\) 皇后问题），它几乎可以在常数时间内找到解，与问题规模无关。例如，100 万皇后问题平均只需约 50 步即可求解。这是因为大多数随机初始赋值已经接近一个解，只需少量局部调整即可收敛。

局部搜索的局限性

局部搜索的主要问题是容易陷入局部最优（Local Minimum）——即所有单变量修改都无法减少冲突数，但当前赋值并非全局最优解。常见的应对策略包括：

• 随机重启（Random Restart）：陷入局部最优时，重新随机初始化。
• 随机游走（Random Walk）：以一定概率随机选择值（而非最小冲突值），帮助跳出局部最优。
• 模拟退火（Simulated Annealing）：以递减的概率接受更差的解。
• 禁忌搜索（Tabu Search）：维护一个"禁忌列表"，避免重复访问最近的赋值。

CSP 作为优化问题

到目前为止，我们讨论的 CSP 都是硬约束：约束要么满足，要么不满足。但在现实世界中，很多问题需要处理软约束（Soft Constraints）和偏好（Preferences）。

软约束与加权 CSP

加权 CSP（Weighted CSP）或约束优化问题（Constraint Optimization Problem, COP）对每条约束赋予一个权重或代价：

• 硬约束：必须满足，违反即无效（权重 = \(\infty\)）。
• 软约束：违反会产生一定代价，但不会导致解无效。

目标从"找到满足所有约束的赋值"变为"找到使总代价最小化的赋值"：

\[ \min_{\text{assignment}} \sum_{C_m \in \text{soft constraints}} w_m \cdot \mathbb{1}[\text{violated}(C_m)] \]

其中 \(w_m\) 是约束 \(C_m\) 的权重，\(\mathbb{1}[\text{violated}(C_m)]\) 在约束被违反时为 1。

在更一般的形式中，每条软约束可以定义一个代价函数 \(f_m\)，赋值的总代价为：

\[ \min_{\text{assignment}} \sum_{C_m} f_m(\text{assignment}) \]

常见的优化方法

加权 CSP 可以用以下方法求解：

• 分支定界（Branch and Bound）：在回溯搜索中维护当前最优解的代价上界，剪掉代价已超过上界的分支。
• 局部搜索：使用最小冲突的加权版本，每次选择使加权冲突代价最小的值。
• 整数线性规划（ILP）：将 CSP 转化为数学规划问题，用成熟的求解器处理。

现实世界中的 CSP 应用

CSP 框架具有强大的通用性，可以建模大量实际问题。

课程调度

大学课程调度是一个典型的 CSP 问题：

• 变量：每门课程的时间段和教室。
• 域：所有可用的时间段和教室。
• 约束： * 同一教授不能在同一时间上两门课（硬约束）。 * 同一教室不能同时安排两门课（硬约束）。 * 教室容量必须满足选课人数（硬约束）。 * 尽量避免同一学生的课程时间冲突（软约束/偏好）。 * 教授偏好的时间段（软约束/偏好）。

数独

数独是一个非常经典的 CSP 实例：

• 变量：\(9 \times 9\) 网格中每个空格 \(X_{ij}\)。
• 域：\(D_{ij} = \{1, 2, ..., 9\}\)。
• 约束： * 每一行中所有数字不重复（All-Different 约束）。 * 每一列中所有数字不重复。 * 每个 \(3 \times 3\) 宫中所有数字不重复。

数独非常适合用 弧一致性 + 回溯搜索 + MRV 来求解。事实上，对于大多数数独谜题，单独使用弧一致性（AC-3）就能解出大部分格子，只需少量回溯即可完成。

其他应用

CSP 框架还广泛应用于：

• 地图着色：给地图的区域着色，使相邻区域颜色不同（经典的图着色问题）。
• 资源分配：将有限的资源分配给多个任务，满足各种约束。
• 电路设计：电子元件的布局和布线。
• 自然语言处理：词性标注、句法分析中的约束传播。
• 计算机视觉：场景标注、图像分割中的标签一致性约束。

---

评论