15 · CSP 的启发式
⏱ 31 分钟 | ⭐ 约束不变,改变的是先填谁、先试什么
时间只是阅读参考。先走完地图例子;想复算次数,再打开实验代码。
🎯 一句话
MRV 先选余地最小的变量,LCV 先试给邻居留下余地的值。 它们改变搜索顺序,不改变哪些完整答案算合法。
在本章固定的地图实验中,静态顺序需要试值 17 次、失败返回 2 次;MRV 配合度启发后是 15 次、0 次。这个小结果不是“总能提速一个数量级”的保证。
🎯 一、变量序:先处理选择少的变量
这里的“变量”是一块待涂色的区域,“值”是红、绿、蓝。相邻区域不能同色;地图和九条约束沿用第 13 章。
第 14 章按 WA、NT、NSW、Q、SA、V、T 的静态顺序搜索。它曾走到 SA 没颜色可用的分支,但变量顺序没有让整个问题变成无解;回溯后仍找得到解。
MRV(Minimum Remaining Values,最小剩余值)每一步都重新问:在当前赋值下,哪个未赋值变量还能选的值最少?
⚠️ “先失败”是在尽早发现什么
假设两个变量中,甲还剩 3 个合法值,乙已经剩 0 个。此时继续试甲没有意义:当前分支已经不可能补全,应该直接返回。
乙若剩 1 个值,它在当前分支下是被迫取这个值。先填它可能进一步缩小问题,但后面仍可能出现矛盾,不能因此宣布已经找到解。
这就是 fail-first(尽早暴露失败)的直觉。MRV 也要花时间计算合法域,不能保证每个实例都比静态顺序省时。算法定义与取值排序
🔨 手算:先把所有并列规则说清楚
初始七块区域各有 3 个颜色,MRV 全部并列。我们固定使用下面三层规则,避免手算与程序各走各的:
- 先选当前合法值最少的变量。
- 若并列,选未赋值邻居最多的变量,这叫度启发(degree heuristic)。
- 若仍并列,按 WA、NT、NSW、Q、SA、V、T 的原顺序选。颜色始终按红、绿、蓝试,本例尚未使用 LCV。
| 本步赋值 | 为什么轮到它 |
|---|---|
| ① SA = 红 | 所有域大小都是 3;SA 有 5 个未赋值邻居,最多。 |
| ② NT = 绿 | SA 的五个邻居都剩绿、蓝;NT、Q、NSW 各有 2 个未赋值邻居,再按原顺序选 NT。 |
| ③ Q = 蓝 | WA 和 Q 都只剩蓝;Q 还连着未赋值的 NSW,WA 已无未赋值邻居,因此选 Q。 |
| ④ NSW = 绿 | WA、NSW 都只剩 1 个值;NSW 还连着未赋值的 V,因此先选它。 |
| ⑤ WA = 蓝 | WA、V 都剩蓝,未赋值邻居数也都为 0,原顺序让 WA 在前。 |
| ⑥ V = 蓝 | V 剩 1 个值,T 仍有 3 个。 |
| ⑦ T = 红 | T 是孤立点,三种颜色都合法;按颜色顺序选红。 |
看第 ③ 步:只剩一个值的并不只有 WA。 度数也必须在每一步重新计算,不能继续把已经填好的 SA 算成 NT 的未赋值邻居。
此处找到首个解时没有失败返回,但 T 最后仍有三个选择。“这条轨迹没有回溯”不等于“从此每一步都只有唯一选择”。
🎨 二、值序:用一个完整小例子看 LCV
选好变量后,还要决定它先试哪个值。LCV(Least Constraining Value,最少约束值)通常先试从未赋值邻居的当前域里排除选项最少的值。
这是一个独立的小型着色 CSP,不是刚才地图轨迹的续步:中心变量 X 可选红、蓝,只与 A、B、C 三个邻居分别有“不等色”约束,邻居之间没有边。
| 邻居 | 当前域 |
|---|---|
| A | 红、绿 |
| B | 红、蓝、绿 |
| C | 红、绿 |
- 试 X = 红:A、B、C 各失去一个红色选项,共删 3 个。
- 试 X = 蓝:只有 B 失去蓝色,共删 1 个。
LCV 会先试蓝。 这个分数只表示眼前少删了几个选项,不是成功概率;在一般 CSP 中,它不能保证这条分支有解。
本例还能另做一步确切判断:因为 A、B、C 之间没有约束,选蓝后各有 2 个值,共有 $2\times2\times2=8$ 个补全;选红后有 $1\times2\times1=2$ 个。两分支都有解,是已知星形结构让我们证明了它,不是 LCV 分数自动给出保证。
打分也有成本;它常与 MRV、前向检查组合,但这些是可分别开关的选择。本章后面的计数实验只比较变量顺序,不加入 LCV。
⚠️ 三、为什么一个挑“紧”,一个挑“松”
两种规则问的不是同一个问题:
| 决策 | 眼前目标 |
|---|---|
| MRV:下一步填哪个变量? | 优先处理选择少的变量,争取及早暴露当前分支的矛盾。 |
| LCV:这个变量先试哪个值? | 尽量少删除邻居选项,争取较快找到一个可行补全。 |
在普通有限 CSP 的回溯搜索里,变量迟早都要填完,而同一变量的不同值会形成不同分支。它们都在改变搜索树的展开顺序。
因此,不宜说“变量序决定要不要搜索、值序才决定走哪条分支”,也不能把它们分别称为最坏情况和最好情况的复杂度优化定理。
如果每个分支都被正确保留或安全剪掉,有限回溯搜索的完备性仍在;MRV、LCV 本身不是“无解证明”。
📊 四、n 皇后实验:次数减少,不等于同倍率提速
模型保持不变:每一行是一个变量,该行皇后所在的列是值;任意两行不能同列,也不能处在同一条对角线上。
只找第一个解。静态序从第 0 行往下填;MRV 每次重算当前合法域。皇后约束图中所有未赋值行互相连接,度启发无法再破并列,于是按行号从小到大选。列号也从小到大试。
先约定怎样计数
试值次数:程序进入一次候选值循环就加一,即使这个值随即被判不合法,也计入。
回溯次数:一次递归调用试完当前变量的所有候选、仍失败返回,才加一。它不是撤销赋值次数,也不是检查约束次数。这与第 14 章的实验口径一致。
MRV 在挑变量时额外做的合法性检查不计入“试值”,但代码另有 checks 计数,不让这部分成本消失。
结果 A:检查了多少个候选值
下表已按本页算法重新运行,保留原实验的五个规模与计数:
| 皇后数 | 静态序试值 | MRV 试值 |
|---|---|---|
| 8 | 876 | 572 |
| 12 | 3,066 | 1,770 |
| 16 | 160,712 | 584 |
| 20 | 3,992,510 | 2,710 |
| 24 | 9,878,316 | 756 |
先看 16 皇后这一行:160,712 / 584 约为 275。 这是候选次数之比,不是“程序快了 275 倍”。
结果 B:多少次递归最终失败
| 皇后数 | 静态序回溯 | MRV 回溯 |
|---|---|---|
| 8 | 105 | 67 |
| 12 | 249 | 141 |
| 16 | 10,036 | 28 |
| 20 | 199,615 | 125 |
| 24 | 411,584 | 19 |
这组固定顺序下 MRV 减少了失败探索,但五个规模不能证明一般增长率。MRV 的试值也不单调:584、2,710、756 先升后降。
再看一次隐藏成本: 8 皇后的静态序做了 2,438 次两变量兼容性检查,MRV 做了 6,868 次,虽然 MRV 的候选试值更少。这说明计数口径不同,结论也可能不同。
按需运行:复算地图与皇后
下面是完整 Python 程序,只需标准库,不依赖前面的代码或变量。默认跑 8、12、16 皇后;想复算整张表,把最后的规模列表补上 20、24。
运行后,地图两行应分别出现 static 17 2、MRV 15 0;皇后行最后三列是“试值、回溯、兼容性检查”。不同机器的耗时可以不同,但这里没有随机数,固定算法下计数应一致。
打开完整可运行代码:同一个求解器,只切换变量顺序
def solve(variables, domains, neighbors, compatible, use_mrv):
assigned = {}
stats = {"trials": 0, "backtracks": 0, "checks": 0}
rank = {var: i for i, var in enumerate(variables)}
def legal(var, value):
for other, chosen in assigned.items():
if other in neighbors[var]:
stats["checks"] += 1
if not compatible(var, value, other, chosen):
return False
return True
def search():
if len(assigned) == len(variables):
return assigned.copy()
remaining = [v for v in variables if v not in assigned]
if use_mrv:
# MRV: recompute legal domains; degree counts unassigned neighbors.
var = min(remaining, key=lambda v: (
sum(legal(v, x) for x in domains[v]),
-sum(u not in assigned for u in neighbors[v]),
rank[v],
))
else:
var = remaining[0]
# Deliberately count EVERY original candidate, including illegal ones.
for value in domains[var]:
stats["trials"] += 1
if legal(var, value):
assigned[var] = value
answer = search()
if answer is not None:
return answer
del assigned[var]
stats["backtracks"] += 1 # One failed recursive call, not one undo.
return None
answer = search()
if answer is not None:
assert all(answer[v] in domains[v] for v in variables)
assert all(compatible(v, answer[v], u, answer[u])
for v in variables for u in neighbors[v])
return answer, stats
order = ["WA", "NT", "NSW", "Q", "SA", "V", "T"]
edges = [("WA", "NT"), ("WA", "SA"), ("NT", "SA"), ("NT", "Q"),
("SA", "Q"), ("SA", "NSW"), ("SA", "V"), ("Q", "NSW"),
("NSW", "V")]
neighbors = {v: set() for v in order}
for a, b in edges:
neighbors[a].add(b)
neighbors[b].add(a)
domains = {v: ["red", "green", "blue"] for v in order}
for mrv in [False, True]:
answer, stats = solve(order, domains, neighbors,
lambda a, x, b, y: x != y, mrv)
assert answer is not None
print("map", "MRV" if mrv else "static",
stats["trials"], stats["backtracks"], list(answer.items()))
# 8/12/16 are enough for a first comparison; add 20, 24 for the full table.
for n in [8, 12, 16]:
rows = list(range(n))
domains = {r: list(range(n)) for r in rows}
neighbors = {r: set(rows) - {r} for r in rows}
def compatible(a, x, b, y):
return x != y and abs(a - b) != abs(x - y)
for mrv in [False, True]:
answer, stats = solve(rows, domains, neighbors, compatible, mrv)
assert answer is not None
print(n, "MRV" if mrv else "static",
stats["trials"], stats["backtracks"], stats["checks"])
代码中的 legal 只与已赋值邻居检查;use_mrv 改变选变量的规则;search 找到首解就返回。两组都没有维护删值后的域,也没有前向检查。 不要把这一列与第 14 章 FC 的次数当成只差变量顺序的实验。
🔄 五、最小冲突:先有完整候选,再修它
前面的回溯搜索逐步构造一个部分赋值。最小冲突(min-conflicts)改用完整但可能违约的赋值作为起点,每次修一个位置。
- 为所有变量准备一个完整赋值。可以随机生成,也可以用贪心办法减少初始冲突。
- 若所有约束都满足,返回答案;否则随机选一个正在冲突中的变量。
- 尝试该变量的各个值,选择违约数最少的值,并列时随机选择。
- 重复检查与修复;到达预设预算仍未成功,则报告“本次未找到”,按需重启。
这四步中的预算不能省掉:允许同分移动也可能在平台上反复游走。未找到解不等于无解。 AIMA 的实现包含贪心初始赋值、随机破并列和最大步数限制。
“百万皇后几十步”到底指什么
这是文献实验,不是上方回溯程序的实测。Minton 等人的实验先用贪心方法建立较少冲突的棋盘,再统计修复阶段;其大规模皇后实验的平均修复次数约为几十次。原论文 §4.1
一次修复不等于一次常数时间操作。 要判断一个皇后移到哪列更好,仍可能检查多个位置;初始化、选择、更新也都要耗时。原论文明确区分修复次数与运行时间。
所以不能把它读成“任意随机棋盘只要几十次操作就能解”,更不能推出所有 CSP 都有相同表现。初始化方法、约束结构和搜索空间都很重要,单说“解很稠密”解释不了保证从哪里来——这里本来就没有这种保证。
它适合放在哪里
排班或调度发生小变化时,可以把旧排表当作初始完整赋值,只修新出现的冲突。这是一种可尝试的策略,不保证比重新搜索更快,也不保证修改后的问题仍有解。
它与第 9 章势场法可作有限类比:都依靠局部信息推进,也可能停滞。但离散赋值修复与连续空间里的运动不是同一个算法,不能称为完全同构。
🌳 六、利用约束图结构
这里暂限于有限域、二元约束的 CSP。n 是变量数,d 是最大域大小,并假设检查一对取值是否兼容只需常数时间。
无环:先删去没有支持的值,再依次赋值
如果约束图是一棵树,可任选一个根;如果是森林,则对每个连通部分各选一个根。
先从叶子向根处理边:父节点某个值在子节点域里找不到兼容值,就删除这个父值。出现空域就判无解;所有域都非空,才进入赋值。
然后从根往叶子选值,每个孩子选一个与父值兼容的值。前一步已经保证这样的支持存在,因此这一阶段无需回溯。标准复杂度为 $O(nd^2)$,不是“树结构一定有解”。
有少量环:先固定割集,不能把约束丢掉
割集条件化(cutset conditioning)先选出一些变量,使它们离开图后剩下的是森林。再逐个枚举割集赋值,检查它们互相之间的约束,并用这些赋值缩小其余变量的域。
澳大利亚例子只需固定 SA。若试 SA = 红,它的五个邻居都不能再用红;剩余图如下:
SA 另外两种颜色也可以对称处理,所以这张三色地图的三个割集赋值都可补全。换一个 CSP,某个割集赋值可能让剩余问题无解,必须换下一个,不能预先承诺成功。
若割集有 c 个变量,至多尝试 $d^c$ 个赋值;每次还要付出检查割集、缩域和解森林的成本。“环被移走”不是这些约束被取消了。树结构与割集算法
环更多:树分解把交叠关系保留下来
树分解不是随便分组。它把变量装入若干可重叠的“袋子”,让袋子之间构成树,并要求:
- 每个变量至少出现在一个袋子里。
- 每条二元约束的两个端点至少同处一个袋子。
- 同一变量出现的那些袋子在袋子树上必须连通。
每袋可枚举局部赋值,袋子之间通过重叠变量核对一致性。这才是把小块视作“超级变量”的含义;重叠部分不能各填各的。
成本通常对最大袋子的大小呈指数增长。块小才可能有帮助,不是任意约束图一分组就变容易。 树分解定义与求解成本
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 14 · 回溯与约束传播 | 看相同地图的静态对照,并区分“改变赋值顺序”和“传播删值”。 |
| 13 · CSP 是什么 | 回看变量、值域、九条地图约束,以及孤立点 T。 |
| 09 · 运动规划 | 对比局部推进的停滞风险;别把两个算法当成同一回事。 |
| 07 · 启发式与 A* | A* 的 h 是剩余代价估计,可讨论可容许性;这里的 MRV/LCV 是搜索次序规则,没有同一个可容许性定义。 |
| 16 · 不确定性下的推理 | 普通 CSP 用确定的硬约束判断可行性;下一章转向如何表达和使用不确定信息。 |
✅ 检查点
- MRV 在数什么?如果某变量当前合法域为空,为什么应尽早处理?
- MRV 并列时,本章怎样继续选?度数要不要包含已经赋值的邻居?
- 地图中前两个变量是谁?为什么第三个是 Q,不是 WA?本次回溯几次?
- LCV 的三邻居例子里,红和蓝各删几个选项?本例为什么能另外证明两分支都有解,而一般的 LCV 分数不能保证?
- MRV 和 LCV 为什么不矛盾?能否分别称为最坏与最好情况的复杂度保证?
- 16 皇后试值减少多少?为何不能当成相同倍率的运行提速?
- 最小冲突的四步是什么?它持有完整赋值还是部分赋值?
- 最小冲突为什么不完备?它与势场法是完全同构吗?
- 百万皇后文献里的“几十步”数的是什么?为什么不能直接外推?
- 树结构算法何时报告无解?固定 SA 后怎样处理剩余图?
👀 答案
- 数未赋值变量在当前状态下的合法取值。空域表示当前分支已不能补全,可以避免继续探索;剩一个值也只是在当前分支下被迫取值,不保证后续无矛盾。
- 先比较未赋值邻居数,再按固定原顺序破并列。已经赋值的邻居不再计入本章的度启发。
- 先 SA,再 NT。第三步 WA、Q 都剩一个值,但 Q 还有未赋值邻居 NSW,WA 没有,所以选 Q。本次 15 次试值、0 次失败返回;T 最后仍有三个选择。
- 红删 3 个,蓝删 1 个,因此 LCV 先试蓝。本例邻居之间没有边,可分别组合剩余取值:选蓝有 8 个补全,选红有 2 个,所以两分支都有解。这个证明依赖完整已知的星形约束结构;一般 LCV 分数不考虑所有后续组合,不能保证有解或给出成功概率。
- 一个选变量,一个排值序,都改变搜索展开次序。尽早暴露矛盾与少妨碍邻居可以配合,但不是两种复杂度保证。
- 从 160,712 到 584,候选次数之比约为 275。MRV 额外重算合法域;本页 8 皇后甚至出现试值少、兼容性检查多的情况。五个规模也不足以证明一般增长曲线。
- 准备完整赋值;检查是否完成并选冲突变量;改成冲突最少的值;重复至成功或预算用完。它在完整赋值之间修复,不是逐层扩展部分赋值。
- 它可能停滞或反复游走,预算用完只能说本次未找到,不能证明无解。与势场法只能类比局部信息与停滞风险,不能称为同一个算法。
- 数特定贪心初始化之后的修复次数,不是初始化加修复的所有操作数,也不是恒定耗时。问题结构、初始化和实现都影响表现。
- 从叶到根删无支持值时若出现空域,就报告无解;否则可从根到叶无回溯赋值。固定 SA 后仍需从五个邻居域中删其颜色,再分别解剩余链和孤立点 T。
本节回顾
⚡ 走神救援
- MRV:先选当前合法值少的变量;并列规则也要说清。
- LCV:先试少删邻居选项的值,不是成功概率保证。
- 次数减少不等于同倍率提速,启发式计算本身也有成本。
- 最小冲突修完整赋值;没找到不等于无解。
- 无环结构能简化求解;固定割集后,关联约束仍须生效。
如果只想会选变量和值,看到这里就够了。需要验证实现时回到复算程序,需要区分 MRV 与传播时回到第 14 章。
下一节 👉 16-不确定性下的推理.md