Article

人工智能导论-CH2-CSPs

人工智能导论-CH2-CSPs，待补充摘要。

May 31, 2026 修考 20 min read

约束满足问题 (Constraint Satisfaction Problems, CSPs) 课程同步精细笔记

本笔记基于你的手写课堂笔记，结合 UC Berkeley CS188 教材内容进行整理、修正与深度润色，帮助你攻克知识难点，建立系统化的 CSP 知识图谱。

1. CSP 核心概念 (Core Concepts of CSPs)

1.1 规划问题 (Planning) vs. 识别问题 (Identification)

在传统搜索中，我们通常将求解过程视为一个规划问题；而在 CSP 中，我们将其视为识别问题。这两者有着本质区别：

规划问题 (Planning): 关注动作序列 (Sequence of actions) 与到达目标的路径 (Path)。例如，在迷宫寻路中，我们不仅要找到出口，还要关注一路上左拐还是右拐（Cost 往往与路径长度或步数挂钩）。
识别问题 (Identification): 我们关注的是结果（最终状态），而不是路径 (We care about the result, not the path)。传统搜索问题是一个“黑箱”（Black Box），状态转换函数和目标测试对搜索算法是不透明的。而 CSP 的状态是由一组变量显式定义的，我们的目标是找到一个满足所有约束的变量赋值组合，而不在乎它是通过什么动作步骤达到的。

🌟 核心要点： 原本的传统搜索只能根据路径代价（Cost）来进行启发式搜索，而 CSP 提供了一种通用目的 (General purpose) 的表征方法，使得我们可以利用问题内部的约束结构，极大提高求解效率。

1.2 CSP 的形式化定义

一个约束满足问题可以用三元组 $(V, D, C)$ 显式定义：

$V$ (Variables): 变量集合 $V = \{X_1, X_2, \dots, X_n\}$ 。
$D$ (Domains): 值域（域）集合 $D = \{D_1, D_2, \dots, D_n\}$ ，每个变量 $X_i$ 都有对应的取值范围 $D_i$ 。
$C$ $C$ (Constraints): 约束条件集合。每个约束限制了相关变量的合法取值组合。
- 元数 (Arity) 分类：
  - 一元约束 (Unary Constraint): 仅限制单个变量的取值。例如： $SA \neq \text{green}$ 。
  - 二元约束 (Binary Constraint): 限制两个变量的关系。例如： $SA \neq WA$ 。这也是约束图 (Constraint Graph) 的基础（节点代表变量，边代表二元约束）。
  - 多元约束 (Higher-order Constraint): 涉及三个或更多变量（如密码算术问题）。

1.3 什么是解 (Solution)？

完全赋值 (Complete Assignment): 每个变量都已被分配了一个值。
相容赋值 (Consistent Assignment): 该赋值不违反任何约束条件。
解 (Solution): 一个既完全又相容的赋值。换言之，Solution 就是满足约束的一种从 Variables 到 Domains 的映射 (Mapping)。

1.4 经典例题：澳大利亚地图着色问题 (Map Coloring)

为了直观理解，我们以经典的澳大利亚地图着色为例：

       [ WA ] --- [ NT ] --- [ Q ]
         |        /    \     /   \
         |      /        \ /       \
       [ SA ] ----------- [ NSW ] -- [ V ]
                                      
                             [ T ]

变量 $V$ : $\{WA, NT, Q, NSW, V, SA, T\}$ （各州名称缩写）。
值域 $D$ : $\{red, green, blue\}$ （三种颜色）。
约束 $C$ : 相邻的州不能涂相同的颜色（例如： $WA \neq NT, WA \neq SA, NT \neq Q, \dots$ ）。
可行解之一 (Mapping):

$\{WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red\}$

2. 求解 CSPs：回溯搜索 (Backtracking Search)

2.1 传统 DFS 与回溯搜索 (Backtracking Search) 的区别

传统 DFS (深度优先搜索): 是一种“盲目”的搜索。它会一直向下尝试赋值（例如，一上来就给所有节点都涂红色），直到走投无路（生成了一个完整的状态）后，才去检查这个状态是否满足约束条件。这会造成巨大的计算资源浪费（“传统 DFS 会一直给红色”）。
回溯搜索 (Backtracking Search, 简称 BS): 是 DFS 的一种优化。它在逐个为变量赋值的过程中，每一步都会检查当前赋值是否满足约束条件。如果发现当前的局部赋值已经违反了约束，它会立即撤销上一步的选择并回溯，尝试其他可能性，从而剪掉了大批无用的搜索分支。

2.2 回溯搜索的标准算法伪代码

