约束满足与地图着色

给一张地图着色，让相邻的两个区域颜色不同。这听起来像下雨天打发时间的小游戏，却是约束满足问题的标准入门例子，因为同一套方法也能排考试时间表、分配房间、填数独。这篇笔记跟着一个回溯搜索给地图着色，并讲清楚让它变快的两个小想法。

基本想法

约束满足问题（CSP）有三个部分：变量、每个变量可能取值的论域，以及规定哪些组合被允许的约束。在地图着色里，变量是区域，论域是颜色的集合，每一条共享边界都是一条约束，要求两边颜色不同。一个解就是给每个变量一个值，而且不违反任何约束。人工智能主题把 CSP 和搜索、逻辑放在一起讲。

教科书用的地图是澳大利亚本土加上塔斯马尼亚，用三种颜色。南澳和另外五个州区相邻，所以最难安排。塔斯马尼亚不和任何州区相邻，什么时候取什么颜色都行。通常的版本不画首都领地，加上它也不会改变什么，因为它只和新南威尔士相邻。

回溯搜索一次给一个区域着色。当某个区域已经没有合法颜色可选时，它撤销最近的一次选择，换那个区域的下一个颜色。这是在部分着色上做深度优先搜索，它从不把所有可能着色的整棵树建出来，因为一出现冲突就放弃这条分支。

有两个想法让它变快。变量排序决定下一个给哪个区域着色。最少剩余值规则 MRV 选剩下合法颜色最少的区域，这样注定失败的分支会早早失败，而不是绕一大圈之后才失败。推理在每次选择后往前看一步。前向检查从每个还没着色的邻居那里删掉刚用的颜色，一旦某个邻居没有颜色可选，就立刻回退。

对平面地图来说，四种颜色永远够用。Appel 和 Haken 在 1976 年证明了这一点，用计算机检查了所有情形，这是第一个需要计算机才能完成证明的重大定理。三种颜色不一定够，而判断三种颜色够不够是 NP 完全问题，平面地图也不例外。

数学

把地图写成一个图。每个区域是一个变量 $X_i$ ，每条共享边界是 $E$ 里的一条边，每个变量取 $k$ 种颜色之一。

\mathcal{X} = \{X_1, \dots, X_n\}, \qquad D_i = \{1, \dots, k\}, \qquad \mathcal{C} = \{\, X_i \ne X_j : (i, j) \in E \,\}

完整的着色一共有 kⁿ 种。回溯搜索边走边检查约束，所以在大多数地图上只会访问其中很小的一部分。

给定一个部分着色 $\sigma$ ，一个区域的合法颜色 $L_i$ 就是它的论域减去邻居已经用掉的颜色。MRV 接下来给 $L_i$ 最小的区域着色，平局时选还没着色的邻居最多的那个，也就是度规则。

L_i = D_i \setminus \{\, \sigma(X_j) : (i, j) \in E,\ X_j \text{ coloured} \,\}, \qquad \text{next} = \arg\min_{X_i \text{ uncoloured}} \lvert L_i \rvert

Haralick 和 Elliott 把这叫作“先失败”：如果一个区域注定会失败，就尽早发现。

前向检查让论域本身随时保持最新。一个区域取了颜色 $c$ 之后，每个未着色的邻居都失去 $c$ ，某个论域一旦变空，就说明这条分支在搜索走进去之前已经死了。

X_i \leftarrow c \;\Longrightarrow\; D_j \leftarrow D_j \setminus \{c\} \ \text{ for every uncoloured neighbour } X_j, \qquad \text{back up if some } D_j = \varnothing

回退的时候，每一个论域都要恢复，而不只是被撤销的那个区域。

弧相容又往前走了一步。Mackworth 的 AC-3 不断删除那些在某个邻居里找不到相容值的取值，直到没有变化为止。前向检查是它的廉价版本，只看刚着色区域隔着一条边界的邻居。

动手试

