📑 本页目录（点开跳转）
15 · CSP 的启发式
⏱ 31 分钟 ｜ ⭐⭐ 一行约束都不改，只换「先填谁、先试哪个值」
🎯 一句话
上一章的变量顺序是写死的，而正是那个顺序亲手制造了第 ⑤ 步的死局。这一章只改两件事：先赋值哪个变量、先试哪个值 —— 约束一条没动，代价掉一个数量级。
⚠️ 而且这两件事的挑选方向正好相反。这是全章最容易搞反的一点，第三节专门讲。
🎯 一、变量序：先挑最快失败的那个
上一章的顺序是 WA → NT → NSW → Q → SA → V → T。 它在第 ⑤ 步撞墙：SA 的三个邻居已经占掉了红、绿、蓝，SA 无值可赋。
⭐ 回头看，SA 是七个变量里最难的一个 —— 它和 5 个区域相邻（其他变量最多 3 个）。 把最难的留到最后，等于把炸弹推迟引爆。
⭐⭐ MRV（Minimum Remaining Values，最小剩余值）： 每一步都选「当前合法取值最少」的那个变量。 别名 most-constrained-variable，或者更直白的叫法：fail-first。
⚠️ 为什么是「先失败」而不是「先成功」
这个名字听起来像在自找麻烦，其实反过来：
- 如果这条路注定走不通，那越早发现越好 —— 早一层发现，就少搜一整棵子树。
- 如果这条路走得通，那先填哪个都能填完，MRV 也不吃亏。
💡 一句话直觉：剩 1 个选择的变量，其实是没有选择 —— 那不是「选」，那是「记账」。 先把这些没得选的填掉，问题会自己变小。
🔨 手算：同一张地图，MRV 走一遍
初始所有变量值域都是 {红, 绿, 蓝}。全部并列 3 个，怎么破？
⭐ 度启发（degree heuristic） 用来破并列：挑未赋值邻居最多的那个。 直觉：它牵连最广，先钉死它能砍掉最多的分支。
| 步 | 各变量剩余值 | MRV 选谁 | 赋值 |
|---|---|---|---|
| ① | 全是 3 —— 并列 | ⭐ 度启发：SA 有 5 个邻居，最多 | SA = 红 |
| ② | WA/NT/Q/NSW/V 都剩 {绿,蓝}=2，T 剩 3 | 五个并列 2，度启发选 NT（3 个邻居） | NT = 绿 |
| ③ | WA 剩 {蓝}=1 ⭐ | WA（唯一剩 1 个） | WA = 蓝 |
| ④ | Q 剩 {蓝}=1 | Q | Q = 蓝 |
| ⑤ | NSW 剩 {绿}=1 | NSW | NSW = 绿 |
| ⑥ | V 剩 {蓝}=1 | V | V = 蓝 |
| ⑦ | T 剩 3（孤立点） | T | T = 红 |
⭐⭐ 零回溯。 从第 ③ 步起每一步都只有一个合法值 —— 根本没得选，也就无从选错。 对照上一章那个写死的顺序：回溯 2 次、试值 17 次；MRV：回溯 0 次、试值 15 次。
⚠️ 地图太小，差别看着不大。规模一上去就是另一回事了（第四节的数字）。
🎨 二、值序：先试给别人留路最多的那个
变量挑好了，它的几个合法值先试哪个？
⭐ LCV（Least Constraining Value，最少约束值）： 选那个「排除掉邻居选项最少」的值。
例子：假设当前 SA 可以填红或蓝。 - 填红：邻居里还有 3 个变量的值域里有红，于是砍掉 3 个选项 - 填蓝：只有 1 个邻居的值域里有蓝，只砍掉 1 个
⭐ LCV 选蓝 —— 给后面留下最大的回旋余地。
⚠️ 三、⭐⭐ 全章最容易搞反的一点：两个方向是相反的
| 挑什么 | 叫法 | 为什么 | |
|---|---|---|---|
| 变量序 | ⭐ 挑最容易失败的（剩余值最少） | fail-first | 死路要早点发现，好砍掉整棵子树 |
| 值序 | ⭐ 挑最容易成功的（约束别人最少） | least-constraining | 我们只需要一个解，尽快撞上它 |
为什么不矛盾 —— 因为两者服务的目标不同：
⭐⭐ 变量的选择决定「要不要搜这棵树」，值的选择决定「先走哪个分支」。
- 变量层面：这个变量迟早都要填，那就先填最可能爆的那个 —— 早爆早剪枝。
- 值层面：同一个变量的几个值是互斥的分支，只要有一个能成功就够了， 所以先试最可能成功的那个。
💡 换个说法：变量序在优化「最坏情况」（尽早排除死路），值序在优化「最好情况」（尽早撞上解）。 它们优化的根本不是同一件事，所以方向相反完全合理。
📊 四、放到 n 皇后上：数量级的差别
把 n 皇后建成 CSP（变量 = 每一行，值 = 该行皇后放第几列，约束 = 不同列且不同对角线）， 比较「静态序（一行行来）」和「MRV」。
⭐ 下面的数字是实跑的（试值 = 每把一个值放上去检查一次）：
| 规模 | 静态序 · 试值 | 静态序 · 回溯 | ⭐ MRV · 试值 | MRV · 回溯 |
|---|---|---|---|---|
| 8 皇后 | 876 | 105 | 572 | 67 |
| 12 皇后 | 3,066 | 249 | 1,770 | 141 |
| ⭐ 16 皇后 | 160,712 | 10,036 | 584 | 28 |
| 20 皇后 | 3,992,510 | 199,615 | 2,710 | 125 |
| 24 皇后 | 9,878,316 | 411,584 | 756 | 19 |
读这张表要注意三件事：
- ⭐⭐ 16 皇后是 160712 → 584，275 倍。而 8 皇后只有 876 → 572，几乎没差。 启发式的价值随规模爆炸式增长 —— 小例子上试不出它的好。
- ⚠️ MRV 的曲线不是单调的：16 皇后 584 步，20 皇后反而要 2710 步，24 皇后又掉回 756。 启发式是启发式，不是保证 —— 它平均很好，但不承诺每个实例都好。
- 💀 ⭐⭐ 真正的差别是增长曲线，不是「能不能跑完」：静态序从 16 皇后到 20 皇后，试值涨了 25 倍（160,712 → 3,992,510）， 到 24 皇后又涨到 987 万；而 MRV 在同一区间是 584 → 2,710 → 756，基本在原地。 ⚠️ 两个都解得出来 —— 静态序 24 皇后在普通笔记本上也就几秒。差的是它迟早会撞墙，而 MRV 还没开始爬。
🔄 五、换个思路：从「一步步构造」到「先猜再改」
前面所有方法都是构造式的：一次赋一个变量，赋错了退回。 还有一条完全不同的路：先把所有变量都随便填上，然后不断修。
⭐ 最小冲突（min-conflicts）： 1. 给每个变量随机赋一个值（一个完整但很可能违反约束的赋值） 2. 随机挑一个处于冲突中的变量 3. 把它改成「让冲突数最少」的那个值 4. 重复，直到没有冲突
⚠️ 这和前面几章的搜索有个本质区别：它始终持有一个完整赋值， 在「所有完整赋值」的空间里爬山，而不是在「部分赋值」的树上往下走。
代价：⚠️ 它不完备 —— 可能卡在局部极小（改哪个变量冲突都不减少）， 也无法证明无解。⭐ 这一点和第 9 章的势场法完全同构： 同样是爬山，同样丢掉了完备性。
📚 文献结论（Minton et al. 1992，不是本章实测）：最小冲突解 n 皇后时， 所需步数几乎与 n 无关 —— 百万皇后也能在几十步量级内解出。 ⭐ 原因是 n 皇后的解极其稠密，随机一撒就离某个解不远。 ⚠️ 别把这个结论外推：解稀疏的问题上，局部搜索会卡得很惨。
💡 实践中的位置：最小冲突在排班、调度这类「已有一个可行解，环境变了要快速修补」的场景里 特别好用 —— 从旧解开始修，比从头搜快得多。
🌳 六、问题结构本身也能利用
⭐ 如果约束图长得特别，可以绕开搜索：
| 结构 | 结论 |
|---|---|
| ⭐ 树结构（约束图无环） | 有 $O(nd^2)$ 的算法：选个根、拓扑排序、从叶到根做一遍弧相容、再从根到叶赋值，保证零回溯 |
| 近似树（去掉几个点就成树） | 割集条件：枚举那几个点的所有取值，剩下的部分按树来解 |
| 树分解 | 把图拆成互相重叠的小块，每块当一个"超级变量" |
💡 澳大利亚地图里，T（塔斯马尼亚）是孤立点，而去掉 SA 之后剩下的图就变成了一棵树 —— 这正是割集法的教科书例子：枚举 SA 的 3 种颜色，每种情况下剩余部分都能零回溯解完。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 14 · 回溯与约束传播 | ⭐ 本章的对照组全在那里：同一张地图、同一组约束，那边的写死顺序要回溯 2 次，本章 MRV 零回溯。两章合起来才是完整的 CSP 求解器 |
| 13 · CSP 是什么 | 度启发用的是约束图的度数，那一章画了这张图 |
| 09 · 运动规划 | ⭐ 最小冲突和势场法是同一类东西：都是爬山、都很快、都丢掉了完备性、都可能卡在局部极小 |
| 07 · 启发式与 A* | ⚠️ 注意「启发式」这个词在两处的意思不一样：那边的 $h$ 是估计还剩多远（可容许性有严格定义），这里的 MRV/LCV 是选择的次序（没有可容许性一说，纯经验）。同一个词，两个概念 |
| 16 · 不确定性下的推理 | 下一站：前面所有方法都假设「约束是硬的、观测是确定的」。真实世界不是 |
✅ 检查点
- MRV 是什么？为什么叫 fail-first？「先失败」听起来像自找麻烦，好处在哪？
- 初始所有变量值域都是 3 个，MRV 完全并列，怎么破？为什么这么破？
- 在澳大利亚地图上用 MRV，第一个被赋值的是谁？为什么？最终回溯几次？
- LCV 是什么？举例说明它怎么选。
- ⭐ 变量序和值序的挑选方向为什么相反？各自在优化什么？
- 16 皇后从静态序到 MRV，试值次数从多少变成多少？这张表还说明了哪两件事？
- 最小冲突算法的四步是什么？它和前面的搜索有什么本质区别？
- 最小冲突的代价是什么？它和第 9 章的哪个方法同构？
- 「百万皇后几十步就能解」—— 这个结论能外推到所有 CSP 吗？为什么？
- 树结构的 CSP 有什么特别的？澳大利亚地图怎么利用这一点？
👀 答案
- 每一步选「当前合法取值最少」的变量（most-constrained-variable / fail-first）。⭐ 好处：如果这条路注定走不通，越早发现越好 —— 早一层发现就少搜一整棵子树；而如果走得通，先填谁都能填完，不吃亏。💡 直觉：剩 1 个选择的变量其实是没有选择，那不是「选」是「记账」。
- ⭐ 度启发（degree heuristic）：挑未赋值邻居最多的那个。直觉是它牵连最广，先钉死它能砍掉最多分支。
- SA，因为它有 5 个邻居（其他变量最多 3 个）。⭐ 而 SA 正是上一章第 ⑤ 步撞墙的那个变量 —— 把最难的留到最后等于把炸弹推迟引爆。最终 零回溯（对照：上一章写死顺序回溯 2 次、试值 17 次；MRV 回溯 0 次、试值 15 次）。从第 ③ 步起每步只有一个合法值，根本没得选也就无从选错。
- 最少约束值：选那个排除掉邻居选项最少的值。例子：SA 可填红或蓝，填红砍掉 3 个邻居选项、填蓝只砍 1 个 ⟹ 选蓝，给后面留最大回旋余地。
- ⭐⭐ 因为服务的目标不同：变量的选择决定「要不要搜这棵树」（这个变量迟早要填，先填最可能爆的 → 早爆早剪枝，优化最坏情况）；值的选择决定「先走哪个分支」（几个值是互斥分支，只要一个成功就够 → 先试最可能成功的，优化最好情况）。方向相反完全合理。
- 160,712 → 584（约 275 倍）。另两件事：① ⭐⭐ 启发式的价值随规模爆炸式增长 —— 8 皇后只有 876→572 几乎没差，小例子上试不出它的好；② ⚠️ MRV 曲线不单调（16 皇后 584、20 皇后 2710、24 皇后又回到 756）—— 启发式是启发式不是保证，平均很好但不承诺每个实例。💀 ⭐ 差的是增长曲线不是「能不能跑完」：静态序 16→20 皇后试值涨 25 倍（160,712 → 3,992,510）、24 皇后近千万，而 MRV 基本在原地 —— 两个都解得出来，差在静态序迟早撞墙。
- ① 全部变量随机赋值（完整但很可能违反约束）② 随机挑一个处于冲突中的变量 ③ 改成让冲突数最少的值 ④ 重复到无冲突。⚠️ 本质区别：它始终持有一个完整赋值，在「所有完整赋值」的空间里爬山，而不是在「部分赋值」的树上往下走。
- ⚠️ 不完备 —— 可能卡在局部极小，也无法证明无解。⭐ 和第 9 章的势场法完全同构：同样是爬山、同样快、同样丢掉完备性。
- 不能。 ⭐ 那个结论成立是因为 n 皇后的解极其稠密，随机一撒就离某个解不远。⚠️ 解稀疏的问题上局部搜索会卡得很惨。（另外这是 Minton et al. 1992 的文献结论，不是本章实测。）
- 约束图无环时有 $O(nd^2)$ 算法：选根、拓扑排序、从叶到根做一遍弧相容、再从根到叶赋值，保证零回溯。💡 澳大利亚地图里 T 是孤立点，而去掉 SA 之后剩下的图就是一棵树 —— 枚举 SA 的 3 种颜色，每种情况剩余部分都能零回溯解完（割集条件）。
🛑 可以停在这里
⚡ 走神救援
⭐⭐ 这一章一条约束都没改，只换了两件事：先填哪个变量、先试哪个值 —— 代价掉一个数量级。 变量序：MRV（最小剩余值 / fail-first），每步选当前合法取值最少的那个。⭐ 「先失败」不是自找麻烦：注定走不通的路越早发现越好，早一层发现就少搜一整棵子树；走得通的话先填谁都一样。💡 剩 1 个选择的变量其实是没有选择，那是记账不是选择。全部并列时用 ⭐ 度启发破并列：挑未赋值邻居最多的（牵连最广，钉死它砍掉最多分支）。🔨 澳大利亚地图手算：初始全并列 3 → 度启发选 SA（5 个邻居） —— ⭐ 而 SA 正是上一章第 ⑤ 步撞墙的那个变量，把最难的留到最后等于把炸弹推迟引爆；之后 NT，然后从第 ③ 步起 WA/Q/NSW/V 每步都只剩一个合法值，根本没得选也就无从选错。结果 ⭐⭐ 零回溯（对照上一章写死顺序：回溯 2 次、试值 17 次；MRV：回溯 0 次、试值 15 次）。值序：LCV（最少约束值） —— SA 可填红或蓝，填红砍掉邻居 3 个选项、填蓝只砍 1 个 ⟹ 选蓝，给后面留回旋余地。⚠️⚠️ 全章最容易搞反的一点：两个方向相反。变量挑最容易失败的（fail-first），值挑最容易成功的（least-constraining）。⭐⭐ 不矛盾是因为变量的选择决定「要不要搜这棵树」（优化最坏情况，早爆早剪枝），值的选择决定「先走哪个分支」（优化最好情况，只要一个解就够）。n 皇后实跑数据：8 皇后 876→572（几乎没差），⭐ 16 皇后 160712→584（275 倍），20 皇后静态序 3,992,510 而 MRV 只要 2710，24 皇后静态序 9,878,316 而 MRV 756 步/19 次回溯。三个要点：① 启发式的价值随规模爆炸式增长，小例子上试不出来；② ⚠️ MRV 曲线不单调（16→20→24 是 584→2710→756），启发式是启发式不是保证；③ 💀 差别是增长曲线不是「能不能跑完」：静态序 16→20 皇后试值涨 25 倍、到 24 皇后近千万，而 MRV 基本在原地 —— 两个都解得出来，差的是静态序迟早撞墙。另一条路：最小冲突（全部随机赋值 → 挑一个冲突变量 → 改成冲突最少的值 → 重复）。⚠️ 本质区别是它始终持有完整赋值、在完整赋值空间里爬山，而不是在部分赋值的树上往下走。代价是 ⚠️ 不完备（可能卡在局部极小，无法证明无解）—— ⭐ 和第 9 章的势场法完全同构。📚 文献结论（Minton 1992，非本章实测）：解 n 皇后所需步数几乎与 n 无关，因为解极其稠密；⚠️ 解稀疏的问题上局部搜索会卡得很惨。💡 实践位置：排班调度里「旧解还在、环境变了要快速修补」的场景，从旧解开始修比从头搜快得多。最后，问题结构本身可利用：约束图是树时有 $O(nd^2)$ 零回溯算法；⭐ 澳大利亚地图去掉 SA 之后就是一棵树，枚举 SA 的 3 种颜色即可（割集条件），T 则是孤立点。
下一节 👉 16-不确定性下的推理.md