请务必熟练掌握并背诵以下伪代码：

递归回溯工作方式的伪代码

def BACKTRACKING-SEARCH(csp):
    """
    输入: 一个约束满足问题 csp
    输出: 一个满足约束的完全赋值，或表示无解的 failure
    """
    return BACKTRACK(csp, {})

def BACKTRACK(csp, assignment):
    # 1. 递归基：如果赋值已完全，则直接返回该解
    if len(assignment) == len(csp.variables):
        return assignment
    
    # 2. 启发式选择一个尚未被赋值的变量
    var = SELECT-UNASSIGNED-VARIABLE(csp, assignment)
    
    # 3. 遍历该变量的所有可能取值
    for value in ORDER-DOMAIN-VALUES(csp, var, assignment):
        # 4. 检查当前取值是否与已有赋值相容
        if is_consistent(csp, var, value, assignment):
            # 临时尝试该赋值
            assignment[var] = value
            
            # 5. 递归继续为下一个变量赋值
            result = BACKTRACK(csp, assignment)
            if result != "failure":
                return result
            
            # 若失败，则撤销（回溯）
            del assignment[var]
            
    return "failure"

3. 过滤与剪枝 (Filtering)

在回溯搜索中，过滤 (Filtering) 是一种极高性能的优化方式：通过剔除已知会导致回溯的值，提前修剪未赋值变量的值域 (Domain)，从而达到防患于未然、提前剪枝的效果。

3.1 前向检查 (Forward Checking)

核心思想： 当一个变量 $X$ 被赋值后，立即检查与它相邻的所有未赋值邻居变量，将邻居变量值域中与 $X$ 当前赋值相冲突的值剔除。
局限性： 无法检测到两步及以上的间接冲突。它只向外传播一步，可能导致我们进入一个注定失败的深层分支。

3.2 弧一致性 (Arc Consistency, AC-3 算法)

手写笔记中提到：“如果从 Variable $X$ 中选一个值到 Domain $Y$ 中，都有后路可退，那么 $X \to Y$ 的弧是安全的。” 这是一个非常精准的直观理解！

弧一致性通常通过 AC-3 算法（弧一致性算法 #3）实现

3.2.1 弧一致性的数学定义

对于有向弧 $X \to Y$ ：当且仅当对于 $X$ 的当前值域 $D(X)$ 中的任意一个值 $x$ ，在 $Y$ 的值域 $D(Y)$ 中都至少存在一个值 $y$ 能满足 $X$ 与 $Y$ 之间的二元约束时，我们称有向弧 $X \to Y$ 是弧一致的 (Arc Consistent)。

如果我们在 $D(X)$ 中发现某个值 $x$ 在 $D(Y)$ 中找不到任何一个可以配对的“后路”，我们就必须把 $x$ 从 $D(X)$ 中剔除（Domain Reduction）。

3.2.2 约束传播 (Constraint Propagation)

当 $X$ 的值域被修剪减小后，可能会导致之前原本已经达成一致的其他弧（比如某个 $Z \to X$ ）变得不一致了。因此，我们需要把所有指向 $X$ 的弧重新放入队列中进行检查。这种链式反应就称为约束传播。

3.2.3 ✍️ 重点解析：你的手写 $A, B, C$ 约束传播例题

我们将你手写草稿中的 $A, B, C$ 例子进行严格规范的推演和补充：

已知变量及初始值域：

$D(A) = \{1, 2, 3\}, \quad D(B) = \{1, 2, 3\}, \quad D(C) = \{1, 2, 3\}$
约束条件：
1. $A > B$
2. $B < A$
3. $B = C$
4. $C = B$
待检查的有向弧集合（初始队列 Agenda）：

agenda初始情况就是约束条件。

$\text{Queue} = [A \to B, B \to A, B \to C, C \to B]$

AC-3 算法逐步执行追踪表 (Step-by-Step Trace)

