一、约束满足问题概述

1.1 什么是约束满足问题 (CSP)?

1.2 CSP 与标准搜索问题的区别

• 状态表示：标准搜索问题中，状态具有任意数据结构且通常是不可分割的“黑箱” ；而 CSP 中，状态由一组变量 Xi 及其在定义域 D 中的取值构成，采用因子化表示。

• 目标测试：标准搜索问题的目标测试可以是关于状态的任何函数 ；CSP 的目标测试是一组指定变量子集允许值组合的约束。

• 关注点：规划问题（标准搜索）中路径是重点；识别问题 (CSP) 中目标本身是重点，只要符合要求就OK

• 优势：CSP 通过识别违反约束的变量/值组合，可以一次性排除大量搜索空间。

二、CSP 的形式化定义与示例

2.1 CSP 的组成部分

• 变量 (Variables)：一组需要被赋值的实体 。

• 域 (Domains)：每个变量 可能取值的集合 D（有时域依赖于具体变量）。

• 约束 (Constraints)：规定变量子集之间允许的取值组合。

2.2 CSP 示例

• 地图着色问题 (Map Coloring)
• 问题描述：为地图上的每个区域选择一种颜色（如红、绿、蓝），使得相邻区域颜色不同。
• 变量：地图上的各个区域 (e.g., WA, NT, Q, NSW, V, SA, T)。
• 域：可用的颜色集合 (e.g., {红, 绿, 蓝})。
• 约束：相邻区域颜色必须不同 (e.g., WA≠NT)。
• 解：满足所有约束的变量赋值 (e.g.,{WA=red, NT=green,...})。

• N皇后问题 (N-Queens)
• 问题描述：在 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不能在同一行、同一列或同一对角线上。



• 形式化1：
• 变量：(表示棋盘第 i 行第 j 列是否放置皇后)。
• 域：{0, 1}。
• 约束：行约束、列约束、对角线约束，以及皇后总数为 N。
• 形式化2：
• 变量： (表示第 k 行皇后所在的列号)。
• 域：{1, 2, ..., N}。
• 约束：对于任意两个皇后，它们不能互相攻击。

• 密码算术问题 (Cryptarithmetic)
• 问题描述：给字母赋以不同的数字，使得算式成立。例如 TWO + TWO = FOUR。



• 变量：算式中的字母 (F, T, U, W, R, O) 以及进位 (X1,X2,X3)。
• 域：{0, 1, ..., 9}。
• 约束：不同字母代表不同数字 (alldiff)，以及算术规则 (e.g., O+O=R+10⋅X1)。

• 数独问题 (Sudoku)
• 问题描述：在 9×9 的格子中填入数字 1-9，使得每行、每列、每个 3×3 的子区域内数字不重复。



• 变量：每个待填的格子。
• 域：{1, 2, ..., 9}。
• 约束：每行、每列、每个子区域内数字不重复 (9-way alldiff)。

三、约束图 (Constraint Graphs)

• 定义：约束图的节点代表问题中的变量，连接两个变量的边表示它们之间存在约束。

• 二元 CSP (Binary CSP)：每个约束最多只涉及两个变量。 此时约束图为普通图。
• 类比为一个线段只有两个端点，可以用几何的方法直观表示

• 高阶约束与超图 (Higher-order Constraints&Hypergraphs )当约束涉及三个或更多变量时，可以使用超图来表示，其中超边连接所有参与该约束的变量（如密码算术问题中的列约束）。

• 作用：通用 CSP 算法利用约束图的结构来加速搜索。例如，可以识别出独立的子问题（如图中的塔斯马尼亚岛）。

四、CSP 的种类与约束类型

4.1 CSP 的种类

• 离散变量 (Discrete Variables)
• 有限域 (Finite domains)：例如布尔 CSP（包括布尔可满足性问题 SAT）。解空间大小为 。
• 无限域 (Infinite domains)：例如整数、字符串等。如工作调度问题，变量是每个工作的开始/结束时间。线性约束可解，非线性约束不可判定。

