2.2 CSP、约束传播与回溯：先删掉不可能，再尝试赋值
模型工坊接到一张排班表：每个哨位要有人值守，同一人不能同时出现在两个地点，夜班资格和休息间隔也有限制。枚举所有安排当然能找到答案，但绝大多数组合在填入前几个位置时就已注定失败。
Constraint Satisfaction Problem（CSP）把问题拆成变量、值域和约束。求解器的关键不是更快地产生完整方案，而是尽早传播局部选择造成的后果。
本课目标
- 用变量、domain 和 constraint 建模；
- 实现顺序无关的回溯与 forward checking；
- 理解 MRV、degree、LCV 和 arc consistency；
- 区分局部一致性、可满足性、一个解与所有解。
1. CSP 的形式
一个有限 CSP 包含：
$$ X={X_1,\ldots,X_n},\quad D_i, \quad C={C_1,\ldots,C_m}. $$
- 变量 $X_i$；
- 每个变量的候选域 $D_i$；
- 约束规定哪些变量组合允许出现。
完整且满足所有约束的赋值是解。目标若还要最小化成本，就成为 constraint optimization problem，不能把找到的第一个可行解当最优。
2. 约束有不同作用域
- unary：
shift != night； - binary：相邻区域颜色不同；
- global：
AllDifferent(X1, ..., X9)； - arithmetic/cumulative：资源总量和时间区间容量。
把 global constraint 拆成许多 binary constraints 可能保持可行解集合，却丢失更强传播能力。例如 AllDifferent 可利用整体匹配结构，比逐对 != 更早发现无解。
3. 一个顺序无关的最小求解器
旧稿把约束存为有向 (var, assigned_var)，只登记 (a,b)，当赋值顺序反过来时可能漏检。更稳妥的是让约束对象声明 scope，并统一检查当前已赋值部分。
from dataclasses import dataclass
@dataclass(frozen=True)
class Constraint:
scope: tuple[str, ...]
predicate: object
def consistent(assignment, constraints):
for constraint in constraints:
if all(v in assignment for v in constraint.scope):
values = [assignment[v] for v in constraint.scope]
if not constraint.predicate(*values):
return False
return True
def backtrack(variables, domains, constraints, assignment=None):
assignment = {} if assignment is None else assignment
if len(assignment) == len(variables):
return assignment.copy()
var = next(v for v in variables if v not in assignment)
for value in domains[var]:
assignment[var] = value
if consistent(assignment, constraints):
result = backtrack(variables, domains, constraints, assignment)
if result is not None:
return result
del assignment[var]
return None它正确性清晰，却只在约束 scope 全赋值后检查，传播很弱。
4. Forward checking
给变量赋值后，立即从未赋值邻居的 domain 删除不兼容值。若某个 domain 变空，立刻回溯。
实现时不要直接永久修改共享 domain；使用可撤销 trail 或复制当前 domain。复制简单但成本高，trail 更高效却容易因回溯恢复不完整产生隐蔽错误。
Forward checking 只看当前赋值与邻居，不能发现两个未赋值变量之间已经无可行配对。
5. Arc consistency 与 AC-3
二元约束 $C(X,Y)$ 下，弧 $X\to Y$ arc-consistent，当 $D_X$ 中每个值都能在 $D_Y$ 找到一个支持值。
AC-3 反复修订不一致的弧：
queue ← all directed arcs
while queue not empty:
(X, Y) ← pop(queue)
if revise(X, Y):
if domain[X] is empty: fail
add (Z, X) for every neighbor Z != Y达到 arc consistency 不代表全局有解。地图着色、数独等仍可能所有局部弧都有支持，却无法组合成完整赋值。
6. 变量和值排序
MRV
选择剩余合法值最少的变量，优先暴露失败（fail first）。
Degree heuristic
MRV 平局时，优先选择约束最多未赋值邻居的变量。
LCV
尝试对邻居删值最少的 value，给后续保留空间。
这些启发式影响搜索量，不改变解集合。LCV 评分也有计算成本；小问题上不一定更快。
7. 建模通常比换启发式更重要
- 使用紧 domain，不要先放所有值再用约束排除；
- 选择能表达真实独立性的变量；
- 用 global constraint 保留结构；
- 消除对称：三种颜色可互换时，固定第一个区域颜色；
- 将可预计算的固定关系移出搜索；
- 不把软偏好伪装成硬约束。
错误的时间粒度可能把可行排班判为不可行，过粗变量又可能遗漏休息间隔。
8. Unsat 也需要解释
现实中“无解”常比找到解更重要。求解器应尽可能返回冲突约束/unsat core，帮助业务判断：是容量确实不足，还是规则互相矛盾。
软约束可附 penalty，形成 weighted CSP/optimization。必须说明哪些规则绝不违反，哪些只是偏好，以及总分是否掩盖某人承担全部代价。
9. 测试
空变量集合
单变量空 domain
不对称输入顺序
多个解与唯一解
局部一致但全局无解
对称解
回溯后 domain 完整恢复
硬约束与软约束冲突对小实例枚举全部赋值，与优化求解器结果对照。
常见误区
- 节点/弧一致就保证有解：它们只是局部性质。
- 约束登记一个方向就够：求解顺序可能漏检。
- 找到第一个解就是最佳排班：可行与最优不同。
- MRV 永远更快：启发式自身有成本且依赖结构。
练习
- 修复地图着色约束，使变量任意排序都得到合法结果。
- 加入 forward checking，并统计 domain wipeout 次数。
- 构造 arc-consistent 但无解的小 CSP。
- 为排班区分硬规则与软偏好，解释 objective。
小结
CSP 通过变量和约束暴露问题结构。回溯负责选择，传播负责提前删除不可能；建模、global constraints 和恢复机制共同决定求解器是否既正确又高效。
下一课进入概率表示：证据不完整时，不再问某个结论是否必然成立，而是计算给定证据后的概率分布。