下面的工具在网格上画一张最多 16 个区域的虚构地图，用回溯搜索给它着色。整个搜索过程先记录下来，所以你可以一步步走、拖动步骤滑块，或者直接播放，汇总数字还能比较不同设置。

地图上的区域数16

颜色数

先选最受约束的区域（MRV）前向检查

种子 3

步骤第 1 步，共 869 步

每个区域还能取的颜色

A已着色为红
B还能取红、墨、灰
C还能取红、墨、灰
D还能取红、墨、灰
E还能取红、墨、灰
F还能取红、墨、灰
G还能取红、墨、灰
H还能取红、墨、灰
I还能取红、墨、灰
J还能取红、墨、灰
K还能取红、墨、灰
L还能取红、墨、灰
M还能取红、墨、灰
N还能取红、墨、灰
O还能取红、墨、灰
P还能取红、墨、灰

划掉的色块已被排除，原因是相邻区域用了这个颜色，或者前向检查把它删掉了。

第 1 步。 A 着色为红。到这一步为止：着色 1 次，回退 0 次。

整个搜索：着色 382 次，回退 366 次。找到了一种着色。

地图是 24 × 14 网格上带种子的 Voronoi 区域。颜色分别是红、墨、灰和点状，任何状态都不只靠颜色区分。

先用普通回溯、三种颜色。跳到最后：找到着色之前，着色 382 次，回退 366 次。
勾上 MRV。同一张地图只要着色 16 次，一次回退都没有，每个区域一次。
取消 MRV，勾上前向检查。结果介于两者之间：着色 73 次，回退 57 次。
两个都勾上。次数和只用 MRV 一样，因为 MRV 本来就在数每个区域的合法颜色，下一次挑选时就能发现已经无色可选的区域。
改成两种颜色。普通回溯要着色 46 次才能证明不存在可行的着色，MRV 只要 4 次。再在三种颜色下多按几次“换一张地图”。有些地图用三种颜色根本涂不了，普通回溯有时还会先撞上步数上限。用四种颜色，每张地图都能涂。

我在哪用到它

容易出错的地方

五个陷阱

回退时撤销得不够。前向检查会改动邻居的论域。只恢复正在撤销的那个区域，会留下过时的删除记录，搜索就会悄悄漏掉本来存在的着色。每次选择前保存所有论域，回退时全部恢复。
以为几种加速方法的效果可以叠加。MRV 和前向检查有重叠。在默认地图上，给 MRV 再加上前向检查，结果完全不变。
把中途停下的搜索当成证明。撞上步数或时间上限而停下的搜索，对着色是否存在什么也没说明。只有把所有可能都试完的搜索，才能证明不存在。
以为四种颜色总够用，着色就很简单。定理保证着色存在，但不会让用更少颜色找到着色变得便宜，三色问题是 NP 完全的。
忘了取值排序。先试那个给邻居排除选项最少的颜色，也就是最少约束值，往往能更快找到解。工具总是按同样的顺序试颜色，这样区域排序的效果能单独显示出来。

参考资料

Artificial Intelligence: A Modern ApproachRussell 与 Norvig，第 4 版，Pearson，2020。第 6 章。CSP 的标准讲法，以澳大利亚地图为主线，讲回溯、MRV、前向检查和 AC-3。
Increasing tree search efficiency for constraint satisfaction problemsHaralick 与 Elliott，Artificial Intelligence 第 14 卷第 3 期，1980，第 263–313 页。前向检查和“先失败”原则在这里被放在一起研究，并做了测量。
Consistency in networks of relationsMackworth，Artificial Intelligence 第 8 卷第 1 期，1977，第 99–118 页。弧相容和 AC-3 算法的出处。
Every planar map is four colorable. Part I: DischargingAppel 与 Haken，Illinois Journal of Mathematics 第 21 卷第 3 期，1977，第 429–490 页。用计算机辅助证明四种颜色总是够用，这是证明的前半部分。