• 连续变量 (Continuous variables)：例如哈勃望远镜观测的开始/结束时间。
• 线性约束可以通过线性规划方法在多项式时间内求解。

4.2 约束的种类

• 一元约束 (Unary constraints)：只涉及单个变量，等价于缩减域 (e.g., SA=green)。

• 二元约束 (Binary constraints)：涉及一对变量 (e.g., SA=WA )。

• 高阶约束 (Higher-order constraints)：涉及三个或更多变量 (e.g., 密码算术中的列约束)。

• 偏好/软约束 (Preferences/Soft constraints)：表示某些赋值优于其他赋值 (e.g., 红色比绿色更好)。这类问题称为约束优化问题。

• 约束的简化：任何有限域约束都可以通过引入足够的辅助变量简化为一组二元约束。

五、求解 CSP 的方法

5.1 标准搜索形式化

• 状态：已赋值的变量集合（部分赋值）。

• 初始状态：空赋值 {}。

• 动作：为一个未赋值的变量赋一个值。

• 转移模型：产生新的赋值状态。

• 目标测试：当前赋值是完整的并且满足所有约束。

• 问题：朴素的搜索树叶子节点数量可能高达 ，即使只有 个可能的完整赋值。
• 这是因为n个变量是完全等价的，每个变量的顺序是任意的

5.2 回溯搜索 (Backtracking Search)

• 核心思想：
1. 逐个变量赋值：由于变量赋值具有交换性（例如，WA=red 然后 NT=green 与 NT=green 然后 WA=red 相同），固定变量赋值顺序，每一步只考虑为单个变量赋值。这样叶子节点数量降为 。
2. 边赋值边检查约束：只考虑那些不与先前赋值冲突的值，进行增量式目标测试。
3. 缺陷：检查的太晚了；一个初始的糟糕赋值可能已经引起冲突，但是要等到给冲突变量赋值我们才能发现。

• 算法描述：一种改进的深度优先搜索 (DFS)，结合了变量逐个赋值和冲突即失败的策略。

5.3 改进回溯搜索的通用策略

5.3.1 过滤 (Filtering)：提前检测失败

• 前向检查 (Forward Checking)
• 思想：当一个变量被赋值后，检查所有与该变量有约束的未赋值变量的域，去除那些与当前赋值冲突的值。



• 作用：传播已赋值变量到未赋值变量的信息，但不能检测所有失败。
• 这里的关键在于直接相连，我们检查的范围只限于已赋值的变量和未赋值的变量，检查存在盲区

一个具体的例子：地图着色问题

我们用你笔记中反复提到的澳大利亚地图着色问题来说明 。

问题设定:

• 变量: WA, NT, Q, SA, NSW, V, T

• 定义域: {红, 绿, 蓝}

• 约束: 相邻区域颜色不能相同。

搜索步骤与失败分析:

1. 初始状态: 假设所有变量的定义域都是 {红, 绿, 蓝}。

2. 赋值 WA = 红:
• 前向检查: 检查与 WA 相邻的 NT 和 SA。从它们的定义域中移除“红”。
• Domain(NT) 变为 {绿, 蓝}
• Domain(SA) 变为 {绿, 蓝}

3. 赋值 Q = 绿:
• 前向检查: 检查与 Q 相邻的 NT, SA, NSW。从它们的定义域中移除“绿”。
• Domain(NT) 之前是 {绿, 蓝}，现在变为 {蓝}。
• Domain(SA) 之前是 {绿, 蓝}，现在变为 {蓝}。
• Domain(NSW) 变为 {红, 蓝}。
• 此时，前向检查没有发现任何失败，因为没有一个变量的定义域变为空集。

潜在的失败: 我们停下来观察一下现在的局面。变量 SA 和 NSW 都还没有被赋值，但它们是相邻的，所以它们的值必须不同 (SA ≠ NSW)。

