第4章：约束满足问题（Constraint Satisfaction Problems）
一、导读
1.1 本章学习目标
第4章介绍了一类特殊但极其重要的问题形式——约束满足问题（CSP）。与第3章中的通用状态空间搜索不同，CSP 利用问题的结构（变量、值域、约束）来设计更高效的求解算法。许多现实世界的问题——排课、配置、调度、地图着色——都可以自然地表示为 CSP。
本章的核心学习目标包括：
- 掌握 CSP 的形式化方法：学会用变量、值域和约束来描述问题，理解约束图的结构。
- 理解回溯搜索的原理：掌握基本的回溯搜索算法，以及最小冲突值（MRV）、度启发式和最少约束值（LCV）等变量和值选择策略。
- 掌握约束传播技术：理解节点相容、弧相容（AC-3 算法）和路径相容的概念，学会通过约束传播缩小搜索空间。
- 理解局部搜索方法：掌握 MIN-CONFLICTS 启发式在 CSP 求解中的应用。
- 了解 CSP 的结构与复杂性：理解树结构 CSP 的高效求解方法，以及约束传播与搜索的结合。
- 掌握 CSP 的实际应用：数独、地图着色、课程安排、调度等。
1.2 为什么第四章如此重要
CSP 框架在AI中占据独特地位。它介于通用搜索（第3章）和专用算法之间：比通用搜索更结构化，但比专用算法更通用。许多AI问题——从规划到视觉到自然语言处理——都可以表示为 CSP，而 CSP 求解技术是这些应用的基础。
更重要的是，CSP 引入了一种重要的AI设计思想：利用问题结构来指导搜索。约束传播不是盲目地探索状态空间，而是通过分析约束关系来主动缩小搜索空间。这种思想在后续章节的许多算法中都有体现。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
CSP 与通用搜索的关系：CSP 可以转化为状态空间搜索问题，但为什么直接求解 CSP 通常更高效？
约束传播为什么有效？ 弧相容检查如何减少搜索空间？在最坏情况下，约束传播能消除多少无效搜索？
变量选择策略的重要性：为什么"先选约束最多的变量"（度启发式）或"先选剩余值最少的变量"（MRV）能大幅加速求解？
CSP 的结构性：为什么树结构的 CSP 可以在多项式时间内求解？这与约束图的连通性有什么关系？
NP 完全性与实际求解：CSP 一般是 NP 完全的，但为什么许多实际 CSP 实例可以在合理时间内求解？
二、核心概念详解
2.1 CSP 的定义与形式化
2.1.1 CSP 的三要素
一个约束满足问题由三个要素组成：
变量集合 X = {X₁, X₂, ..., Xₙ}
值域集合 D = {D₁, D₂, ..., Dₙ}，每个变量 Xᵢ 有一个值域 Dᵢ
约束集合 C = {C₁, C₂, ..., Cₘ}，每个约束描述了某些变量之间的合法组合
python
class CSP:
def __init__(self, variables, domains, constraints):
self.variables = variables
self.domains = domains
self.constraints = constraints
self.neighbors = {var: set() for var in variables}
for (v1, v2), constraint in constraints.items():
self.neighbors[v1].add(v2)
self.neighbors[v2].add(v1)
def is_consistent(self, var, value, assignment):
for neighbor in self.neighbors[var]:
if neighbor in assignment:
constraint_key = (var, neighbor) if (var, neighbor) in self.constraints else (neighbor, var)
if constraint_key in self.constraints:
if not self.constraints[constraint_key](value, assignment[neighbor]):
return False
return True
# 地图着色问题
def map_coloring_csp():
variables = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']
domains = {var: ['red', 'green', 'blue'] for var in variables}
constraints = {
('WA', 'NT'): lambda a, b: a != b,
('WA', 'SA'): lambda a, b: a != b,
('NT', 'SA'): lambda a, b: a != b,
('NT', 'Q'): lambda a, b: a != b,
('SA', 'Q'): lambda a, b: a != b,
('SA', 'NSW'): lambda a, b: a != b,
('SA', 'V'): lambda a, b: a != b,
('Q', 'NSW'): lambda a, b: a != b,
('NSW', 'V'): lambda a, b: a != b,
}
return CSP(variables, domains, constraints)
csp = map_coloring_csp()
print(f"变量: {csp.variables}")
print(f"值域: {csp.domains['WA']}")2.1.2 约束的类型
约束可以按涉及的变量数量分类：
- 一元约束：只涉及一个变量（如
X > 0） - 二元约束：涉及两个变量（如
X ≠ Y） - 全局约束：涉及任意数量的变量（如
AllDifferent(X, Y, Z)）
python
class ConstraintTypes:
@staticmethod
def unary(var, predicate):
return {var: lambda val: predicate(val)}
@staticmethod
def binary(var1, var2, predicate):
return {(var1, var2): predicate}
@staticmethod
def all_different(variables):
constraints = {}
for i in range(len(variables)):
for j in range(i + 1, len(variables)):
constraints[(variables[i], variables[j])] = lambda a, b: a != b
return constraints
# 数独的 AllDifferent 约束
def sudoku_constraints():
constraints = {}
for i in range(9):
row_vars = [f'R{i}{j}' for j in range(9)]
col_vars = [f'R{j}{i}' for j in range(9)]
box_vars = [f'R{3*(i//3)+j//3}{3*(i%3)+j%3}' for j in range(9)]
for group in [row_vars, col_vars, box_vars]:
for a in range(len(group)):
for b in range(a + 1, len(group)):
constraints[(group[a], group[b])] = lambda x, y: x != y
return constraints2.1.3 约束图
约束图是 CSP 的可视化表示：变量是节点，约束是边。约束图的结构直接影响求解效率。
python
def print_constraint_graph(csp):
print("约束图（邻接表）:")
for var in csp.variables:
neighbors = sorted(csp.neighbors[var])
print(f" {var}: {neighbors}")
csp = map_coloring_csp()
print_constraint_graph(csp)2.2 回溯搜索
2.2.1 基本回溯搜索
回溯搜索是一种深度优先搜索，每次为一个变量赋值，如果发现违反约束则回溯。
python
def backtracking_search(csp):
return backtrack({}, csp)
def backtrack(assignment, csp):
if len(assignment) == len(csp.variables):
return assignment
var = select_unassigned_variable(csp, assignment)
for value in csp.domains[var]:
if csp.is_consistent(var, value, assignment):
assignment[var] = value
result = backtrack(assignment, csp)
if result is not None:
return result
del assignment[var]
return None
def select_unassigned_variable(csp, assignment):
for var in csp.variables:
if var not in assignment:
return var
return None
# 求解地图着色
csp = map_coloring_csp()
solution = backtracking_search(csp)
print(f"地图着色解: {solution}")2.2.2 变量和值选择启发式
好的变量和值选择策略能大幅加速回溯搜索。
最小剩余值（MRV）启发式：选择剩余合法值最少的变量。这能快速发现死胡同。
python
def mrv(csp, assignment):
unassigned = [v for v in csp.variables if v not in assignment]
return min(unassigned, key=lambda v: len(
[val for val in csp.domains[v] if csp.is_consistent(v, val, assignment)]
))度启发式：选择与最多未赋值变量有约束的变量。
python
def degree_heuristic(csp, assignment):
unassigned = [v for v in csp.variables if v not in assignment]
return max(unassigned, key=lambda v: sum(
1 for n in csp.neighbors[v] if n not in assignment
))最少约束值（LCV）：选择对未赋值变量约束最少的值。
python
def lcv_value(csp, var, assignment):
def count_reductions(value):
count = 0
for neighbor in csp.neighbors[var]:
if neighbor not in assignment:
count += sum(1 for v in csp.domains[neighbor]
if not csp.is_consistent(var, value,
{**assignment, var: value}))
return count
consistent_values = [v for v in csp.domains[var]
if csp.is_consistent(var, v, assignment)]
return min(consistent_values, key=count_reductions)2.3 约束传播
2.3.1 弧相容与 AC-3 算法
弧相容：变量 Xᵢ 关于变量 Xⱼ 是弧相容的，如果 Xᵢ 值域中的每个值都能在 Xⱼ 的值域中找到一个满足约束的对应值。
AC-3 算法通过反复检查和维护弧相容来缩小值域。
python
def ac3(csp, queue=None):
if queue is None:
queue = list(csp.constraints.keys())
while queue:
(xi, xj) = queue.pop(0)
revised = revise(csp, xi, xj)
if revised:
if not csp.domains[xi]:
return False
for xk in csp.neighbors[xi]:
if xk != xj:
queue.append((xk, xi))
return True
def revise(csp, xi, xj):
revised = False
constraint = csp.constraints.get((xi, xj)) or csp.constraints.get((xj, xi))
if constraint is None:
return False
to_remove = []
for x in csp.domains[xi]:
if not any(constraint(x, y) for y in csp.domains[xj]):
to_remove.append(x)
revised = True
for x in to_remove:
csp.domains[xi].remove(x)
return revised
# 使用 AC-3 预处理
csp = map_coloring_csp()
print(f"AC-3 结果: {ac3(csp)}")
print(f"预处理后值域: {csp.domains}")2.3.2 节点相容与路径相容
节点相容：每个变量的值域中的每个值都满足所有一元约束。
路径相容：对于任意两个变量 Xᵢ 和 Xⱼ，以及它们值域中的任意值，都存在一条通过第三个变量 Xₖ 的相容路径。
python
def node_consistent(csp):
for var in csp.variables:
csp.domains[var] = [v for v in csp.domains[var]
if all(csp.constraints[(var, var)](v, v)
if (var, var) in csp.constraints else True
for _ in [1])]
return csp
def path_consistent(csp, xi, xj, xk):
new_domain_i = []
for vi in csp.domains[xi]:
for vj in csp.domains[xj]:
constraint_ij = csp.constraints.get((xi, xj)) or csp.constraints.get((xj, xi))
if constraint_ij and not constraint_ij(vi, vj):
continue
for vk in csp.domains[xk]:
constraint_ik = csp.constraints.get((xi, xk)) or csp.constraints.get((xk, xi))
constraint_jk = csp.constraints.get((xj, xk)) or csp.constraints.get((xk, xj))
if (not constraint_ik or constraint_ik(vi, vk)) and \
(not constraint_jk or constraint_jk(vj, vk)):
new_domain_i.append(vi)
break
else:
continue
break
return list(set(new_domain_i))2.4 CSP 的结构与复杂性
2.4.1 树结构 CSP
如果约束图是一棵树（无环），CSP 可以在 O(nd²) 时间内求解，其中 n 是变量数，d 是最大值域大小。
python
def tree_csp_solve(csp, root=None):
if root is None:
root = csp.variables[0]
ordering = topological_sort(csp, root)
for j in reversed(range(len(ordering) - 1)):
child = ordering[j + 1]
parent = find_parent(csp, child, ordering[:j + 1])
make_arc_consistent(csp, parent, child)
assignment = {}
for var in ordering:
assignment[var] = csp.domains[var][0]
return assignment
def topological_sort(csp, root):
visited = set()
order = []
def dfs(node):
visited.add(node)
order.append(node)
for neighbor in csp.neighbors[node]:
if neighbor not in visited:
dfs(neighbor)
dfs(root)
return order
def find_parent(csp, child, ancestors):
for ancestor in reversed(ancestors):
if child in csp.neighbors[ancestor]:
return ancestor
return None
def make_arc_consistent(csp, parent, child):
constraint = csp.constraints.get((parent, child)) or csp.constraints.get((child, parent))
if constraint is None:
return
new_domain = []
for vp in csp.domains[parent]:
for vc in csp.domains[child]:
if constraint(vp, vc):
new_domain.append(vc)
break
csp.domains[child] = list(set(new_domain))2.4.2 割宽与树宽
约束图的树宽决定了 CSP 的求解难度。树宽越小，CSP 越容易求解。
python
def analyze_csp_structure(csp):
n_vars = len(csp.variables)
n_constraints = len(csp.constraints)
max_degree = max(len(csp.neighbors[v]) for v in csp.variables)
avg_degree = sum(len(csp.neighbors[v]) for v in csp.variables) / n_vars
print(f"CSP 结构分析:")
print(f" 变量数: {n_vars}")
print(f" 约束数: {n_constraints}")
print(f" 约束密度: {2 * n_constraints / (n_vars * (n_vars - 1)):.3f}")
print(f" 最大度: {max_degree}")
print(f" 平均度: {avg_degree:.2f}")
if n_constraints < n_vars:
print(f" 结构: 稀疏（可能是树结构）")
elif n_constraints < n_vars * 2:
print(f" 结构: 中等密度")
else:
print(f" 结构: 密集（可能难以求解）")
csp = map_coloring_csp()
analyze_csp_structure(csp)2.5 局部搜索求解 CSP
2.5.1 MIN-CONFLICTS
MIN-CONFLICTS 是一种局部搜索算法，它从完整赋值开始，通过改变单个变量的值来最小化冲突数。
python
def min_conflicts(csp, max_steps=100000):
current = {}
for var in csp.variables:
current[var] = csp.domains[var][0]
for step in range(max_steps):
conflicts = count_conflicts(csp, current)
if conflicts == 0:
return current
var = random.choice([v for v in csp.variables
if count_var_conflicts(csp, current, v) > 0])
best_value = min(csp.domains[var],
key=lambda v: count_value_conflicts(csp, current, var, v))
current[var] = best_value
return None
def count_conflicts(csp, assignment):
total = 0
for (v1, v2), constraint in csp.constraints.items():
if v1 in assignment and v2 in assignment:
if not constraint(assignment[v1], assignment[v2]):
total += 1
return total
def count_var_conflicts(csp, assignment, var):
count = 0
for neighbor in csp.neighbors[var]:
if neighbor in assignment:
constraint = csp.constraints.get((var, neighbor)) or csp.constraints.get((neighbor, var))
if constraint and not constraint(assignment[var], assignment[neighbor]):
count += 1
return count
def count_value_conflicts(csp, assignment, var, value):
count = 0
for neighbor in csp.neighbors[var]:
if neighbor in assignment:
constraint = csp.constraints.get((var, neighbor)) or csp.constraints.get((neighbor, var))
if constraint and not constraint(value, assignment[neighbor]):
count += 1
return count
import random
csp = map_coloring_csp()
solution = min_conflicts(csp)
print(f"MIN-CONFLICTS 解: {solution}")三、实战案例
3.1 案例一：数独求解器
python
def create_sudoku_csp(grid):
variables = [f'R{r}{c}' for r in range(9) for c in range(9)]
domains = {}
constraints = {}
for r in range(9):
for c in range(9):
var = f'R{r}{c}'
if grid[r][c] != 0:
domains[var] = [grid[r][c]]
else:
domains[var] = list(range(1, 10))
for r in range(9):
for c1 in range(9):
for c2 in range(c1 + 1, 9):
constraints[(f'R{r}{c1}', f'R{r}{c2}')] = lambda a, b: a != b
for c in range(9):
for r1 in range(9):
for r2 in range(r1 + 1, 9):
constraints[(f'R{r1}{c}', f'R{r2}{c}')] = lambda a, b: a != b
for br in range(3):
for bc in range(3):
box_vars = [f'R{br*3+r}{bc*3+c}' for r in range(3) for c in range(3)]
for i in range(len(box_vars)):
for j in range(i + 1, len(box_vars)):
constraints[(box_vars[i], box_vars[j])] = lambda a, b: a != b
return CSP(variables, domains, constraints)
def print_sudoku(assignment):
for r in range(9):
row = []
for c in range(9):
row.append(str(assignment.get(f'R{r}{c}', '.')))
if c in [2, 5]:
row.append('|')
print(' '.join(row))
if r in [2, 5]:
print('-' * 21)
# 简单数独谜题
grid = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
]
csp = create_sudoku_csp(grid)
ac3(csp)
solution = backtracking_search(csp)
if solution:
print_sudoku(solution)
else:
print("无解")3.2 案例二：课程排程
python
def create_timetabling_csp():
courses = ['CS101', 'CS201', 'CS301', 'MATH101', 'MATH201', 'PHY101']
rooms = ['R1', 'R2', 'R3']
timeslots = ['Mon9', 'Mon11', 'Tue9', 'Tue11', 'Wed9']
variables = [(c, 'room') for c in courses] + [(c, 'time') for c in courses]
domains = {}
constraints = {}
for c in courses:
domains[(c, 'room')] = rooms[:]
domains[(c, 'time')] = timeslots[:]
for c in courses:
constraints[((c, 'room'), (c, 'time'))] = lambda a, b: True
for i in range(len(courses)):
for j in range(i + 1, len(courses)):
c1, c2 = courses[i], courses[j]
constraints[((c1, 'room'), (c2, 'room'))] = lambda a, b: True
constraints[((c1, 'time'), (c2, 'time'))] = lambda a, b: a != b
return CSP(variables, domains, constraints)
csp = create_timetabling_csp()
solution = backtracking_search(csp)
if solution:
courses = set(v[0] for v in solution)
for c in sorted(courses):
room = solution.get((c, 'room'), '?')
time = solution.get((c, 'time'), '?')
print(f"{c}: {room} @ {time}")四、本章小结
本章系统介绍了约束满足问题（CSP）的概念和求解方法。CSP 通过变量、值域和约束来描述问题，利用约束传播和启发式搜索来高效求解。
核心知识点回顾：
- CSP 的三要素：变量、值域、约束
- 回溯搜索是求解 CSP 的基本方法
- MRV、度启发式和 LCV 能大幅加速搜索
- AC-3 算法通过弧相容检查缩小值域
- 树结构 CSP 可在多项式时间内求解
- MIN-CONFLICTS 是一种高效的局部搜索方法
五、思考与练习
思考题
约束传播的极限：AC-3 算法能否保证找到所有解？如果不能，它的作用是什么？
CSP 的 NP 完全性：为什么一般的 CSP 是 NP 完全的？什么样的约束结构使 CSP 变得容易？
编程练习
实现 N 皇后 CSP：用 CSP 框架表示 N 皇后问题，比较回溯搜索和 MIN-CONFLICTS 的性能。
实现 AC-4 算法：AC-4 比 AC-3 更强，它维护每个值的支撑计数。实现 AC-4 并比较性能。
词谜问题：用 CSP 求解填字游戏或字母算术谜题（如 SEND + MORE = MONEY）。