步骤	出队弧 (Arc)	适用约束	检查与修剪过程 (Reduction)	值域变化结果	触发入队弧 (Added to Queue)
1	$A \to B$	$A > B$	检查 $D(A)=\{1,2,3\}$ :• $A=1$ : $D(B)$ 中无任何元素比它小 ( $1 \ngtr 1,2,3$ ) $\to$ 修剪 1• $A=2,3$ : 均能在 $D(B)$ 中找到对应的 $B=1$ 满足条件 $\to$ 保留	$D(A) \gets \{2, 3\}$	因 $D(A)$ 改变，所有指向 $A$ 的弧重新入队：• $B \to A$ (已在队列中，不重入)• $C \to A$ (无约束，忽略)
2	$B \to A$	$B < A$	检查 $D(B)=\{1,2,3\}$ 且此时 $D(A)=\{2,3\}$ :• $B=3$ : $D(A)$ 中无任何元素比它大 ( $3 \nless 2, 3$ ) $\to$ 修剪 3• $B=1,2$ : 均能在 $D(A)$ 中找到对应的 $A=2,3$ 满足条件 $\to$ 保留	$D(B) \gets \{1, 2\}$	因 $D(B)$ 改变，所有指向 $B$ 的弧重新入队：• $A \to B$ (重新入队)• $C \to B$ (重新入队)
3	$B \to C$	$B = C$	检查 $D(B)=\{1,2\}$ 且 $D(C)=\{1,2,3\}$ :• $B=1 \to C=1$ (合法)• $B=2 \to C=2$ (合法)无需修剪。	$D(B) = \{1, 2\}$	无改变
4	$C \to B$	$C = B$	检查 $D(C)=\{1,2,3\}$ 且 $D(B)=\{1,2\}$ :• $C=3$ : $D(B)$ 中无对应元素相等 $\to$ 修剪 3• $C=1,2$ : 合法。	$D(C) \gets \{1, 2\}$	因 $D(C)$ 改变，指向 $C$ 的弧入队：• $B \to C$ (重新入队)
5	$A \to B$ (复审)	$A > B$	检查 $D(A)=\{2,3\}$ 且 $D(B)=\{1,2\}$ :• $A=2$ : 对应 $B=1$ (满足 $2 > 1$ )• $A=3$ : 对应 $B=1$ 或 $2$ (满足 $3>1$ )无需修剪。	$D(A) = \{2, 3\}$	无改变
6	$B \to C$ (复审)	$B = C$	检查 $D(B)=\{1,2\}$ 且 $D(C)=\{1,2\}$ :相互完美对应，无需修剪。	$D(B) = \{1, 2\}$	无改变

AC-3 最终输出结果：

$D(A) = \{2, 3\}, \quad D(B) = \{1, 2\}, \quad D(C) = \{1, 2\}$

💡 总结： 通过 AC-3 的约束传播，我们在没有进行任何搜索（Search）的前提下，就已经将状态空间由原先的 $3 \times 3 \times 3 = 27$ 种可能，压缩到了 $2 \times 2 \times 2 = 8$ 种，极大地减轻了后续回溯搜索的负担！

4. 变量/值排序启发式与树结构 CSPs (Ordering & Tree-Structured CSPs)

4.1 排序启发式 (Ordering Heuristics)

回溯搜索中，以什么顺序挑选变量以及以什么顺序尝试其取值，对搜索效率有着决定性影响：

最少剩余值 (Minimum Remaining Values, MRV):
- 法则： 优先给最受约束（当前值域最小）的变量赋值。
- 哲学： “最不容易成功的先试（Fail-fast）”，如果这个变量注定会失败导致回溯，尽早发现，避免做无用功。
最少约束值 (Least Constraining Value, LCV):
- 法则： 优先尝试对相邻未赋值变量的值域剪枝最少（留给别人空间最大）的值。
- 哲学： 我们希望能尽快找到一个可行解，所以挑选胜率最高、最宽容的值。

4.2 🌲 深度解析：树结构 CSP 问题的线性时间求解 (Tree-Structured CSPs)

手写笔记难点攻克：“树结构的 CSP 问题解决我完全没懂”

不要担心！树结构 CSP 算法是整个 CSP 章节中最精妙、最优雅的算法。它的神奇之处在于：如果一个 CSP 的约束图是一棵树（无环），那么我们可以在 $O(N d^2)$ 的线性时间内百分之百求出解，且在这个过程中不需要任何回溯！

4.2.1 算法核心原理：

假设有 $N$ 个变量，值域大小为 $d$ 。

第一步：拓扑排序 (Topological Sort)

在约束树中任意选择一个变量作为根节点（比如 $X_1$ ）。
将树进行有向化（所有边都从根节点指向叶子节点）。
得到一个拓扑序列： $[X_1, X_2, \dots, X_n]$ ，保证任何一个节点 $X_i$ 的父节点 $P(X_i)$ 在序列中都排在 $X_i$ 的前面。

       [ X1 ] (根)
       /    \
   [ X2 ]  [ X3 ]
   /
[ X4 ]

拓扑序列： $[X_1, X_2, X_3, X_4]$

第二步：逆向弧一致性检查 (Backward Pass / Leaf-to-Root)

我们从序列的最后一个元素开始，逆向遍历到第二个元素（即从叶子节点到根节点，对于上面的树，顺序为 $i = 4, 3, 2$ ）：