然而，在给 Q 赋值为“绿”之后，我们发现：

• Domain(SA) 只剩下 {蓝}

• Domain(NT) 只剩下 {蓝}

虽然我们还没给 SA 和 NT 赋值，但它们各自只剩唯一的选择“蓝色”。由于 SA 和 NT 相邻，它们未来必定会发生冲突。这个失败已经是“板上钉钉”了。

• 约束传播 (Constraint Propagation) / 弧相容性 (Arc Consistency)
• 思想：不仅仅是从已赋值变量传播，而是在约束之间进行推理，使得整个约束网络达到自洽的状态
• 弧 X→Y 相容：对于变量 X 域中的每一个值 ，在变量 Y 的域中都至少存在一个值 ，使得 满足 X 和 Y 之间的约束。如果不相容，则从 X 的域中删除。



• AC-3 算法：一种维护弧相容性的算法。初始化一个包含 CSP 中所有弧的队列。当从队列中取出一个弧 (Xi,Xj) 时，检查其相容性，如果 Xi 的域因此缩小，则将所有指向 Xi 的邻居弧 (Xk,Xi) 加入队列重新检查。
• 效果：弧相容性比前向检查能更早地检测到失败，可以在每次赋值后运行。

5.3.2 排序 (Ordering)：选择变量和值的顺序

• 变量排序 (Variable Ordering)
• 最少剩余值 (Minimum Remaining Values - MRV)：选择域中剩余合法值最少的变量进行赋值，也称为“最受约束变量”(Most Constrained Variable)。



• 度启发式 (Degree Heuristic)：选择与最多其他未赋值变量相关的变量（即在约束图中度数最高的变量），通常作为 MRV 的平局打破规则。
• 如果这个变量确定，那么会带来最多的限制条件

• 值排序 (Value Ordering)
• 最少约束值 (Least Constraining Value - LCV)：对于选定的变量，选择那个对其他未赋值变量的域排除的值最少的值。这可能需要一些计算来确定（例如，重新运行过滤）。

• 效果：结合这些排序思想，可以使得求解如 1000 皇后问题变得可行。

5.3.3 结构 (Structure)：利用问题结构

• 独立子问题 (Independent Subproblems)
• 如果约束图可以分解为互不相连的连通分量，那么这些分量可以独立求解。
• 若一个包含 n 个变量的问题可以分解为 c 个变量的子问题，则最坏情况下的求解代价从 降至 。

• 树结构 CSP (Tree-Structured CSPs)
• 定理：如果约束图无环（即为树），则 CSP 可以在 时间内求解。



• 算法：
1. 排序：选择一个根变量，对变量进行拓扑排序，使得父节点在子节点之前。
2. 反向移除不一致：从叶节点向根节点方向 (i=n 到 2)，对每个节点 Xi 和其父节点 Parent(Xi)，应用 RemoveInconsistent(Parent(Xi),Xi) 使弧 (Parent(Xi)→Xi) 相容。
3. 正向赋值：从根节点向叶节点方向 (i=1 到 n)，为每个 Xi 选择一个与其父节点 Parent(Xi) 的赋值相容的值。



• 正确性：反向传递后，所有从根到叶的路径上的弧都是相容的，因此正向赋值不会发生回溯。
• 局限性：此算法不适用于有环的约束图，因为值的删除可能会沿着环传播回来，使得之前确保的相容性失效。

• 近似树结构 CSP / 切集条件化 (Nearly Tree-Structured CSPs / Cutset Conditioning)
• 思想：通过实例化一小部分变量（称为切集, cutset），使得剩余的约束图变成树结构。



• 过程：
1. 选择一个切集（一般选择最小割集）。
2. 对切集中的变量进行所有可能的赋值组合。
3. 对于每一种赋值，计算剩余的 CSP（此时为树结构）。
4. 求解这些树结构的剩余 CSP。
• 复杂度：如果切集大小为 c，则运行时间为，对于小的 c 非常快。

