2.1 约束满足问题 (Constraint Satisfaction Problems)
在之前的笔记中，我们学习了如何找到搜索问题的最优解，这是一种规划问题 (planning problem)。现在，我们将学习解决一类相关的问题，即约束满足问题 (constraint satisfaction problems, CSPs)。与搜索问题不同，CSPs 是一种识别问题 (identification problem)，在这类问题中，我们只需要识别一个状态是否是目标状态，而不在乎我们是如何到达该目标的。CSPs 由三个因素定义：
- 变量 (Variables) - CSPs 拥有一组 \(N\) 个变量 \(X_1, \dots, X_N\)，每个变量都可以从某个定义的数值集合中取一个值。
- 定义域 (Domain) - 一个集合 \(\{x_1, \dots, x_d\}\)，代表一个 CSP 变量可以取的所有可能值。
- 约束 (Constraints) - 约束定义了对变量取值的限制，可能涉及到其他变量。
考虑 \(N\)-皇后识别问题：给定一个 \(N \times N\) 的棋盘，我们能否找到一种配置，将 \(N\) 个皇后放置在棋盘上，使得没有两个皇后互相攻击？
我们可以将这个问题形式化为一个 CSP，如下所示：
- 变量 - \(X_{ij}\)，其中 \(0 \leq i, j < N\)。每个 \(X_{ij}\) 代表我们 \(N \times N\) 棋盘上的一个网格位置，\(i\) 和 \(j\) 分别指定行号和列号。
- 定义域 - \(\{0, 1\}\)。每个 \(X_{ij}\) 可以取值 0 或 1，这是一个布尔值，代表棋盘上位置 \((i, j)\) 是否存在皇后。
- 约束 -
- \(\forall i,j,k \:\: (X_{ij}, X_{ik}) \in \{(0, 0), (0, 1), (1, 0)\}\)。这个约束表明，如果两个变量具有相同的 \(i\) 值，它们中只能有一个取值为 1。这有效地封装了没有两个皇后可以在同一行的条件。
- \(\forall i,j,k \:\: (X_{ij}, X_{kj}) \in \{(0, 0), (0, 1), (1, 0)\}\)。与前一个约束几乎相同，这个约束表明，如果两个变量具有相同的 \(j\) 值，它们中只能有一个取值为 1，封装了没有两个皇后可以在同一列的条件。
- \(\forall i,j,k \:\: (X_{ij}, X_{i+k,j+k}) \in \{(0, 0), (0, 1), (1, 0)\}\)。同理，我们可以看到这个约束和下一个约束分别代表了没有两个皇后可以在同一主对角线或副对角线上的条件。
- \(\forall i,j,k \:\: (X_{ij}, X_{i+k,j-k}) \in \{(0, 0), (0, 1), (1, 0)\}\)。
- \(\sum_{i,j}X_{ij} = N\)。这个约束表明我们必须恰好有 \(N\) 个网格位置标记为 1，其他所有位置标记为 0，捕捉了棋盘上必须恰好有 \(N\) 个皇后的要求。
约束满足问题是 NP-难 (NP-hard) 的，这大致意味着不存在已知的算法可以在多项式时间内找到它们的解。给定一个有 \(N\) 个变量的问题，每个变量的定义域大小为 \(O(d)\)，则有 \(O(d^N)\) 种可能的赋值，这是变量数量的指数级。我们通常可以通过将 CSPs 形式化为搜索问题来绕过这个限制，将状态定义为部分赋值 (partial assignments)（即 CSPs 的变量赋值，其中一些变量已被赋值，而其他变量尚未赋值）。相应地，CSP 状态的后继函数输出所有分配了一个新变量的状态，目标测试验证它正在测试的状态中所有变量都已赋值且所有约束都已满足。约束满足问题往往比传统的搜索问题具有更多的结构，我们可以通过将上述形式化与适当的启发式方法相结合来利用这种结构，从而在可行的时间内找到解。
2.1.1 约束图 (Constraint Graphs)
让我们介绍第二个 CSP 示例：地图着色。地图着色解决的问题是：给定一组颜色，必须给地图着色，使得没有两个相邻的州或区域具有相同的颜色。
约束满足问题通常表示为约束图，其中节点表示变量，边表示它们之间的约束。有许多不同类型的约束，每种约束的处理方式略有不同：
- 一元约束 (Unary Constraints) - 一元约束涉及 CSP 中的单个变量。它们不在约束图中表示，而是在必要时仅用于修剪它们约束的变量的定义域。
- 二元约束 (Binary Constraints) - 二元约束涉及两个变量。它们在约束图中表示为传统的图边。
- 高阶约束 (Higher-order Constraints) - 涉及三个或更多变量的约束也可以用 CSP 图中的边来表示，它们看起来稍微有些不同寻常。
考虑为澳大利亚地图着色：
这个问题中的约束很简单，即没有两个相邻的州可以是相同的颜色。因此，通过在每对相邻的州之间画一条边，我们可以生成澳大利亚地图着色的约束图，如下所示：
约束图的价值在于我们可以利用它们来提取关于我们正在解决的 CSPs 结构的宝贵信息。通过分析 CSP 的图，我们可以确定诸如它是稀疏连接还是紧密连接/受限，以及它是否是树状结构等信息。当我们更详细地讨论解决约束满足问题时，我们将更深入地讨论这一点。