Constraint Satisfaction Problems

最开始的人工智能做的都是search，而之后的机器学习才开始做inference，会自己学习知识。而CSP问题则介于两者之间，它会把inference的思路融入到search中，这是人工智能的一大进步，智能体在搜索的时候会进行思考。

Constraint Satisfaction Problems(CSP)

What is Search For?

一种问题是寻找路径，即一系列行动。
另一种是识别，识别最终的目标状态，路径则不重要。

这里的目标满足问题(CSP)主要关心识别的问题，即只关心最终状态，不关心路径。

State Representation

对于CSP问题

一个状态由一系列变量 $X_{i}(i=1, 2, \ldots n)$ 的集合构成，值域为 $D_i$
目标测试由一系列约束 $C_i(i=1, 2, \ldots m)$ 来决定。

CSP问题相较于之前搜索算法的进步：

原子状态(atomic state) $\rightarrow$ (factored state)
搜索(search) $\rightarrow$ 搜索+推断(inference)
特定算法(specific) $\rightarrow$ $\to$ 通用算法(general)
- 搜索问题对于每个问题都需要根据问题进行设计，而CSP问题则有一些通用的算法，只要问题能够建模成CSP问题，就能用特定的算法解决。

Example: Map-Coloring

变量：WA，NT，Q，NSW，V，SA，T
定义域： $D_i$ = {red, green, blue}
约束：相邻区域必须颜色不同

将其抽象成一个约束满足问题：

一个节点对应一个变量，一条边对应一个约束。

把这个问题当成约束满足问题，相比最简单的搜索问题，一个优势是可以减小搜索空间，加快搜索。

Varieties of CSPs

变量取离散值
- 有限域，假如有 $n$ 个变量， $d$ 种取值，那么会有 $O(d^{n})$ 种选择
- 无限域，那么就需要一些约束条件
连续变量
- 有各种约束和优先级，可能用线性规划来解决

Standard search formulation (incremental)

对于所有的约束满足问题，初始状态、目标测试和后继函数都可以进行统一的定义

初始状态：空的指派
后继函数：选择一个还未赋值变量对其进行控制
目标测试：看所有变量的赋值有没有冲突

Backtracking Search

回溯搜索本质上也是一种深度优先搜索，我们把用于约束满足问题的单变量赋值的深度优先搜索称为回溯搜索。回溯搜索是一种没有信息指导的搜索，只需要在每个节点考虑单变量的赋值。

Two improvements

每次只考虑一个变量的赋值，并且变量的赋值是可交换的(即赋值的顺序不影响最终结果)
每一次赋值之后需要检查是否满足目标

搜索树越深，已经赋值的变量越多，需要检查的约束也越多。

地图染色的例子如下

Pseudo code

其中 $\text{SELECT-UNASSIGNED-VARIANBLE}(\text{VARIABLE}[csp], assignment, csp)$ 和 $\text{for each } value \text{ in ORDER-DOMAINJ-VALUES}(VAR, assignemnt, csp)$ 这两点都非常重要，选择策略是否合适会影响算法的效率。

改进回溯算法，就是需要改进这两个选择的函数。

Improving backtracking efficiency

对于变量的选择：

首先可以选择约束比较多的变量(most constrained variable)，比如说做数独的时候通常先填那些基本已经确定的，因为此时这个变量能够选择的空间就比较小。(minimum remaining values heuristic)
其次可以选择对其他变量影响最多的(most constraining variable, Tie-breaker)，即选择那些在约束条件中出现次数最多的。比如说地图染色中，我们会倾向于选择中间的点开始染色。

以上操作相当于做剪枝

对于变量的赋值：
选择对其他变量影响最少的(least constraining value)。