13 · CSP 是什么
⏱ 33 分钟 | ⭐ 先写清要填什么、能填什么、哪些组合不允许
时间是阅读参考,不是截止时间。本章不要求写程序:先学会检查一个方案,再看如何把问题写成求解器能处理的形式。
🎯 一句话
约束满足问题(CSP)要找一份完整方案:每个空都填上允许的值,而且所有规则同时成立。
例如,地图只有红、绿、蓝三种颜色,相邻区域不能同色。若西澳已填红、北领地已填绿,而南澳与两者都相邻,南澳就只剩蓝色。
这一步没有枚举所有完整地图,而是利用已经写出的规则排除候选。后两章会把这种做法变成算法。
- 第一次接触:从变量、值域、约束开始,认清地图上的三个角色。
- 想看建模怎样省事:看每列一个变量的 n 皇后。
- 想亲手推一次:看密码算术的进位推导。
🔀 一、转折:从「怎么走过去」到「最后填成什么样」
在路线规划里,只给你目的地还不够:你需要一条能从起点走过去的路线。路径顺序和代价都可能属于答案。
标准 n 皇后题问的却是:能否在棋盘上摆出一组互不攻击的皇后?通常只需交付最终棋盘,不评价先填哪一列。
这是两类任务的对照,不是说前面所有算法都只看黑箱、只返回路径。局部搜索也可能寻找最终状态;博弈搜索常用于决定下一步动作。
| 任务 | 要交付什么 | 给定候选后,怎么核对 |
|---|---|---|
| CSP:n 皇后 | 一份满足规则的棋盘 | 检查皇后数量及是否互相攻击 |
| 路径搜索:还原魔方 | 一串合法转动 | 从当前状态执行,检查是否六面同色 |
两者都可能“容易检查、难以找到”。n 皇后不是不知道目标的规则,而是还没有找到满足规则的那份具体赋值。
好处一:不必重复尝试“填空的先后顺序”
WA 是西澳,NT 是北领地。先填 WA=红、再填 NT=绿,与反过来填,得到的是同一份部分赋值。这里说的可交换是“赋值顺序不改变最终方案”。
所以回溯时可以先选定一个未赋值变量,再只枚举它的值。变量的选择仍可以依据当前情况改变,不必全程固定顺序。
若每个变量至多有 $d$ 个候选,这个节点最多产生 $d$ 个试值分支,而不是把“选哪个变量”也重复展开一遍。在从空赋值开始、每步只填一个变量的搜索树里,填完 $n$ 个变量的解位于深度 $n$。传播一次确定多个变量时,不能再把递归层数当成已填变量数。
好处二:规则能直接帮助排除候选
普通搜索接口可以把状态当成一个整体,主要提供后继状态、代价和目标检查。CSP 则显式告诉算法:有哪些变量、还剩哪些值、哪些组合相互冲突。
页首的南澳例子就是一次最小推理:先根据相邻规则删掉红和绿,再继续搜索。这提供了提前发现某些死路的机会,不保证所有死路都能提前发现。 Berkeley CS188:CSP 与约束图
🧩 二、三件套:变量、值域、约束
先把术语翻成填空题的语言:
| 名称 | 你要写清什么 | 地图里的例子 |
|---|---|---|
| 变量 $X_i$ | 要决定的那个空 | 南澳的颜色 SA |
| 值域 $D_i$ | 这个空允许取的值 | 红、绿、蓝 |
| 约束 | 哪些组合允许,哪些不允许 | SA 与 WA 不能同色 |
赋值就是给变量选值。只填一部分叫部分赋值;所有变量都填好叫完整赋值。解必须是满足全部约束的完整赋值,“目前还没冲突”不等于已经有解。Poole 与 Mackworth:变量、约束与解
主线例子:澳大利亚地图着色
本例使用常见的七区域简化模型,不纳入所有领地;把共享边界的两区视为相邻,仅在角点接触不算。规则是相邻区域不能同色。
| 变量 | 区域 | 一个合法方案 |
|---|---|---|
| WA | 西澳 | 红 |
| NT | 北领地 | 绿 |
| SA | 南澳 | 蓝 |
| Q | 昆士兰 | 红 |
| NSW | 新南威尔士 | 绿 |
| V | 维多利亚 | 红 |
| T | 塔斯马尼亚 | 绿 |
每个区域最初都可选红、绿、蓝。把相邻关系写全并去重,就有以下 9 条约束:
- 西部与北部:$WA \ne NT$、$WA \ne SA$、$NT \ne SA$、$NT \ne Q$。
- 南澳连向东部:$SA \ne Q$、$SA \ne NSW$、$SA \ne V$。
- 东部相邻区域:$Q \ne NSW$、$NSW \ne V$。
忽略约束时,有 $3^7 = 2187$ 份完整候选。这是候选总数,不是合法解数,也不是算法必定尝试的次数。
现在用表里的方案检查任意一条,例如 SA=蓝、NSW=绿,满足 $SA \ne NSW$。其余八条也都不同色,所以这是一份解;T 虽然不连其他区域,也仍需填一个允许的颜色。
本章先用这张图理解模型;第 14 章研究回溯、前向检查与 AC-3,第 15 章研究变量顺序和割集条件。
约束图
把变量画成节点、把每条二元约束画成一条边,就得到约束图:
一个节点连着几条边,就称它的度是多少。这里有三条可以利用的信息:
- T 的度为 0。 它可独立上色,不影响大陆部分。
- SA 的度为 5。 它与最多区域发生约束联系,但不等于它当前“最难填”。还剩几个合法颜色、邻居是否已赋值,同样重要;第 15 章会区分 MRV 和度启发式。
- 移开 SA 及相连的边后,WA、NT、Q、NSW、V 按这个次序形成一条链,T 是孤立点。合起来是没有环的森林,不是一棵连通的树。
因此,集合 {SA} 是一个环割集:移除它后,图不再有环。实际求解不能直接扔掉 SA 的约束;要尝试 SA 的颜色,并先从邻居值域删掉同色,再处理剩下的森林。第 15 章会展开这个过程。
候选是变量可以尝试的值,解要同时满足全部约束。约束图展示哪些变量之间存在约束。
🏷 三、约束的种类
先数它牵涉几个变量
约束的元数,就是它涉及的不同变量个数。不是公式里有多少个符号。
| 种类 | 变量数 | 例子 |
|---|---|---|
| 一元 | 1 | $M \ne 0$(首位不能是零) |
| 二元 | 2 | $SA \ne WA$ |
| 高阶 | 至少 3 | $Y = D + E$(3 个变量) |
连续或离散是另一种分类,不能与元数混在一起。例如 $EndJob_1 + 5 \le StartJob_3$ 涉及两个时间变量:工序 3 至少在工序 1 结束后 5 个时间单位开始。时间既可用连续数,也可用整数时隙;第 14 章的实现只处理有限值域。
高阶约束能改写,但要付出代价
对有限值域 CSP,可以用辅助变量把高阶约束改写成二元约束,同时保留原变量上的解。下面直接看构造,不必背结论。
设 A、B 只能取 0 或 1,C 可取 0、1、2,约束是 $A+B=C$。引入辅助变量 H:它的每个值是一整个合法三元组。
- H 可取:(0,0,0)、(0,1,1)、(1,0,1)、(1,1,2)。
- H 与 A 之间要求:H 的第一项等于 A。
- H 与 B、C 之间分别检查第二项、第三项。
每条新约束只连接两个变量。例如 H=(1,0,1) 就强制 A=1、B=0、C=1。反过来,每个合法的 A、B、C 组合也能找到对应的 H。
代价是 H 的值域可能非常大。 可行解能保留,不代表改写后更省内存、更快,或传播效果相同。下一章讲二元 AC-3 是为了先理解基本机制,不是要求所有实际模型都拆成二元。
AllDiff:解不变,提前排除的能力可能改变
AllDiff(all-different)要求一组变量的取值两两不同。这是一种有专门语义的全局约束;它不是“元数之外的另一种变量数”。MiniZinc:All-Different 的定义
保留 AllDiff,或把它写成所有成对不等式,可行解集合相同。区别在于求解器采用什么传播算法。
看原来的小例子:5 个变量,每个都只能取 1、2、3、4,还要求五者互不相同。
- 整体看:无解。 5 个不同变量要占用不同值,却只有 4 个值,这是鸽笼原理。
- 只看任意一对:都还有搭配。 其中一个取 1,另一个仍可取 2、3 或 4;其他取值也一样。对成对不等式逐条做弧一致性检查,删不掉任何候选。
因此,足够强的 AllDiff 整体传播可以在搜索前发现这类矛盾,而成对弧一致性不行。不能把“每对都有支持”误说成“存在一份同时满足所有约束的赋值”。具体支持哪种传播强度取决于求解器,而不只是写了哪个名字。MiniZinc:全局约束与求解器实现
还要区分“必须满足”和“尽量满足”
本章的普通 CSP 只问能否满足全部硬约束。若还要比较方案好坏,就进入约束优化(COP);也常见“软约束 CSP”等扩展称呼,不能简单说软约束与 CSP 毫无关系。
例如排课:老师不能同时出现在两间教室,是硬约束;“能排 11 点就别排 8 点”“尽量不排周五下午”是偏好。可以为不理想安排计分,在硬约束全满足的前提下,最小化总罚分。
两个可行方案分别罚 0 分和 1 分,纯可行性问题接受两者,优化问题则偏好 0 分。求解器不会替你决定偏好有多重要,权重和优先级也是建模的一部分。OR-Tools:排班约束与偏好目标
👑 四、n 皇后:换变量,先排除不必要的候选
$n \times n$ 棋盘上放恰好 $n$ 个皇后,任意两个不能在同一行、同一列或同一条对角线上。
模型 A:每格一个布尔变量。 每格取 0 或 1,表示不放或放。还要写出“恰好放 n 个”以及行、列、对角线的互斥约束。
8×8 棋盘需要 64 个变量;忽略约束,有 $2^{64}$ 份候选。但这不是求解器一定要遍历的数量,它可以传播和剪枝。
模型 B:每列一个变量。 因为恰好有 n 个皇后、n 列且同列至多放一个,所以每列必须恰好放一个。于是可以直接记“这一列的皇后在哪一行”:
- 变量:$Q_1, \dots, Q_n$(第 $i$ 列的皇后在第几行)
- 值域:$\{1, \dots, n\}$
- 约束:对每一对不同的列 $i<j$,分别检查不同行、不同对角线。
$$Q_i \ne Q_j$$
这里 $Q_i$ 是第 i 列皇后的行号。两个行号不能相同,便排除了横向攻击。
$$\lvert Q_i-Q_j\rvert \ne \lvert i-j\rvert$$
同一条对角线上,横跨几列就会上下跨几行。右边是列间距,左边是行间距;两者相等就会攻击。
这时“每列恰好一个皇后”已经编码进变量的含义,不再需要另写一条检查。忽略其余约束,8 皇后的候选是 $8^8=16{,}777{,}216$,约 $1.7\times10^7$,远少于模型 A 的原始组合。
这说明表示方式会改变搜索空间,不是两个模型实测速度的结论。 布尔模型也有用途,例如适配 SAT 或整数规划工具;不能只凭变量数或原始组合数就断言哪个求解器一定快。
就像特征工程会影响学习任务,CSP 的变量和约束设计也会影响求解难度。但性能还取决于传播、搜索顺序和实现,不能把“建模比算法重要”当成无条件排名。
手边就能核对:4 皇后的一个解是 $(Q_1,Q_2,Q_3,Q_4)=(2,4,1,3)$。四个行号不同;例如第 1、3 列的行间距是 1、列间距是 2,不在同一条对角线。六对列都检查通过,才算验证这份解。
🔢 五、密码算术:SEND + MORE = MONEY
本例先用规则推出 M=1、O=0、S=9,再检查剩余候选。 最终答案是 9567+1085=10652;下面解释它如何得到,不要求你猜中某个数字。
这里的“密码算术”是字母代替数字的谜题,不是加密方案。相同字母始终表示同一数字,不同字母必须使用不同数字,首位不能为 0。
$$\texttt{SEND} + \texttt{MORE} = \texttt{MONEY}$$
- 字母变量:S、E、N、D、M、O、R、Y,共 8 个。
- 值域:$\{0,\dots,9\}$
- 约束:AllDiff(S,E,N,D,M,O,R,Y);一元约束 $S \ne 0$、$M \ne 0$
还缺一条:加法本身必须成立。可以直接写一个牵涉 8 个字母的加法约束,也可以引入辅助变量(进位),把它按列分开。
① 每个进位记录哪一列的“满十”
C₁ 是个位向十位的进位,C₂ 是十位向百位的进位,C₃ 是百位向千位的进位,C₄ 是千位向万位的进位。两位数字加上一个进位最多是 19,所以每个进位只可能是 0 或 1。
个位: D 与 E 相加,个位留下 Y,满十的部分送给 C₁。
$$D+E=Y+10C_1$$
十位: 除 N 与 R,还要接住上一列的 C₁。
$$N+R+C_1=E+10C_2$$
百位: E 与 O,加上 C₂,得到 N 和下一次进位。
$$E+O+C_2=N+10C_3$$
千位: S 与 M,加上 C₃,得到 O 和万位进位。
$$S+M+C_3=O+10C_4$$
万位: 没有其他数字可相加,最高位 M 就是 C₄。
$$M=C_4$$
现在一个 8 元加法约束变成五个较局部的约束,元数分别是 4、5、5、5、2。例如十位那条涉及 N、R、C₁、E、C₂ 五个不同变量,不能把它数成四元。
AllDiff 和首位非零约束仍须保留。增加进位变量是为了暴露每列的联系,不保证一定比一个整体加法约束跑得快。
② 先推五步,不猜字母取什么值
第 1 步:最高位只能是 1。 M=C₄,而 C₄ 只能为 0 或 1。M 是首位不能为 0,所以 M=1,C₄=1。
第 2 步:O 只能是 0。 千位变成 $S+1+C_3=O+10$。因为 S≤9、C₃≤1,所以 O≤1。M 已占用数字 1,AllDiff 排除 O=1,因此 O=0。
注意:这里只能先推出 O≤1,不能直接写 O≤0;从 1 排除到 0,还用到了字母互异约束。
第 3 步:排除 C₃=1,得到 S=9。 假如 C₃=1,百位要求 $E+C_2=N+10$。左边至多 10;由于 O=0,N 不能再为 0,右边至少 11,矛盾。所以 C₃=0,千位变成 S+1=10,得到 S=9。
这里排除 C₃=1 是一次反证推理,不是任选一个字母值后沿搜索树继续试。
第 4 步:N 比 E 大 1。 百位现在是 $E+C_2=N$。E 与 N 不能相同,所以 C₂=1,N=E+1。
第 5 步:R=8,个位有进位。 把 N=E+1 代入十位,得到 $R+C_1=9$。若 C₁=0,就有 R=9,与 S 冲突;因此 C₁=1,R=8。
③ 剩下的候选逐一核对,不把猜测当推导
现在 S、M、O、R 已占用 9、1、0、8。E、N、D、Y 只能从 2、3、4、5、6、7 中取互不相同的数,还须满足 N=E+1、D+E=Y+10。
下面列全 E 的候选。表中的排除理由,都同时保留了个位必须进位、字母不能重号这两个条件。
| E / N | 剩余检查 |
|---|---|
| 2 / 3 | D 最大为 7,D+E≤9,不能产生已确定的进位。 |
| 3 / 4 | 要进位只能取 D=7,但会得到 Y=0,与 O 冲突。 |
| 4 / 5 | 要进位只能取 D=6 或 7,得到 Y=0 或 1,均已占用。 |
| 5 / 6 | 可用 D 中只有 7 能进位,此时 Y=2,所有字母互异。 |
| 6 / 7 | D 只能用 2、3、4、5;能进位的 D=4 或 5 只给出 Y=0 或 1,仍冲突。 |
| 7 / 8 | N=8 已与 R 冲突,不必再检查个位。 |
因此只有 E=5、N=6、D=7、Y=2 留下,得到:
$$9567+1085=10652$$
读数重点:前五步把大量候选排除,最后仍做了一个很小的候选检查。这里的唯一性来自列全候选,而不是“挑 E=5 恰好成功”。本页算术已用独立穷举核对;谜题规则也可对照 OR-Tools 的密码算术建模示例。
🏭 六、哪些实际任务可以用这种方式建模
CSP 和约束优化是排班、调度、配置等任务的一类工具,不是所有软件都使用的默认底座。下面每行只列一个简化模型;真实系统通常还要加入业务条件。
| 场景 | 变量 | 值 | 典型约束 |
|---|---|---|---|
| 排课 / 排考 | 每门课或考试的安排 | (时段, 教室) | 同一老师/教室不冲突;若要求考试间隔至少 1 天,也要写成约束 |
| 护士排班 | 每人每天的班次 | 早/中/夜/休 | 按实际排班规则设置夜班后休息、工时上限与技能覆盖 |
| 资源分配 | 每个任务的机器及开始时间 | 机器编号、时间 | 容量限制、同机任务冲突与工序先后 |
| 数独 | 81 个格 | 1–9 | 每行/列/宫一条 AllDiff |
| 寄存器分配的简化模型 | 需要保存的中间值 | $k$ 个物理寄存器 | 发生干涉、不能共用存储的两个值不能占同一个寄存器 |
| 硬件配置 / 运输调度 | 每个部件 / 每车货 | 型号 / 班次 | 兼容性、容量、时间窗 |
寄存器分配为什么像地图着色? 寄存器是处理器里用来暂存数值的少量高速存储位置。两个还要使用、且不能共用位置的中间值称为相互“干涉”,在图上给它们连边;k 个可用寄存器对应 k 种颜色。
在固定干涉关系、忽略其他机器限制的模型中,这就变成图着色。真实编译器还要考虑寄存器类别、固定寄存器要求,以及位置不够时把部分值暂存到内存等决策;不能说它与七区域地图完全一样。LLVM:目标无关代码生成与寄存器分配
实际求解时,可以选择 CP-SAT、MIP 等现成工具:CP-SAT 使用约束规划和 SAT 技术;MIP 求解器常把分支定界与线性松弛等方法结合。它们不是“几十行回溯加 AC-3”的别名,不同结构也可能更适合网络流等专门算法。OR-Tools:求解器的适用区别
学习后两章的价值,是能看懂“哪里发生冲突、传播排除了什么、变量顺序在影响什么”,从而更有依据地检查模型。它不替代对具体求解器的测量和诊断。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 14 · 回溯与约束传播 | 本章已检查地图解、手推密码算术;下一章把求解过程写成算法,对比回溯、前向检查与 AC-3 能发现哪些冲突。 |
| 博弈论与集体决策 05 · 推理与分辨率 | 看命题逻辑怎样用 CNF 子句表达约束。CNF 的可满足性可视为一个布尔值域 CSP,但布尔值域并不自动意味着约束已写成 CNF;分辨率与 CSP 传播也不是同一个算法。 |
| AI基础设施 07 · 算子融合与编译 | 看减少中间结果往返显存的动机。融合会影响中间值的保存方式和资源需求,但该章不是寄存器分配算法教程;两者联系在于编译时如何使用有限的存储资源。 |
✅ 检查点
- n 皇后 CSP 与魔方路径搜索,交付的答案有什么不同?为什么“容易检查一个候选”不等于“容易找到答案”?
- “赋值可交换”省去了什么重复?在什么搜索方式下,n 个变量的解恰好位于深度 n?
- 显式列出变量、值域和约束后,算法可以怎样提前排除候选?它保证所有死路都能提前发现吗?
- 写出本例地图的变量、值域与 9 条约束。2187 表示候选数、合法解数,还是算法实际试值次数?
- SA 的度为 5、T 的度为 0,各能提供什么线索?移开 SA 后是什么结构,真正求解时能直接丢掉它的约束吗?
- AllDiff 改成成对不等式后,可行解是否改变?5 个变量共用 4 个值的例子,说明了哪种传播差异?
- n 皇后按列建模为什么不再检查“同列冲突”?$2^{64}$ 与 $8^8$ 的比较能证明实际运行时间吗?
- SEND+MORE=MONEY 为什么引入进位?手推 M、O、S,并数出十位等式涉及几个变量。得到 E=5 是凭猜测还是检查了剩余候选?
👀 答案
-
n 皇后交付满足规则的最终棋盘,不评价填列顺序;魔方需要从当前状态出发的合法转动序列。两者都能检查给定候选,但找到成功候选可能要排除大量失败选择。
-
不必把“先 WA 再 NT”和“先 NT 再 WA”当成两份不同方案。选定一个未赋值变量后,只枚举它的值;若每个值域至多 d 个值,分支数至多 d。从空赋值开始、每步只填一个变量时,完整解才恰好位于深度 n。
-
例如 WA=红、NT=绿,而 SA 与两者相邻,就可从 SA 的三个颜色中排除红、绿。结构让传播有信息可用,但这种局部检查不保证提前找出所有无解情况。
-
变量是 WA、NT、SA、Q、NSW、V、T;值域都是红、绿、蓝。9 条不等关系是 WA–NT、WA–SA、NT–SA、NT–Q、SA–Q、SA–NSW、SA–V、Q–NSW、NSW–V,每一对都必须不同色。2187 是忽略这些约束时的完整候选数,不是合法解数或实测次数。
-
SA 与最多区域相互约束,但度数不直接给出当前合法值的多少;T 可独立上色。移开 SA 后是五点链加孤立 T,合起来为森林。割集条件要先尝试 SA 的颜色并收缩邻居值域,不能只删掉相连约束。
-
可行解不变。五个变量要用不同值、却只有四个值,整体看不可能;但成对不等式的弧一致性检查中,每个值在另一个变量那里都有支持,因此删不动。足够强的 AllDiff 整体传播能发现矛盾;不能据此声称所有实现总是同样强或更快。
-
每列只有一个变量,它的一个取值只指定一个皇后的行号,因此每列恰好一个已由表示保证。两个指数只是忽略其他约束的原始组合数;实际运行还受传播和搜索策略等影响,不能把它们当成耗时比。
-
进位把一个整体加法暴露成局部联系。M=C₄ 且 M≠0,故 M=1;千位先推出 O≤1,再由 O≠M 推出 O=0;假设 C₃=1 会使百位左边≤10、右边≥11,故 C₃=0,得到 S=9。十位等式涉及 N、R、C₁、E、C₂,共 5 个变量。最后列出 E=2 至 7 的候选,只有 E=5、N=6、D=7、Y=2 合法;不是未经论证地选中 E=5。
本节回顾
⚡ 走神救援
- CSP 的解是“全部变量已赋值,而且全部约束同时成立”,不是“暂时没发现冲突”。
- 显式的变量、值域和约束,让传播能提前排除某些候选;它不保证不用搜索。
- 同一个问题可以换表示。解是否保留、传播强弱、运行快慢,是三件不同的事。
- 看不懂进位时,从按列拆开的五条等式恢复;会读模型后,就可以进入求解算法。
下一节 👉 14-回溯与约束传播.md
下一章比较回溯、前向检查和 AC-3,重点看它们什么时候发现冲突,以及没有发现冲突时还不能保证什么。