🏠 总目录📚 本教程 15 · CSP 的启发式 ← →

变量先选最紧的,取值却为何选最宽松的?

读后可检查:用原小例子区分 MRV 与 LCV,再检查搜索次数和真实耗时并不等价。

📑 本页目录(点开跳转)

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 全部并列。我们固定使用下面三层规则,避免手算与程序各走各的:

  1. 先选当前合法值最少的变量。
  2. 若并列,选未赋值邻居最多的变量,这叫度启发(degree heuristic)。
  3. 若仍并列,按 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 试值
8876572
123,0661,770
16160,712584
203,992,5102,710
249,878,316756

先看 16 皇后这一行:160,712 / 584 约为 275。 这是候选次数之比,不是“程序快了 275 倍”。

结果 B:多少次递归最终失败

皇后数静态序回溯MRV 回溯
810567
12249141
1610,03628
20199,615125
24411,58419

这组固定顺序下 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)改用完整但可能违约的赋值作为起点,每次修一个位置。

  1. 为所有变量准备一个完整赋值。可以随机生成,也可以用贪心办法减少初始冲突。
  2. 若所有约束都满足,返回答案;否则随机选一个正在冲突中的变量。
  3. 尝试该变量的各个值,选择违约数最少的值,并列时随机选择。
  4. 重复检查与修复;到达预设预算仍未成功,则报告“本次未找到”,按需重启。

这四步中的预算不能省掉:允许同分移动也可能在平台上反复游走。未找到解不等于无解。 AIMA 的实现包含贪心初始赋值、随机破并列和最大步数限制。

“百万皇后几十步”到底指什么

这是文献实验,不是上方回溯程序的实测。Minton 等人的实验先用贪心方法建立较少冲突的棋盘,再统计修复阶段;其大规模皇后实验的平均修复次数约为几十次。原论文 §4.1

一次修复不等于一次常数时间操作。 要判断一个皇后移到哪列更好,仍可能检查多个位置;初始化、选择、更新也都要耗时。原论文明确区分修复次数与运行时间。

所以不能把它读成“任意随机棋盘只要几十次操作就能解”,更不能推出所有 CSP 都有相同表现。初始化方法、约束结构和搜索空间都很重要,单说“解很稠密”解释不了保证从哪里来——这里本来就没有这种保证。

它适合放在哪里

排班或调度发生小变化时,可以把旧排表当作初始完整赋值,只修新出现的冲突。这是一种可尝试的策略,不保证比重新搜索更快,也不保证修改后的问题仍有解。

它与第 9 章势场法可作有限类比:都依靠局部信息推进,也可能停滞。但离散赋值修复与连续空间里的运动不是同一个算法,不能称为完全同构。

🌳 六、利用约束图结构

这里暂限于有限域、二元约束的 CSP。n 是变量数,d 是最大域大小,并假设检查一对取值是否兼容只需常数时间。

无环:先删去没有支持的值,再依次赋值

如果约束图是一棵树,可任选一个根;如果是森林,则对每个连通部分各选一个根。

先从叶子向根处理边:父节点某个值在子节点域里找不到兼容值,就删除这个父值。出现空域就判无解;所有域都非空,才进入赋值。

然后从根往叶子选值,每个孩子选一个与父值兼容的值。前一步已经保证这样的支持存在,因此这一阶段无需回溯。标准复杂度为 $O(nd^2)$,不是“树结构一定有解”。

有少量环:先固定割集,不能把约束丢掉

割集条件化(cutset conditioning)先选出一些变量,使它们离开图后剩下的是森林。再逐个枚举割集赋值,检查它们互相之间的约束,并用这些赋值缩小其余变量的域。

澳大利亚例子只需固定 SA。若试 SA = 红,它的五个邻居都不能再用红;剩余图如下:

SA 已固定为红;相邻节点的域均删去红 WANT QNSW VT 上方四条边仍要求相邻区域异色 独立部分,仍可选三色
这里有两个连通部分,不是一棵连通的树。 上方的链可用绿、蓝交替着色;T 没有边,单独处理。

SA 另外两种颜色也可以对称处理,所以这张三色地图的三个割集赋值都可补全。换一个 CSP,某个割集赋值可能让剩余问题无解,必须换下一个,不能预先承诺成功。

若割集有 c 个变量,至多尝试 $d^c$ 个赋值;每次还要付出检查割集、缩域和解森林的成本。“环被移走”不是这些约束被取消了。树结构与割集算法

环更多:树分解把交叠关系保留下来

树分解不是随便分组。它把变量装入若干可重叠的“袋子”,让袋子之间构成树,并要求:

  • 每个变量至少出现在一个袋子里。
  • 每条二元约束的两个端点至少同处一个袋子。
  • 同一变量出现的那些袋子在袋子树上必须连通。

