第 II 部分 · 问题求解
第 6 章 约束满足问题
Chapter 6 · Constraint Satisfaction Problems
本章导读
一类特殊的搜索问题：状态是变量赋值，目标是满足一组约束。通过约束传播与启发式回溯大幅剪枝，是求解调度、图着色、数独等组合问题的标准武器。
学习要点
- CSP 形式化：变量 / 值域 / 约束三元组；二元约束图与全局约束（如 AllDiff）。
- 回溯搜索 = 深度优先 + 一次赋一个变量；变量排序（最少剩余值 MRV、度启发式）与值排序（最少约束值）的威力。
- 约束传播：前向检验、弧一致性 AC-3；传播与搜索交替执行（MAC）。
- 利用问题结构：连通分量分解、树状 CSP 的线性时间算法、树分解与割集条件化。
- 局部修复方法：min-conflicts 启发式在大规模 CSP（百万皇后）上惊人有效。
核心概念
| 术语 | English | 一句话解释 |
|---|---|---|
| 约束满足问题 | CSP | 变量 + 值域 + 约束构成的一类结构化搜索问题 |
| 回溯搜索 | Backtracking Search | 逐变量赋值、冲突即回退的深度优先搜索 |
| 最少剩余值 | MRV | 优先给候选值最少的变量赋值（失败优先） |
| 前向检验 | Forward Checking | 赋值后立即删除邻居的非法候选值 |
| 弧一致性 | Arc Consistency | 变量每个取值在约束另一端都有支持 |
| AC-3 | AC-3 | 用队列传播弧一致性的经典算法 |
| 最少冲突 | Min-Conflicts | 每次选择与已赋变量冲突最少的值 |
| 树分解 | Tree Decomposition | 把约束图切成子问题降低求解复杂度 |
| 全局约束 | Global Constraint | 涉及大量变量的结构化约束，可做专门传播 |
配套代码（aima-python）
aima-python 是官方维护的开源算法库（MIT 协议），建议每学完一章就跑一遍对应模块的示例。