1. 什么是约束满足问题（CSP）？

约束满足问题（CSP）是一类特殊的搜索问题，具有以下特点：

• 变量（Variables）：一组变量，每个变量有一个取值域。
• 值域（Domain）：每个变量的取值来自于一个特定的集合。
• 约束（Constraints）：定义了哪些变量的值可以组合在一起。

问题定义

• 状态：部分赋值（Partial Assignment），即某些变量已被赋值。
• 目标测试：检查当前赋值是否满足所有约束。
• 后继函数：为一个未赋值的变量分配一个值。

约束满足问题的实例：

• 地图着色问题（Map Coloring）：
  • 变量：各州（WA, NT, Q, NSW, V, SA）
  • 约束：相邻的州不能有相同的颜色（如：WA ≠ NT）。

2. 约束类型

• 一元约束：仅限制单个变量的取值。例如：$SA \neq green$。
• 二元约束：限制两个变量的取值。例如：$SA \neq WA$。
• 全局约束：限制多个变量的取值。
• 偏好约束：指示哪些解更优，例如：红色优于绿色。

3. 约束传播（Constraint Propagation）

约束传播是CSP中的一个推理过程，它通过减小变量的取值范围来缩小搜索空间。它包括以下几个主要概念：

节点相容（Node Consistency）

• 如果一个变量的所有取值都满足它的一元约束，则该变量是节点相容的。

弧相容（Arc Consistency）

• 如果某个变量的所有取值都满足该变量与其他变量的二元约束，则该变量是弧相容的。
• AC-3 算法用于检查和维护弧相容性，帮助减少不可能的值域。

路径相容（Path Consistency）

• 给定一对变量，确保它们与第三个变量的取值组合满足二元约束。

k-相容性（k-Consistency）

• CSP的k-相容性表示在给定k-1个变量的取值情况下，如何为第k个变量选择合适的取值，使其与前k-1个变量相容。

4. CSP 求解方法

回溯搜索（Backtracking Search）

• 回溯搜索是一种基础的无信息算法，通过逐步赋值来探索解空间。
• 每次赋值时检查约束，若违反约束则回溯。

回溯搜索的改进

• 最少剩余值（MRV）：优先选择值域最小的变量进行赋值，避免在较晚阶段遇到困难。
• 最少约束值（LCV）：选择对邻居变量留下最多选择的值。
• 前向检查（Forward Checking）：在给变量赋值后，立即检查与之相关的未赋值变量，剔除无效的值。

启发式方法

• 度启发式（Degree Heuristic）：选择与其他未赋值变量约束最多的变量进行赋值，减少未来的分支因子。

5. CSP 的优化

弧一致性和前向检查

• 弧一致性：通过传播约束来确保所有变量之间的取值保持一致。它可以通过AC-3算法进行实现。
• 前向检查：赋值时检查与已赋值变量相关的所有未赋值变量，剔除无效取值。

问题结构（Problem Structure）

• 分解问题：在现实世界问题中，很多问题可以分解成多个子问题，例如独立的子问题。
• 树形结构：对于树形结构的CSP，可以在线性时间内求解。若约束图有环，需要通过节点删除或合并方法将其转化为树形结构。

剪切集（Cutset Conditioning）

• 通过赋值某些变量，使得剩余的约束图变为树形结构，简化求解过程。

6. 现实世界中的CSP应用

CSP被广泛应用于许多实际问题，包括：

• 调度问题：如班级时间表安排。
• 任务分配问题：如任务和工作分配。
• 硬件配置：如电路设计中的元件配置。
• 交通调度：如公交线路安排等。

7. 局部搜索（Local Search）

• 局部搜索是解决CSP的一种有效方法，通常用于求解大规模问题。局部搜索通过修改已赋值的变量的值，逐步逼近目标解。

8. 例题 课程调度问题（Course Scheduling）

你负责安排一组电气工程课程的课程时间表，这些课程将在周一、周三和周五上课。共有5门课程，并且3名教授将负责这些课程。每个教授只能教一门课。

课程信息：

1. Class 1 - Circuits and Systems: 8:00 - 9:00 am
2. Class 2 - Digital Logic Fundamentals: 8:30 - 9:30 am
3. Class 3 - Electromagnetic Fields and Waves: 9:00 - 10:00 am
4. Class 4 - Control Systems: 9:00 - 10:00 am
5. Class 5 - Microprocessors and Digital Systems: 9:30 - 10:30 am

教授信息：

1. Professor A：有资格教授Class 3和Class 4。
2. Professor B：有资格教授Class 2、3、4和5。
3. Professor C：有资格教授Class 1、2、3、4和5。

(a) 将此问题表述为CSP问题

变量（Variables）：

每个课程都是一个变量，即：

• $C_1$：Class 1
• $C_2$：Class 2
• $C_3$：Class 3
• $C_4$：Class 4
• $C_5$：Class 5

值域（Domains）：

• $C_1$：可能的教授为 {A, B, C}
• $C_2$：可能的教授为 {B, C}
• $C_3$：可能的教授为 {A, B, C}
• $C_4$：可能的教授为 {A, B, C}
• $C_5$：可能的教授为 {B, C}

约束（Constraints）：

1. 每个教授只能教授一门课程，因此同一教授不能同时安排多门课程。
2. 每门课程的教授必须在其对应的值域内选择。

(b) 绘制CSP的约束图

• 约束图：每个节点代表一个课程，每条边表示两个课程之间的约束关系。
• 约束关系：如果两个课程由同一教授教授，则它们之间有约束。

(c) 给出一个满足所有约束的解

一种可能的解：

• $C_1 = C$
• $C_2 = B$
• $C_3 = A$
• $C_4 = C$
• $C_5 = B$

这个解满足所有约束，即每个教授只教授一门课程，且每门课程的教授来自其可选的教授集合。