每袋可枚举局部赋值,袋子之间通过重叠变量核对一致性。这才是把小块视作“超级变量”的含义;重叠部分不能各填各的。

成本通常对最大袋子的大小呈指数增长。块小才可能有帮助,不是任意约束图一分组就变容易。 树分解定义与求解成本

🔗 这一章连到哪里

去哪 为什么
14 · 回溯与约束传播 看相同地图的静态对照,并区分“改变赋值顺序”和“传播删值”。
13 · CSP 是什么 回看变量、值域、九条地图约束,以及孤立点 T。
09 · 运动规划 对比局部推进的停滞风险;别把两个算法当成同一回事。
07 · 启发式与 A* A* 的 h 是剩余代价估计,可讨论可容许性;这里的 MRV/LCV 是搜索次序规则,没有同一个可容许性定义。
16 · 不确定性下的推理 普通 CSP 用确定的硬约束判断可行性;下一章转向如何表达和使用不确定信息。

✅ 检查点

  1. MRV 在数什么?如果某变量当前合法域为空,为什么应尽早处理?
  2. MRV 并列时,本章怎样继续选?度数要不要包含已经赋值的邻居?
  3. 地图中前两个变量是谁?为什么第三个是 Q,不是 WA?本次回溯几次?
  4. LCV 的三邻居例子里,红和蓝各删几个选项?本例为什么能另外证明两分支都有解,而一般的 LCV 分数不能保证?
  5. MRV 和 LCV 为什么不矛盾?能否分别称为最坏与最好情况的复杂度保证?
  6. 16 皇后试值减少多少?为何不能当成相同倍率的运行提速?
  7. 最小冲突的四步是什么?它持有完整赋值还是部分赋值?
  8. 最小冲突为什么不完备?它与势场法是完全同构吗?
  9. 百万皇后文献里的“几十步”数的是什么?为什么不能直接外推?
  10. 树结构算法何时报告无解?固定 SA 后怎样处理剩余图?
👀 答案
  1. 数未赋值变量在当前状态下的合法取值。空域表示当前分支已不能补全,可以避免继续探索;剩一个值也只是在当前分支下被迫取值,不保证后续无矛盾。
  2. 先比较未赋值邻居数,再按固定原顺序破并列。已经赋值的邻居不再计入本章的度启发。
  3. 先 SA,再 NT。第三步 WA、Q 都剩一个值,但 Q 还有未赋值邻居 NSW,WA 没有,所以选 Q。本次 15 次试值、0 次失败返回;T 最后仍有三个选择。
  4. 红删 3 个,蓝删 1 个,因此 LCV 先试蓝。本例邻居之间没有边,可分别组合剩余取值:选蓝有 8 个补全,选红有 2 个,所以两分支都有解。这个证明依赖完整已知的星形约束结构;一般 LCV 分数不考虑所有后续组合,不能保证有解或给出成功概率。
  5. 一个选变量,一个排值序,都改变搜索展开次序。尽早暴露矛盾与少妨碍邻居可以配合,但不是两种复杂度保证。
  6. 从 160,712 到 584,候选次数之比约为 275。MRV 额外重算合法域;本页 8 皇后甚至出现试值少、兼容性检查多的情况。五个规模也不足以证明一般增长曲线。
  7. 准备完整赋值;检查是否完成并选冲突变量;改成冲突最少的值;重复至成功或预算用完。它在完整赋值之间修复,不是逐层扩展部分赋值。
  8. 它可能停滞或反复游走,预算用完只能说本次未找到,不能证明无解。与势场法只能类比局部信息与停滞风险,不能称为同一个算法。
  9. 数特定贪心初始化之后的修复次数,不是初始化加修复的所有操作数,也不是恒定耗时。问题结构、初始化和实现都影响表现。
  10. 从叶到根删无支持值时若出现空域,就报告无解;否则可从根到叶无回溯赋值。固定 SA 后仍需从五个邻居域中删其颜色,再分别解剩余链和孤立点 T。

本节回顾

⚡ 走神救援

  • MRV:先选当前合法值少的变量;并列规则也要说清。
  • LCV:先试少删邻居选项的值,不是成功概率保证。
  • 次数减少不等于同倍率提速,启发式计算本身也有成本。
  • 最小冲突修完整赋值;没找到不等于无解。
  • 无环结构能简化求解;固定割集后,关联约束仍须生效。

如果只想会选变量和值,看到这里就够了。需要验证实现时回到复算程序,需要区分 MRV 与传播时回到第 14 章。

下一节 👉 16-不确定性下的推理.md

打卡记录保存在你的浏览器里,首页能看到总进度