约束满足问题 — 打开状态的黑盒
这一章讲三件事: 把状态从「黑盒」拆成「变量(每个可从一组候选值里取一个)+取值」之后, 推断、启发式、问题结构分别能省下多少搜索;以及为什么有些 CSP 天生好解、有些天生无解。 读完你会拿到一组可以迁移到调度、排班、数独乃至概率推理(第 9 章)的通用技术。
1. 这一章讲什么
第 2 章的搜索算法看着每个状态都像一颗黑盒:想知道「这步之后是什么」, 必须写领域专用的代码。本章做一件小事却打开一个大世界:把状态写成 一组变量,每个变量取自己域里的值;当所有变量的取值满足所有约束,问题就解了。 满足这种形式的问题叫约束满足问题(CSP)1。
CSP 的算法因此有两个新武器:一看「哪些变量/取值组合违反约束」就能 一次性砍掉一大块搜索空间;二能直接从问题定义推导动作和转移模型, 不再手写2。
2. 顶层全景
定义:X(变量) · D(域) · C(约束 = 〈scope, rel〉)
解 = 一致 + 完整的赋值
│
┌───────────────┼───────────────────┐
▼ ▼ ▼
约束传播 回溯搜索 问题结构
(先推断) (推断与搜索交替) (图的形状定难度)
节点一致 选变量:MRV/度 独立子问题
弧一致 AC-3 选值:最少约束值 树状 CSP:线性!
路径一致 推断:前向检验/MAC 割集调整
k 一致/边界 回溯:冲突导向回跳 树分解与树宽
学习:no-good
│ │
└──── 局部搜索(最少冲突法):完整赋值空间里爬山
图说:三大支柱不是三选一,而是流水线——先传播、再按结构选路、最后才搜索; 最少冲突法是另一条「不搜索、只修复」的平行路线。
3. 核心原理
3.1 主走查:给澳大利亚上色
主走查的输入是一张澳大利亚地图,七个区域: X = {WA, NT, Q, NSW, V, SA, T},每个区域的域都是 {red, green, blue}, 约束是九条「相邻不同色」,比如 SA≠WA、SA≠NT…… SA 一个邻居都没漏, 它就是那个「邻居最多」的省3。
第一笔账,先看形式化本身值多少钱:一旦确定 SA=blue,它的 5 个邻居 立刻都不能取 blue。没有约束的搜索要考虑这 5 个变量的 3^5=243 种组合; 有约束,只剩 2^5=32 种——一步棋省掉 87% 的空间4。
第二笔账,看搜索怎么走。书里的走查顺序 WA、NT、Q……:
赋值 WA=red → 前向检验:从 NT、SA 的域里删掉 red
→ NT={green,blue}, SA={green,blue}
赋值 Q=green → 删 green → NT={blue}, SA={blue}, NSW={red,blue}
→ NT 和 SA 都只剩一种,零分支!
赋值 V=blue → 删 blue → SA 的域 = {} 空了 → 立刻回溯
第三步是这一章的灵魂:V=blue 之后 SA 变空,搜索根本没有「试完 SA 的 所有值」——是约束把失败提前报告了。这就是 CSP 与第 2 章黑盒搜索的 本质区别:书里的原话是,在原子搜索里你只能问「这个状态是目标吗?不是? 那下一个呢?」;而 CSP 能告诉你为什么不是,把聚焦点钉到关键变量上6。
3.2 约束传播:不等搜索,先做算术
约束传播的定义一句话:用约束减少一个变量的合法值,这又会减少另一个 变量的合法值,如此连锁——它可以与搜索交替,也可以作为预处理, 有时预处理本身就解出整个问题7。
一致性的四个强度等级:
| 等级 | 检查什么 | 例子 |
|---|---|---|
| 节点一致 | 一元约束 | SA 讨厌 green → 从域里删掉 |
| 弧一致 | 二元约束,逐条边 | Y=X²:X 收缩到 {0,1,2,3},Y 收缩到 {0,1,4,9} |
| 路径一致 | 借第三个变量收紧二元约束 | 两色澳大利亚:WA 与 SA 各自可行,但相对 NT 无解 |
| k 一致 | 任意 k 个变量 | 强 n 一致的 CSP 无需回溯即可解 |
弧一致的标准算法是 AC-3:维护一个待检查弧的队列;检查 (Xi,Xj) 时 把 Di 里「在 Dj 找不到搭档」的值删掉;只要 Di 变了,就把指向 Xi 的 所有弧塞回队列——因为 Xi 变小了,别人对它的约束可能也松了。 若某域变空,立即报告无解10。复杂度 O(cd³)(c 条弧、域大小 d)11。 顺带一个冷知识:「AC-3」的 3 是因为它是 Mackworth 论文里的第三个版本12。
弧一致有软肋。给澳大 利亚只发两色:每条弧单独看都满足(一红一蓝总凑得出), 但 WA、NT、SA 三省两两相邻,两色根本不够——路径一致就是为这种 「各自都行、合起来不行」准备的:检查 {WA,SA} 相对 NT,枚举(逐一列出)一致赋值 {WA=red,SA=blue} 与 {WA=blue,SA=red},发现 NT 两种颜色都会撞车, 于是这两组赋值全部被删除,问题当场判死13。
现实里常用的一条是边界传播:变量域用区间 [下界,上界] 表示。 两架航班容量 165 和 385,约束 F1(航班一)+F2(航班二)=420,边界传播直接把域缩成 D1=[35,165]、D2=[255,385]14。
3.3 回溯搜索:一次只给一个变量发牌
朴素地把深度受限搜索套到 CSP 上,会为「先赋 NSW 还是先赋 SA」 重复整棵子树。CSP 有个免费性质消掉它:可交换性——赋值顺序不影响结果, 所以每层只考虑「下一个变量取什么值」,叶节点从 n!·d^n 砍到 d^n15。
骨架定型为 Backtrack:选一个未赋值变量 → 按序试它的值 → 递归(对缩小后的问题调用同一过程)→ 失败就撤销。真正的学问在三个函数里16:
选变量(MRV): 选「剩余合法值最少」的变量,别名「失败优先」—— 它最可能马上失败,早失败早回头。走查里 WA=red、NT=green 落子后, SA 只剩一种合法值,MRV 立刻抓它:SA 一旦定了,Q、NSW、V 全部随之确定17。 MRV 的死穴是开局(大家都有 3 种颜色),此时用度启发式破局: 选约束到最多未赋值变量的那个——SA 度为 5,全场最大18。
选值(最少约束值): 变量选择失败优先,值选择恰恰相反——失败延后: 挑给邻居留下最多选择权的值。给 Q 上色时,blue 会吃掉 SA 最后的合法值, 所以先试 red19。
推断: 最轻的是前向检验——变量 X 落子后,把与 X 相邻的未赋值 变量里冲突的值删掉(主走查里每行都是它)。但它看不远:NT 和 SA 都只剩 blue 时它毫无察觉,哪怕这两省相邻。MAC(维持弧一致)补上: 每次赋值后就跑一遍 AC-3,严格强于前向检验——前向检验只处理队列的 初始弧,MAC 会递归传播20。
回溯: 朴素的时序回溯会闹笑话:按 Q、NSW、V、T、SA 顺序, SA 失败时它退回去给塔斯马尼亚换颜色——T 和 SA 根本不相邻, 换一万次也没用21。冲突导向回跳记下「谁的赋值害我失败」: SA 的冲突集是 {Q=red, NSW=green, V=blue},回跳就跳到其中最近的 V。 更妙的是把「共同致败」也记账:WA 与 NSW 合起来导致 NT、Q、V、SA 整段无解,就用公式 conf(Xi) ← conf(Xi) ∪ conf(Xj) − {Xi} 把冲突集 逐级合并,一路跳回 NSW22。失败的最小肇事集本身也值得存下来, 叫 no-good:再遇到同样的组合直接拒签——这是现代 CSP 求解器最重要的 效率技术之一23。
3.4 局部搜索: million queens in 50 steps
另一条路线干脆不做部分赋值:随机给完整赋值,然后反复 「挑一个冲突变量,改成冲突最少的值」——最少冲突启发式24。 它的战绩近乎滑稽:百万皇后问题,初始布局之后平均 50 步解出, 而且运行时间基本与问题规模无关25。哈勃太空望远镜的观测调度 用它把一周排程的计算从 3 周压到约 10 分钟26。 为什么这么猛?n 皇后的解密集地撒在整个状态空间上, 几乎随便乱走都能撞见一个——它是一个「欠约束」的问题。 配套的还有禁忌搜索(禁止回到最近访问过的状态)和约束加权 (违反过的约束提高权重(重要性分数)、罚得更狠,给平台区造出地形)27。
3.5 问题结构:图的形状就是难度
同一类问题,约束图的形状直接改写复杂度:
- 独立子问题:塔斯马尼亚与大陆不相连,两块各自上色再拼起来。 若每个连通分量只有常数 c 个变量,总工作量 O(d^c · n/c),对 n 线性—— 书里的对比:100 个变量的布尔 CSP 拆成 4 份,最坏求解时间 从宇宙寿命降到不到 1 秒28。
- 树状 CSP:约束图是树时,按拓扑排序做一遍定向弧一致 (O(nd²)),然后从根到叶每个变量随手取一个合法值即可,全程零回溯29。
- 割集调整:图「接近树」时,挑一小撮变量(环割集)枚举它们的所有取值, 每种取值下剩下的是树。割集大小 c 时总时间 O(d^c·(n−c)d²)—— c=20、n=100 的例子,从宇宙寿命降到几分钟30。
- 树分解:把图收拢成一棵「节点装变量组」的树;解的代价 O(nd^(w+1)),w 是树宽。书里的数字:每个树节点 10 个变量,几秒出解; 涨到 30 个变量,要几个世纪31。
值对称是最后一块免费的蛋糕:三色地图上 WA、NT、SA 换个颜色名还是同一个解, 3!=6 个解实为一个。加一条对称破缺约束(NT<SA<WA),空间直接除以 d!32。
4. 作者的判断与证据
- (书内实验) 百万皇后 50 步、哈勃 3 周→10 分钟、86%→94%(上一章) 都是可复现的统计结果2526。
- (书内定理) 树状 CSP 线性可解(Freuder 1985 系列工作); 树宽有界 ⟹ 多项式可解;最小环割集与最优树分解都是 NP 难33。
- (书内方法论) 「确定一致性检查的层级基本上是一门经验科学」—— 实践中常见 2 一致(弧一致),其次是 3 一致34。
- (作者的观察) 「困难」问题聚集在相变点附近:几乎所有随机 CSP 要么极易要么无解,恰在可解比例 50% 的参数带里藏着难题—— 书里把它记为 Cheeseman 等人的发现,并预告拆解 06 会再遇 SAT 的 4.3 峭壁35。
- (书内坦白) 「没有理论结果证明一种算法在所有问题上优于另一种」—— CSP 算法比较最终是经验科学36。
5. 边界与局限
- 弧一致不是万能的:书里明确给了反例——对澳大利亚三色问题 AC-3 什么也收缩不了(每条边单独看都可满足);数独里它也只能解最简单的, 稍难的要 PC-2(路径一致),需要考虑 255,960 条路径约束37。
- 全局约束(Alldiff)的专用推理比拆成二元约束高效,但需要为每类约束单独开发。
- 树分解的时间以 w 为指数;w 稍大就崩,而找最小分解本身 NP 难38。
- 最少冲突法在「解稀疏(解在状态空间里很分散)」的问题上会失去魔力——它的神话绑定了「解密集」。
6. 可带走的
- 把状态拆成变量+域+约束,你白拿三样东西:传播、通用启发式、结构分析。
- 先传播后搜索:每次赋值后跑 AC-3(MAC)几乎总比裸回溯强。
- 变量选择失败优先(MRV),值选择失败延后(最少约束值)—— 一句口诀,两个方向。
- 回跳的本质是记「谁害我」;no-good 的本质是「同样的坑不踩第二次」。
- 看到组合爆炸(局面数随规模暴涨)先看图:不连通就拆,是树就直接扫,接近树就割或分解。
- 遇到对称(换色、换名、换序)先破缺,空间按阶缩小。
- 欠约束问题反而要靠局部搜索——先问「解密吗?」再选算法。
7. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| CSP 定义(因子化) | 6 开篇 | text/10-fm.txt:6132(搜「因子化表示」) · text/10-fm.txt:6141(搜「3 个部分」) |
| 澳大利亚与 9 约束 | 6.1.1 | text/10-fm.txt:6159(搜「澳大利亚」) · text/10-fm.txt:6168(搜「SA WA」) |
| 87% 的账 | 6.1.1 | text/10-fm.txt:6179(搜「243」) |
| CSP 看得出为什么 | 6.1.1 | text/10-fm.txt:6187(搜「目标状态吗」) |
| 车间调度 | 6.1.2 | text/10-fm.txt:6198(搜「15 个任务」) · text/10-fm.txt:6218(搜「AxleB」) |
| 约束传播定义 | 6.2 | text/10-fm.txt:6302(搜「约束传播」) |
| 弧一致 Y=X² | 6.2.2 | text/10-fm.txt:6326(搜「Y = X 2」) |
| 两色失败 → 路径一致 | 6.2.3 | text/10-fm.txt:6374(搜「两种颜色」) · text/10-fm.txt:6383(搜「{WA, SA}」) |
| AC-3 | 6.2.2 | text/10-fm.txt:6335(搜「AC-3」) · text/10-fm.txt:6367(搜「第三个版本」) |
| O(cd³) | 6.2.2 | text/10-fm.txt:6371(搜「cd3」) |
| 边界传播 420 | 6.2.5 | text/10-fm.txt:6431(搜「165」) |
| 数独 E6 | 6.2.6 | text/10-fm.txt:6466(搜「E6」) · text/10-fm.txt:6478(搜「255 960」) |
| 可交换性 | 6.3 | text/10-fm.txt:6502(搜「可交换性」) |
| MRV 例子 | 6.3.1 | text/10-fm.txt:6554(搜「SA 只有一个」) · text/10-fm.txt:6556(搜「最少剩余值」) |
| 度启发式 | 6.3.1 | text/10-fm.txt:6562(搜「度启发式」) |
| 最少约束值 | 6.3.1 | text/10-fm.txt:6567(搜「最少约束值」) |
| 前向检验走查 | 6.3.2 | text/10-fm.txt:6172(搜「WA = red」) · text/10-fm.txt:6592(搜「没有合法值」) |
| 前向检验盲区与 MAC | 6.3.2 | text/10-fm.txt:6600(搜「前向检验能够检测出」) · text/10-fm.txt:6603(搜「MAC」) |
| 塔斯马尼亚笑话 | 6.3.3 | text/10-fm.txt:6618(搜「塔斯马尼亚州」) |
| 冲突集与回跳 | 6.3.3 | text/10-fm.txt:6623(搜「冲突集」) · text/10-fm.txt:6874(搜「冲突导向回跳」) |
| 冲突集合并公式 | 6.3.3 | text/10-fm.txt:6658(搜「conf(Xi)」) |
| no-good | 6.3.4 | text/10-fm.txt:6660(搜「约束学习」) · text/10-fm.txt:6674(搜「最重要技术之一」) |
| 最少冲突法 | 6.4 | text/10-fm.txt:6682(搜「最少冲突」) |
| 百万皇后 50 步 | 6.4 | text/10-fm.txt:6710(搜「百万皇后」) · text/10-fm.txt:6710(搜「50 步」) |
| 哈勃 3 周→10 分钟 | 6.4 | text/10-fm.txt:6713(搜「哈勃」) |
| 禁忌与约束加权 | 6.4 | text/10-fm.txt:6718(搜「禁忌搜索」) · text/10-fm.txt:6720(搜「约束加权」) |
| 独立 子问题 1 秒 | 6.5 | text/10-fm.txt:6738(搜「独立子问题」) · text/10-fm.txt:6746(搜「1 秒」) |
| 树状 CSP | 6.5 | text/10-fm.txt:6748(搜「树状结构」) · text/10-fm.txt:6759(搜「不必回溯」) |
| 割集调整 | 6.5.1 | text/10-fm.txt:6801(搜「环割集」) · text/10-fm.txt:6811(搜「几分钟」) |
| 树分解与树宽 | 6.5.2 | text/10-fm.txt:6816(搜「树分解」) · text/10-fm.txt:6841(搜「几秒」) · text/10-fm.txt:6843(搜「树宽」) |
| 值对称 | 6.5.3 | text/10-fm.txt:6857(搜「值对称」) |
| 相变与难题 | 参考文献 | text/10-fm.txt:1192(搜「困难」) |
| 经验科学 | 参考文献 | text/10-fm.txt:6992(搜「经验科学」) |