例题

5.4 迭代算法 (Iterative Algorithms for CSPs) / 局部搜索 (Local Search)

• 基本思想：从一个可能不满足所有约束的完整赋值开始，通过修改变量的值来逐步减少不满足的约束数量。

• 特点：没有前沿（frontier），内存高效，通常更快，但不完备且可能非最优，适用于样本空间很大甚至是连续的场景

• 值选择：需要给定一个函数来描述系统当前状态的好坏；给出一个评价和比较的标准

最小冲突启发式 (Min-Conflicts Heuristic)

• 算法：当未解决时：
1. 变量选择：随机选择任何一个有冲突的变量（即参与了未满足约束的变量）。
2. 值选择：选择一个使得违反约束数量最小的值（即采用爬山法，目标函数 为违反约束的总数）。

• 性能：对于随机生成的 CSP，除了在约束数量与变量数量之比 R 处于某个狭窄的“困难”区域外，该算法通常能在接近常数的时间内解决问题（例如 N 皇后问题，当 N 很大时）。

5.5 高级局部搜索技术

爬山法 (Hill Climbing)

• 首先进行值选择，描述当前状态

• 思想：持续向值更优（或代价更低）的方向移动。如果当前状态的所有邻居都不比当前状态更优，则停止。

• 缺点：
• 不完备 (Incomplete)：可能陷入局部最优（local maximum）、平坦区域（"flat" local maximum，无法选择下一步）或山脊（shoulder，向上移动困难）。



• 非最优 (Not Optimal)：找到的很可能是局部最优而非全局最优。

• 优点：简单，内存占用少。

• 成功性：很大程度上取决于状态空间的地形。

模拟退火 (Simulated Annealing)

• 思想：通过允许“下坡”移动来跳出局部最优，但随着时间的推移使这种下坡移动的概率越来越小（因为随着时间的推移已经找到全局最优解的概率越来越大）。 其灵感来源于物理冶金中的退火过程。

• 算法： 其中， 是值的变化量， 是当前的“温度”。如果(找到了更好的状态)，则接受；否则，以概率 接受（，所以概率小于1）。

• 理论保证：如果温度 T 下降得足够慢，算法将收敛到全局最优状态。然而，实际中需要逃离的局部最优越深，连续走出所有下坡步骤的概率就越低。

遗传算法 (Genetic Algorithms - GA)

• 思想：借鉴自然选择和遗传学的隐喻，维护一个状态“种群”，通过选择、交叉（crossover）和突变（mutation）等操作产生下一代种群。

• 关键操作：
• 编码 (Coding)：将问题的解表示为“染色体”。
• 适应度函数 (Fitness Function)：评估每个个体的优劣。
• 选择 (Selection)：根据适应度选择父代。
• 交叉 (Crossover)：组合两个父代的“基因”产生子代。当两个父代状态差异较大时，交叉操作可能产生一个远离任一父代的新状态，有助于早期探索大的状态空间。
• 突变 (Mutation)：随机改变子代的某些“基因”。

• 适用性：对于 N 皇后问题，交叉操作有意义，因为它可能组合不同解决方案的良好部分。

其他元启发式算法 (Other Metaheuristics)

• 元启发式定义：指导搜索过程的策略，非问题特定，目标是高效探索搜索空间以找到近似最优解。通常是近似且不确定性的。

• 粒子群优化 (Particle Swarm Optimization - PSO)：每个粒子的运动受其自身历史最佳位置和群体全局最佳位置的影响。

• 蚁群优化 (Ant Colony Optimization - ACO)：模拟蚂蚁通过信息素寻找路径的行为，信息素在较短路径上浓度较高。

六、CSP 总结

• CSP 是一类特殊的搜索问题，状态是部分赋值，目标测试由约束定义。

• 基本解决方法是回溯搜索。

• 加速技术包括排序、过滤和利用问题结构。

• 迭代的最小冲突算法在实践中通常很有效。