让父节点 $P(X_i)$ 与子节点 $X_i$ 达成弧一致：即调用 REVISE(P(X_i), X_i)。
为什么这样做？ 因为这样可以把不相容的值“自底向上”地过滤掉。当我们把每个父节点关于其子节点的冲突值剔除后，能保证：一旦父节点分配了任何一个剩余的值，子节点在后续的赋值中都绝对能找到与之一致的取值。

第三步：顺向赋值 (Forward Pass / Root-to-Leaf)

我们按照拓扑序列从前往后（从根到叶，即 $i = 1, 2, 3, 4$ ）：

依次给 $X_i$ 赋值。
在为 $X_i$ 选择取值时，只需要选择一个与它的父节点 $P(X_i)$ 已分得的值相容的值即可。
由于我们在第二步中已经自底向上做过完整的弧一致过滤，这里绝对能找到相容的值，因而整个过程一路绿灯，不需要任何回溯！

4.2.2 复杂度分析

每次 REVISE 的代价为 $O(d^2)$ 。
一共需要进行 $N-1$ 次 REVISE 运算。
总时间复杂度： $O(N d^2)$ 。相比普通 CSP 动辄 $O(d^N)$ 的指数级时间复杂度，这简直是降维打击！

5. 局部搜索与遗传算法 (Local Search & Genetic Algorithms)

5.1 局部搜索：最小冲突启发式 (Min-Conflicts Heuristic)

思想： 局部搜索不使用“部分赋值”（不像回溯那样一个一个放），而是从一个完全赋值（即便它违反了约束）开始，然后不断局部调整以消除冲突。
步骤：
1. 随机生成一个对所有变量的完全赋值。
2. 只要当前赋值仍然存在冲突：
  - 随机选择一个有冲突的变量 $X$ 。
  - 将 $X$ 的值修改为能使当前总冲突数降到最低的值（即最小冲突启发式）。
优点： 极为高效。例如在解决 $N$ 皇后问题时，最小冲突算法几乎能在常数时间内解决百万级别的皇后放置问题。

5.2 🧬 深度解析：遗传算法 (Genetic Algorithms, GA)

手写笔记难点攻克：“我不太理解遗传算法”

遗传算法是模拟达尔文自然选择学说（优胜劣汰、适者生存）的一种随机全局搜索算法。在 CSP 中，我们不只保留一个状态，而是维护一个包含多个状态的种群 (Population)，让它们像生物进化一样进行繁衍。

我们用一个极简的例题来生动拆解其核心步骤：

5.2.1 遗传算法的 5 大核心要素

1. 状态编码（染色体 / Chromosome）

每一个个体的“染色体”代表了对 CSP 的一个完全赋值。

例：假设有 4 个变量 $A, B, C, D$ ，值域均为 $\{1, 2, 3, 4\}$ 。
某个体 1 的基因编码为：[2, 4, 1, 3]（即 $A=2, B=4, C=1, D=3$ ）。
另一个体 2 的基因编码为：[1, 3, 2, 4]。

2. 适应度函数 (Fitness Function)

用于评价一个状态（个体）有多优秀。在 CSP 中，适应度通常定义为满足的约束数量，或者未发生冲突的变量对数。适应度越高，越容易生存下来。

3. 选择 (Selection)

根据适应度高低，从种群中挑选父母。适应度越高的个体，被选去生孩子的概率就越大（常用方法如“轮盘赌选择”）。

4. 交叉 (Crossover / 重组)

模拟有性繁殖，将两个父母的基因片段拼接，产生下一代（子代）。

单点交叉示例：
- 设定交叉点在第 2 个位置：
  - 父亲：[2, 4 | 1, 3]
  - 母亲：[1, 3 | 2, 4]
- 交叉产生的两个子代：
  - 孩子甲：[2, 4, 2, 4] (继承了父亲的前半段和母亲的后半段)
  - 孩子乙：[1, 3, 1, 3]

5. 变异 (Mutation)

以一个极小的概率，随机改变子代染色体中的某一个基因，以防止种群基因单一化，跳出局部最优。

变异示例：
- 孩子甲：[2, 4, 2, 4] $\xrightarrow{\text{变异}}$ [2, 4, 4, 4]（第 3 个位置的基因由 2 随机变异为了 4）。

5.2.2 遗传算法求解流程图：

$\text{初始种群} \to \text{计算适应度} \to \text{选择优秀父母} \to \text{交叉产生后代} \to \text{基因变异} \to \text{新一代种群} \to \text{循环往复}$

当种群中进化出了适应度达到最大值（无冲突）的个体时，算法终止，该个体即为满足所有约束的解。