约束满足问题
《人工智能现代方法》读书笔记
本章聚焦约束满足问题（CSP），是比通用搜索更高效的一种问题建模方法。核心内容：
CSP的基本要素
变量、值域、约束（一元、二元、全局）。
约束图：节点为变量，边为二元约束。
回溯搜索
深度优先+约束检测。实用改进：
变量排序：最少剩余值（MRV）、度启发式。
值排序：最少约束值（LCV）。
前向检查：赋值后从相邻变量值域中删除不合法值，提前检测失败。
约束传播
弧一致性（AC-3）：保持所有弧的二元约束满足，删除值域中无支持的值。
相关概念解释
约束问题（CSP）的形式化定义：
- X 是变量集合，
- D 是域集合，{D1,...,Dn}，每个变量有一个域
- C 约束集合，用来规定允许值的组合。对应实际问题的限制条件，例如两个相邻区域色彩不能相同
让我们用一个贯穿始终的生动例子来解释CSP中的各种概念：“动物派对排座位”。
假设你要安排大象、斑马、企鹅三只动物坐在一排三个座位上（座位1、2、3）。每个动物有喜欢的颜色（红、蓝、绿）和食物（草、鱼、肉）。问题涉及多种约束，我们逐一展开。
一、基本概念：离散有限域、线性/非线性约束、一元/二元/全局约束
- 离散有限域：每个变量的取值来自有限、可数的集合。例如大象的座位域是{1,2,3}，颜色域是{红,蓝,绿}。这就是离散且有限的。
- 线性约束：约束可以写成变量乘以系数的线性等式或不等式。例如“大象的座位号 ≤ 斑马的座位号”（座位1≤座位2）是线性约束。
- 非线性约束：约束涉及乘法、取模、绝对值等。例如“大象和斑马的座位号之差的绝对值 ≠ 1”（不能相邻）是非线性的（绝对值）。
- 一元约束：只涉及单个变量。例如“企鹅不能坐座位2”。
- 二元约束：涉及两个变量。例如“大象和斑马不能同座”。
- 全局约束：涉及任意多个变量。例如“所有动物的座位互不相同”（Alldiff），它等价于多个二元不等约束的集合，但作为整体更高效。
二、一致性概念（用于约束传播）
1. 节点一致（Node Consistency）
定义：单个变量值域中的所有值都满足它的一元约束。
例子：如果一元约束“企鹅不能坐座位2”，那么企鹅的值域{1,2,3}中需要删除2 → {1,3}。达到节点一致。
2. 弧一致（Arc Consistency）
定义：对每个二元约束，变量域中每个值在另一变量域中都有至少一个值使其满足约束。
生动解释：大象和斑马有“不能同座”约束。检查大象的座位1：斑马域中要有不是1的值（有2,3）→ ok；大象座位2：斑马要有不是2的值→ ok；大象座位3：ok。反过来检查斑马也一样。如果某值找不到搭档，就删除它。
作用：弧一致是CSP中最常用的传播技术，例如AC-3算法。
3. 路径一致（Path Consistency）
定义：通过三元变量间的约束，检查任意一对变量在第三个变量的帮助下是否相容。
例子：大象、斑马、企鹅三个变量。大象和斑马不能同座，斑马和企鹅不能同座，大象和企鹅没有直接约束。路径一致会检查：是否存在一个斑马的座位值，使得大象和斑马、斑马和企鹅都相容？如果不存在，则调整大象和企鹅的值域。
比喻：通过中间人（斑马）来调节另外两个人的关系。
4. K一致（K-Consistency）
定义：对于任意K-1个变量的相容赋值，总能给第K个变量赋值使其与前面相容。
直观：K=2就是弧一致（任意一个变量，总能找到另一个变量的值满足约束）。K=3是路径一致。
强K一致：对于所有j≤K，都是j一致的。强K一致意味着无需回溯就能找到解（如果存在）。
5. 边界传播（Bound Propagation）
用于连续域或有序域的数值约束。通过约束不等式，逐步收紧变量的上下界。
例子：大象的座位≤斑马的座位，且大象座位≥1，斑马座位≤3。初始大象[1,3]，斑马[1,3]。传播：斑马≥大象，所以斑马下界≥大象下界；大象上界≤斑马上界。反复收紧直到稳定。
三、求解算法
1. 回溯搜索（Backtracking Search）
思想：深度优先搜索，每次给一个变量赋值，若违反约束则回退到上一个变量尝试其他值。
生动例子：你依次安排大象、斑马、企鹅的座位。
- 大象坐1。
- 斑马坐2（检查：与大象不同，ok）。
- 企鹅只能坐3（检查与斑马不同，与大象不同，ok）。找到解。
- 如果企鹅没位置了，就回退到斑马换座位（例如换到3），再试企鹅。
这是CSP的最基本求解器。
2. 局部搜索（Local Search for CSP）
思想：不完整搜索，从一个完整但可能违反约束的赋值开始，通过修改变量的值（例如随机或选择冲突最小的）来逐步减少冲突数量。
生动例子：你随便给三只动物各分配一个座位（可能冲突）。然后每次都选一个冲突最多的动物，换到另一个座位使得冲突减少。重复直到无冲突或达到时间上限。
典型算法：最小冲突启发式（Min-Conflicts），非常高效，尤其适合大规模CSP（如百万皇后问题）。
总结表
| 概念 | 通俗解释 |
|---|---|
| 离散有限域 | 变量取值像选择题，选项固定且数量有限 |
| 线性约束 | 像“我的年龄≤你的年龄” |
| 非线性约束 | 像“我们不能相邻坐” |
| 一元约束 | 只限制一个变量，如“企鹅不能坐1号” |
| 二元约束 | 限制两个变量，如“大象≠斑马” |
| 全局约束 | 同时限制多个变量，如“所有动物座位互异” |
| 节点一致 | 把明显违规的选项删掉 |
| 弧一致 | 确保每对变量之间都有“搭档” |
| 路径一致 | 通过第三方间接检查关系 |
| K一致/强K一致 | 任意K个变量都能协调 |
| 边界传播 | 通过不等式收紧取值范围 |
| 回溯搜索 | 尝试赋值，碰壁就回退 |
| 局部搜索 | 从乱分配开始，逐步改到无冲突 |
希望这个“动物派对”的例子能让你轻松记住CSP的核心概念。如果你需要进一步讲解某个算法的伪代码或实现细节，随时告诉我。
为什么介绍 CSP
之前的搜索算法依赖于特定领域迭代启发算法进行状态空间的搜索，然后我认为并不是每个人都能成为问题领域的专家，所以要发明一种 不依赖于领域专家的解决问题的思路，所以需要通用的启发式算法，CSP就是这样一种通用的启发式算法。
CSP的结构
树形CSP：可在线性时间求解（通过拓扑排序+方向弧一致）。
树分解：将一般CSP转化为树形子问题（降低复杂度）。
局部搜索
最小冲突法：随机初始解，迭代减少冲突，常用于大规模CSP（如N皇后）。