Algorithms in AI

Chapter 0. Intro

0.1 The definition of Artificial Intelligence

• Think rationally -> Think like people -> Act like people -> Act rationally.

  The system maximumly achieving predefined goals.

  -> Maximize the expected utility. (最大化预期效用)

• Brains and AI

  • Why not reverse engineering the brains? -> Not as modular as software.

  • But there are the lessons learned from the brain (interleave, 交织在一起):

    • Memory (data): Judge situations depending on the previous experiences (statistics).

      e.g., Bayes’ nets, Decision theory, Machine learning,…

    • Simulation (computation): Predict the future depending on the models.

      e.g., Search, Satisfying constraints, Adversarial and uncertain search,… (Algorithms)

0.2 The History of AI

0.3 The Applications of AI

• Natural language: speech technology (+context), language processing technologies (Q&A / translation / web search …);

• Computer vision (perception)

• Game playing;

• Logic: Theorems provers, NASA fault diagnosis, …

0.4 Designing Rational Agents

• Agent: An agent is an entity that perceives and acts.
• Environment -> sensors of an agent -> agent functions -> actuators -> effect on environment.

Chapter 1. Search

Discuss agents that plan ahead rather than just react to a current situation.

将现实问题 formalize 为数学问题，并使用算法模拟搜索求解。

1.1 Reflex Agents

• They have a current percept, and maybe make decision based on these memory but without consideration of the consequences of their actions.

  仅根据当前状态，直接进行当前最优动作；

  例如，根据当前 successor 的结果谁更接近 goal 就进行什么操作。

• 类似贪心算法，有时 rational，但有时并不是；

1.2 Planing Agents

• They have the model of what the world works, and the goals. 根据一系列动作，结合模型假设后果，并根据后果和目标的关系来决定是否进行这个操作。

  实现 1 (master-mind)：先遍历查找动作序列，再行动（时间花费很大）；

  实现 2 (re-planning)：先遍历最近的动作序列，行动，然后再遍历下一段的动作序列，再行动，以此往复（类似结合了贪心法的动态规划）；

• Optimal Planning（最优计划） & Complete Planning（能解决问题的存在性计划）

1.3 Search Problem（Uninformed Search）

1.3.1 Definitions

什么是计算机中的搜索问题？

• 一个搜索问题包含：

  • 状态空间（a state space，存放环境信息）；

  • 后继函数（a successor function，包含动作、动作开销）；

    有哪些可行的动作？动作执行后的结果状态如何？——这个函数编码了 “how the world works”

  • 初始状态（a start state）和目标检查（a goal test）；

• 搜索问题的解：就是一个从初始状态到目标状态的动作序列（a sequence of actions / a plan）.

以上可以称为搜索问题的模板，可以看作接口（interface），这意味着我们可以将现实生活中的问题抽象到上面的模板中（casting to search problem），再对照模板设计算法，就能解决实际问题。

1.3.2 Examples

搜索问题本质上是一个模型。举例：

• 城市导航路线图
  • state space: cities;
  • successor function: roads (go to adjacent cities with cost (可以是距离、交通情况等));
  • start state: 位于起点的状态；
  • goal test: 当前状态是否是位于终点的状态；
  • solution: 有向路径；
• pac-man 游戏（目标是走到指定位置）
  • state space: (x, y) 实体的位置信息；action: NSEW；successor function: update location only；goal test: 是否有 (x,y)==DESTINATION；
• pac-man 游戏（目标是吃完所有豆子）
  • state space: (x, y) 位置 + 是否有食物的布尔值；action: NSEW；successor function: 更新位置和食物情况；goal test: 是否有所有食物布尔值都为 false；

1.3.3 Mathematical & Algorithmic Representation

• 搜索问题的数学表示：状态图和搜索树（state space graphs & search tree）

  • 它们一般过于庞大，画不出来，只需要有这样的概念就行；
  • 搜索树结点数一般远大于状态图，因为搜索树中可以有多个结点代表同一个状态；

• 搜索树（General Tree Search）解决 等权 / 非等权搜索问题

  本部分就是数据结构中图的相关算法。涉及解决等权图最短路、非等正权图最短路等问题的经典算法。但有所不同，因为是 Tree Search，所以不会记录 visited 结点——意味着会重复搜索（具体会在 1.5 中进行阐释和改进）；

  • Important Ideas:

    • Fringe (原义条纹 / 边缘，这里指的是 a set of leaf nodes that are waiting to be expanded，通常是存放等待处理的数据结点的结构，可以是栈、队列等);
    • Expansion (查找过程中再向树中插入合法结点);
    • Exploration strategy (DFS / BFS / Uniform Cost Search)

  • Pseudo Code:

    

• Search Algorithm Properties of General Tree Search（针对所有 “利用搜索树” 解决搜索问题的算法）

  • 如果 expansion strategy 算法是 DFS：

    • 实现方式：栈；
    • 时间复杂度为 $O(b^m)$，b 为每个结点的后继结点数量级，m 为搜索树中最大深度的数量级；空间复杂度为 $O(b\cdot m)$；
    • 算法是 complete 的（如果对于无限树，且存在解，则能够找到至少一个解）；
    • 算法不是 optimal 的（DFS 无法自动找到最优解，除非你一直找，再手动比较）；

  • 如果算法是 BFS：

    • 实现方式：队列；
    • 时间复杂度为 $O(b^s)$，b 为每个结点的后继结点数量级，s 为搜索到最近的 goal state 所在层数的数量级；空间复杂度也是 $O(b^s)$;
    • 算法是 complete 的（不遍历结束、得出结果，则不会退出）；
    • 如果 cost 是相等的——即等权图，则算法是 optimal 的，因为按照层级（tier）从近处向远处找；

  • 综合上面特点发现，DFS 空间性能更好，但 BFS 能够找到等权情况下的最短路；那么我们有没有一种算法综合它们的优点呢？有的！它就是 Iterative Deepening；

    Iterative Deepening（迭代深搜）利用了 DFS 空间优势。在搜索开始后，先执行 DFS，以 depth=1 和 goal 为终止条件，如果找到，就结束；否则证明 depth=1 的深度无解，将 depth 结束条件放宽至 depth=2，继续 DFS，以此类推。

    这就将 DFS 和 BFS 的优势结合了起来。

    不用担心每次都把前几层重复检查，因为理论上搜索树每层结点指数增长，下一层结点数往往远大于前几层结点数之和，所以重复检查的部分微不足道。

  • Uniform Cost Search（UCS，一致代价搜索） 解决 Cost-sensitive Search（非等权搜索问题）

    • 实现方式：优先级队列；
    • 时间复杂度 $O(b^{C^*/\varepsilon})$，b 为每个结点后继结点数量级，C* 为解的 cost 数量级，ε 为各个结点间（每一步）的最小 cost 数量级；空间复杂度与时间相同；
    • 此算法借鉴了 BFS 的思路，在 expansion 的时候选取 cost 最小的；
    • 算法在最小权为正数的情况下是 complete 和 optimal 的。
    • 优点很好，但缺点也很严重——一般情况下开销极大，因为遍历了一个正权下的所有状态结点（可以通过 goal 的信息进行优化，后面介绍，就是 informed search）；

1.4 Informed Search

搜索问题的定义是相同的，只不过 informed search（有提示搜索）的 expanding strategy 会考虑到距离 goal 的远近程度（在 uninformed search 的基础上进行改进）而已。

所以下面仅比较不同的 expanding strategy。

1.4.1 Search Heuristics

启发式搜索，即启发函数，是后面 informed search 算法的基础。

• The definition for a heuristic

  • A function that estimates how close a state is to a goal.

  • Designed for a particular search problem （因为距离判断因问题而异）；

    可以是 Manhattan distance，Euclidean distance……（for pathing）

• Examples

  • The pac-man game（去往特定的有食物的地点）：“距离”（heuristic function）可以是与终点的欧式距离、曼哈顿距离（因为上下左右移动）；
  • The pancake problem（完成从上到下饼依此增大的排列）：heuristics function 可以是位置正确的煎饼个数、位置不正确的最大煎饼编号（因为和汉诺塔类似，势必要先把最大煎饼先挪到底层）；

  具体选择哪种 heuristic function，可以举几种固定情况（例如画一部分状态图），看谁的 heuristic function 的值在接近 goal 时表现更好。

1.4.2 Expanding Strategy: Greedy Search（贪婪法）

• 思路：选择 fringe 中 heuristic function 最接近 goal 的结点进行 expand；
• 优点：在某些情况下搜索非常迅速，并且开销很小；
• 缺陷：局部最优解不一定是全局最优解，即贪婪法不一定是正确的（算法不一定是 optimal 的），最坏情况是 badly-guided DFS，尤其是当 heuristics function 没选好的时候；

1.4.3 Expanding Strategy: A* Search（A* 搜索）

理解 A star Search 前，先以龟兔赛跑的寓言故事（fable）作比：Uniform Cost Search (uninformed) 就像 tortoise，虽然缓慢，但会搜索到同一权重下的所有状态情况，如果有的话确保一定找到最优解；Greedy Search 就像 hare，非常迅速，但容易走错方向，找不到最优解。

所以 A star search 相当于是坐在乌龟上的兔子，既结合了 Uniform Cost Search 的稳妥，又具有 Greedy Search 部分的借助 heuristic function 迅速搜索的特点。现在看看是如何实现的：

以一个例子来阐释：

对于这个正权有向图而言，Uniform Cost Search 的 expanding strategy 是按照当前步的累计 cost（理解为“深度”）g(n) 来评定的，而 Greedy Search 的 heuristic function 是按照距离 goal 的加权路径距离和 h(n) 来评定的。将 这两个标准相加得到 A* 的评价标准 f(n)，这样既考虑到了下一步的 cost，又考虑到了距离终点的相对位置，达到了一个较好的效果。

因为如果仅仅是 Uniform cost search，则要搜索 6 个结点才能找到 optimal solution；仅用 Greedy Search 只能找到非 optimal 的解；而用 A-star search 只需搜索 4 个结点就找到了 optimal solution.

有同学可能会问，为什么上面图中 e 结点的 h = 1 而不是 2？因为这和 heuristic function 的取法有关系。这里可能不是到达终点的路径长度和，而是直线距离。

思考：为什么只能在结点出队的时候才能检查它是不是 goal 然后再结束？进队的时候不行吗？

答案：不行。进队的时候，没法保证该结点一定比 fringe 内其他所有结点都要优；

• A* 算法不一定是 optimal 的，因为可以举出反例：

  

  上面的反例可以看出，如果 heuristic function 函数没有选好，选的过于 pessimistic，那么很有可能会误导 agent，导致正确的 optimal solution 迟迟无法出队，这就是 A* 不一定 optimal 的原因——heuristic function 选取失误。

• 为了减少以上情况的出现，即优化这个算法，我们引入 Admissibility 来评价一个 heuristic function：

  • 如果 heuristic function 在任意结点的值 $h(n)$ 小于等于实际到 optimal solution 的加权路径长度 $h^(n)$（我们在不知道结果前时无法得知，但它数学上客观存在），那么称为 optimistic heuristic function，这样的 A\ Search 会得到 optimal solution；

    即 optimistic (admissible) heuristic function 的定义为：

    $$\forall\space node\space n,\space 0\le h(n)\le h^*(n)\Longrightarrow h(n)\space is\space admissible$$

  • 如果 heuristic function 在某一结点的值大于实际到 optimal solution 的加权路径长度，则称为 pessimistic heuristic function，这样的 A* Search 很可能无法得到 optimal solution；

  重要的是，虽然我们不知道 $h^*(n)$，但这已经足以我们判断一些情况下使用 A* Search 能否得到 optimal solution了：

  例如在 pac-man game 的例子中，如果取到 goal 的 Manhattan distance 为 heuristic function，那么它一定是 optimistic 的，所以用 A* Search 一定能得到正确的 optimal solution（因为 Manhattan distance 考虑没有墙的情况下的距离，一定是乐观的）；

  再例如在 pancake problem 的例子中，如果取 错位的薄饼的最大编号 为 heuristic function，那么 它也一定是 optimistic 的（因为你至少还要移动编号个数的薄饼次数才能达到 goal）；

  所以到目前为止，选取 heuristic function 的标准一个是举例子看看在某些结点上，$h(n)$ 是否接近 $g(n)$；另一个就是看看能否判断出 optimistic (admissible)，如果能，则能证明 A* Search 算法的 optimality，那么一定比 Uniform Cost Search 要好。

1.4.4 拓展：A* Search 的 optimality 证明

为啥取了 admissible 的 heuristic function，A* Search 就一定是 optimal 的？

定义命题：

$$P:\quad h(n)\space is\space admissible\Longrightarrow A^*\space Search\space is\space optimal$$

下面证明命题 $P$：

1. 假设 A* Search tree 如下图所示，具有一个 optimal solution A 和 suboptimal solution B，由于二者的任意性，所以只要能证明 A 能在 B 之前出队并 expand，则就能证明 $P$；

2. 再假设 B 在 fringe 中的情况（即 B 在搜索队列中），否则 $P$ 直接成立；

3. 再假设 A 或 A 的祖先结点一定在 fringe 中，否则A 及其祖先节点一定都已经 expand 完毕了（因为 A，至少 A 的祖先节点，是 $f(n)$ 值小于 B 的 “候选结点”），这个时候 $P$ 也直接成立；所以记在 fringe 中的 A 或其祖先结点为 n，如下图所示；

4. 则可以证明 $f(n)\le f(A)$：由 $f(n)$ 的定义可知，$f(n)=g(n)+h(n)$，再由 admissibility 的定义可知，

   $$h(n)\space is\space admissible\Longrightarrow h(n)\le h^*(n)\Longrightarrow g(n)+h(n)\le g(n)+h^*(n)$$

   即 $f(n)\le g(A)$；再根据 heuristic function 的定义，$h(A)=0$，所以 $g(A)=f(A)$，进而得出 $f(n)\le f(A)$；

5. 能够证明 $f(A)\lt f(B)$：由 suboptimal solution 的定义，$g(A)\lt g(B)$，由于 $h(A)=h(B)=0$，所以 $f(A)\lt f(B)$；

6. 由第 4 条和第 5 条，能够证明 n 必然在 B 之前 expand，即 $f(n)\lt f(B)$（因为 $f(n)\le f(A)\lt f(B)$）；

7. 由于祖先结点 n 的任意性，所以 A 或 A 的祖先结点一定都在 B 之前 expand，所以 任意的 optimal solution A 一定在 suboptimal solution B 之前 expand，因此 A* Search 的 solution 必然是 optimal solution，$P$ 成立，原命题得证。

Q：为什么第 5 条 $f(A)\lt f(B)$ 不就能说明 A 在 B 前 expand 了吗？

A：其实不然，我们在第 5 条的时候还缺少一个条件——我们当时还不能证明 A 结点一定在 fringe 当中。我们只知道 A 的祖先结点在 fringe 当中。

1.4.5 How to Create Admissible Heuristic Functions ?

• example: 8 puzzle（8 格华容道）

  

  • 取法 1：状态结点 n 中，错位的数字数目定为 heuristic function $h(n)$，此时易得 $h(n)$ 是 admissible 的；
  • 结论 1：将原问题转化为 relaxed-problem heuristic 来讨论，例如在 8-puzzle 里面，如果能够直接把数字拆下来，直接安装到正确位置，那么这个问题就变简单了，action 数目一定变少了，而这个新问题就叫做 relaxed-problem；显然有：新问题的总步数（cost）小于原问题的 optimal solution 的步数（cost）；
  • 取法 2：状态结点 n 中，所有数字距离正确位置的 Manhattan distance 的总和定为 $h(n)$，这个做法就是上述结论的应用。这种取法对应的 relaxed-problem 是 忽略数字方块之间的格挡限制，可以证明这种取法的 $h(n)$ 不仅是 admissible 的，而且比取法 1 更接近真实 optimal solution 的 cost；

• 总而言之，Heuristic function 的选取就在 node expansion 的空间消耗 和 $h(n)$ 计算的时间消耗 之间抉择、权衡。但一般无论哪个方向，都必须要是 admissible 的（因为如果不是的话，就不能保证 A* Search 的 optimality，那还不如用 Greedy search）。

  • 要么 $h(n)$ 选取一些 admissible 且方便计算的函数，但平均需要更多的 node expansion 才能找到 optimal solution；
  • 要么 $h(n)$ 选取一些 admissible 且更接近真实 optimal solution cost 的函数，但一般平均需要花费更长时间才能计算出 $h(n)$ 在某一结点的值；

• 结论 2：两个 admissible heuristic function 的最大值函数一定是更接近于真实 optimal solution cost 的 admissible heuristic function；如下图：

  

  注：如果 $\forall n,\space h(n)=0$，则 A* search 退化为 Uniform Cost Search（相当于提供 goal 的信息被 “磨平了”，各结点处都一样了）

1.4.6 From Tree Search to Graph Search

前面说的算法，从 uninformed search (DFS、BFS、Uniform Cost Search) 到 informed search (Greedy Search、A* Search)，都借助了 Tree Search 的思想，没有标注 visited 结点，导致大量重复冗余的 node expansion（同一状态结点入队多次）。

我们借鉴图算法的思想，只需要在前面 Tree Search 算法中 expansion strategy 前 加入 visited 判断，即可变成 Graph Search。具体实现方法可以借助 closed set（闭集，就是集合结构的数学名称）（别用列表，因为线性表查找元素是否存在的时间复杂度远大于集合结构）

易得，Tree Search 算法和同等的 Graph Search 算法的 complete 性质相同。因为它们理论上都能遍历完有限结点。

但！转换为 Graph Search 后，却不一定有同等的 optimality。因为在某些情况下，如果某些 admissible heuristic function 选的不好，很有可能导致 visited 会放弃掉 optimal solution，例如下面这种情况：

这是因为 heuristic function 选取的不一致性（inconsistency）导致的，通常是因为两个结点之间的 $h(n)$ 值之差大于它们间的 cost，导致其中一个结点需要第二次进队才有可能找到 optimal solution。这里结点 A 和 C 之间就存在这个问题，$h(A)-h(C)=3\gt cost(A,C)=1$，所以当 C 结点在 A* Tree Search 第二次进队时，才算 optimal solution。如果贸然转换为 Graph Search，就会丢失这个 optimal solution。

所以，考虑对于一个 admissible heuristic function，如果每两个结点之间的 $h(n)$ 值之差必然小于等于它们之间的 cost，所以称这个 admissible heuristic 为 consistent 的。

只有 heuristic function 是 consistent 的，越靠 fringe 后面弹出的 node，其 $f(n)$ 越大，越不可能是 optimal solution，否则不能满足这个特性。

• 性质 1： Consistency 蕴含（implies）Admissibility（一个 consistent heuristic function 一定是 admissible heuristic function）；
• 性质 2：只有选取了 Consistent heuristic function，A* Graph Search 才能保证 optimality，但 A* Tree Search 只需要 Admissible heuristic function 就能保证 optimality；

因此，如果选取的 heuristic 具备 consistency，那么将之前的所有 Tree Search 算法加上 visited 判断变成 Graph Search 算法，均不改变其 completion 和 optimality，并且可以减少 node expansion 的数目，实现算法的优化。

值得庆幸的是，大部分自然得到的 admissible heuristic functions 都是 consistent 的，尤其是由 relaxed problems 取得的。所以大可以认为，用 relaxed problems 方法取得的 heuristic functions 都具有 consistency，而无需证明。

上面的 “一致性” 比较抽象，有位知乎网友 @Hepta 解释的好，截下来给大家参考：

这可以认为，这个 heuristic function 取得确实是 admissible（每个结点的 $h(n)$ 总趋势都是越接近 goal 就越接近0，并且是乐观估计的），但是每个路线上的 “乐观估计程度不相同”，如果存在一种情况：一个实际更长（cost 更大）的路径比一个实际更短（cost 更小）路径的 $h(n)$ 更乐观——即虽然它们各自都正确反映了 goal 远近的性质（admissible），但相对远近反映不一致（inconsistent），这就是 heuristic function 的不一致性。

这种不一致就会影响搜索，导致suboptimal solution 的路径比 optimal solution 的路径更快到达 solution 附近停下来（但总体受到 admissible 的限制，suboptimal solution 不会先进队的），所以这个时候如果附近的结点又恰好唯一，并且还有 visited 不允许重复进队，那么 optimal solution 的路径就会被 suboptimal solution 的路径截断，造成错误地丢失正确最优解。

所以上面说 “relaxed problems 得到的 admissible heuristic function 都有 consistency” 是符合一般规律的，故意设计的 heuristic function 可能不满足 consistency、满足 admissible，但它一般不能从 relaxed problems 得出。

1.4.7 补充：Dijkstra Algorithm & A* Algorithm

其实细心的同学已经发现，Dijkstra 算法不就是 A* 算法的特殊情况嘛！当我们仅仅以当前步累计的 cost（去掉距离 goal 的 cost）作为 heuristic function 时，A* 算法就退化为了 Dijkstra 算法。

它们都只能解决非负边权值图的最短路径问题。

1.5 Summary

本章讲述了 搜索问题 的基本定义和算法。我们可以总结出：

• 搜索问题的使用场景：用于一类很特定的问题，它们满足搜索问题的模板。例如地图导航的最短路搜索、没有敌人并且是去往特定位置的 pac-man 游戏；

• 搜索问题中 Agent 的性质：Planning Agent，即先根据算法计算，得出一系列动作序列之后再行动，更关注 master-mind，即固定的动作序列解法来得到最优解；

• 搜索问题的前提假设：单个 Agent（没有其他 agent 做出不确定 (uncertain) 或者对抗性 (adversarial) 的 actions 对当前 agent 造成影响）、可决定的 Actions、完全可观测的 States、离散的 State space；

• 搜索问题的目标

  • 获取路径：此时 Agent 的性质是 Planning Agent，即先根据算法计算，得出一系列动作序列之后再行动，更关注 master-mind，即固定的动作序列解法（即路径）来得到最优解；

    本章讲述的几乎所有内容都是关于这个方面的；

  • 获得结果：此时动作序列并不重要，只关心这个动作序列能否达到 goal；通常这种目标下不会考虑 costs；

所以搜索问题的假设很多，在这个问题基础上，我们添加了一些信息，例如路径是否等权？权重大小多少？是否可以用 goal 信息来 inform 搜索的方法？

对应的算法常见的有：Tree Search 的 DFS、BFS、UCS（都是 uninformed）和 Greedy Search、A Star Search；进一步进行改进还有对应的 Graph Search。

以后几章，我们将一点点解除这些前提假设的限制，让问题发生变化，并探讨新问题的算法。

Chapter 2. Constraint Satisfaction Problems (CSPs)

2.1 The Introduction to CSP

正如上一章总结所说，CSP 只是一种特殊的 “获取结果” 的 Search Problem，它对问题作了如下假设：

• 状态空间是个黑盒，可以是任何数据结构，无法直接访问状态空间的信息；
• 目标测试也可以是任何形式的函数，也是黑盒，只能调用（即从结果上看是否达到目标）；
• 后继函数仍然是黑盒，你只能通过调用来取得可能的后继状态；

因此我们可以问题抽象为新的数学表示：

• CSP 就是 Search Problem 的一个特殊子集，目标本质是找到 goal；
• 所有的状态可以被定义为一组变量：$X_i$，其值在定义域 $D$ 中变化（有的时候 $D$ 取决于 $i$）；
• 后继函数的运作方法类似为这些状态变量赋值；
• 目标测试就是一组限制条件（Constraints），指明了最终的 goal，即可接受的状态序列（由可接受的一组 $X_i$ 的值组成），这也是为什么这个问题被称为 “Constraint Satisfaction Problems”；

它的应用相当广泛，生活中几乎都能见到。

2.1.1 Example 1: 地图上色

举一个例子，计算机证明 四色定理 时需要正确地为地图分配颜色。现在我们想要为地图上一片有划分的区域填色，要求相邻区域颜色不得相同。具体做法如下：

1. 首先把问题抽象为 CSP。很显然，问题的状态可以由一组区域变量表示，其定义域为各自不同颜色组成的集合，这里假设有 6 个区域，在 $x_1\sim x_6$；
2. 这里可以把颜色定义域设置为 3 种颜色：D = { red, green, blue }；
3. 目标测试（限制条件）
   • Implicit（隐含）：adjacent regions must have different colors（体现在代码中就是每两个相邻区域变量不相等）；
   • Explicit（明确）： $(x_i,x_j)\in\{(red,green),(red,blue),\cdots\}$；
4. 解决方案（solution）：就是一组或多组符合限制条件的 $x_i$ 的赋值（assignments），CSP 问题的解只需要找到一个解即可；

---

除了使用变量 + 限制条件的方法，还有一种方法可以描述 CSP 问题：Constraint Graphs：

• 每个变量由图中的一个结点代替；

• 如果限制条件是 二元 的（是/否、有/无、等于/不等于，等等），那么可以用结点之间是否连接边来表示；

  注意：限制图的边只是表示哪里有限制，没有说明限制是什么，所以应该是二元的限制条件；

这种最多每两个变量之间具有二元限制条件的 CSP 问题被称为 Binary CSP，对应的限制图被称为 Binary Constraint Graph；

相对应的还有一元限制条件（Unary Constraint），即指定变量必须为某特定值；后面会具体说。

2.1.2 Example 2: N-Queens 问题

我们听过 “八皇后问题”，那么对于 N-皇后问题，除了使用递归+回溯的经典解法，还可以将其转化为 CSP 求解：

• 表示方法 1：逐格表示

  • 状态：就是 N × N 的数组，用于保存其上是否存在 “皇后” 棋，定义域为 {0, 1}；

  • 目标测试（限制条件）：

    1. $\forall i,j,k\space(X_{ij},X_{ik})\in\{(0,0),(0,1),(1,0)\}$（不能在同一行）
    2. $\forall i,j,k\space(X_{ij},X_{kj})\in\{(0,0),(0,1),(1,0)\}$（不能在同一列）
    3. $\forall i,j,k\space(X_{ij},X_{i+k,\space j+k})\in\{(0,0),(0,1),(1,0)\}$（不能在对角线下半部分）
    4. $\forall i,j,k\space(X_{ij},X_{i+k,\space j-k})\in\{(0,0),(0,1),(1,0)\}$（不能在对角线上半部分）
    5. $\sum_{i,j}X_{ij}=N$；

• 表示方法 2：列表示

  • 状态：第 $k$ 行的 queen 位于的列数 $Q_k$，定义域为 {1, 2, ..., N}；
  • 限制条件：$(Q_1,Q_2)\in\{(1,3),\space(1,4),\cdots\}$ ……;

2.1.3 Example 3: Cryptarithmetic 加密运算

例如对加法式：

    T W O
  + T W O
-----------
  F O U R

解出每个字母所代表的数字（0 ~ 9）；可以抽象出如下 CSP 问题：

• 变量 F、T、U、W、R、O、C1（第一位进位）、C2、C3；定义域 {0,1,...,9}；
• 限制条件
  • alldiff(F, T, U, W, R, O)，字母各不相同；
  • O + O = R + 10 * C1, ……;

2.1.4 Example 4: Sudoku

对于数独而言，转化为 CSP 可以是：

• 变量即每一个没有填数的方块，定义域 0 ~ 9 的整数；
• 限制条件
  • 每一行所有元素不得相同；
  • 每一列所有元素不得相同；
  • 每一小正方形区域所有元素不得相同；
  • 本身填有数的方块为 Unary Constraint，要求必须为某个数字；

2.1.5 Example 5: The Waltz Algorithm (Deprecated)

早期计算机视觉使用这个算法来识别 3D 图形的顶点是向外凸，还是向内凹。基本原理是：将立体中的所有顶点作为一个变量，限制条件就是相邻两个点不能一个是凸顶点，一个是凹顶点；

2.2 Varieties of CSPs

2.2.1 Varieties of Variables

研究 CSPs 算法前，先弄清楚 CSPs 的详细信息。首先 CSP 总的来说有两种变量类型：

• 离散型变量（Discrete Variables）
  • 有穷定义域（$card(D)=d$）：存在 $O(d^n)$ 种完全指配；例如 二元 CSP，有些是 NP-完全 问题；
  • 无穷定义域（整型、字符串等）：更加困难，例如工作安排问题（某些问题必须在另一些问题之前完成）；仅线性约束可解。
• 连续型变量（Continuous Variables）
  • 例如与时间变化有关的问题，线性约束可解，并且是多项式时间内可以利用 LP 方法完成；

2.2.2 Varieties of Constraints

• Unary Constraint：与单个变量有关，等价于减小定义域，例如：$x=1$、$y\ne2$；

• Binary Constraint：仅与一对变量有关，例如：$x=y$、$a\ne b$；

• Higher-order Constraint: involve 3 or more variables，例如 2.1.3 加密计算；

• Soft Constraint: Preferences（非强制的倾向），实现方法是加权，并且转化为限制优化问题；

  本章会忽略这种情况，到 贝叶斯网络 再讨论这个问题。

2.3 The formulations for Binary CSPs

本节仅讨论 Constraint 至多与 2 个变量有关的问题。

2.3.1 Standard Search Formulation

一种常用解决 CSP 问题的方法被称为 Standard Search Formulation，方法将 CSP 问题看作一种特殊的搜索问题，定义如下：

• 状态：defined by the values assigned so far；
• 初始状态：空指派；
• 后继函数：为一个没有指派的变量从定义域种指派一个值；
• 目标测试：当前指配是否为完全指派，并且满足所有约束条件；

现在讨论这种思路下的算法，从最原始的方法开始来一步步优化。

现在以上面任一个 Example 为例。

BFS 遍历

我们考虑最原始的 BFS 遍历，发现这是最差的算法，没有之一。因为这个问题中，所有的解法都在搜索树的最底层。意味着 BFS 需要遍历几乎所有状态才能找到至少一个解。我们大可以直接放弃这个方法。

DFS 遍历

在这个问题中，DFS 方法要比 BFS 好一些，所以这一节中接下来的优化算法都基于此。这和上一章解决普通 Search Problem 的思路不一样，那个时候的算法几乎都从 BFS 的思路出发（UCS / A Star）。

实现思路是先一步步沿搜索树向下指派变量，全部指派结束后，再检查目标测试，不满足则从栈中弹出最上面的赋值（最后一个赋值），换一个值，如此递归进行。

实现思路简单，但是非常繁琐，接下来进行优化。

Backtracking Search

是一种解决 CSP 的 basic uninformed algorithm，思路如下：

• 一次仅对一个变量进行操作

  • 变量指派是可交换顺序的，所以首先定下顺序（例如先赋值 $x=1$，再赋值 $y=2$ 和 先赋值 $y=2$，再赋值 $x=1$ 是等价的），只要将定义域排序，并且按序指派就能实现；
  • 每一步只需要考虑一个单独变量的指派；

• 每一步都检查限制条件：一旦违反条件，立即更换当前最近一次的指派。

  这主要因为 CSP 问题在前一步违反条件后，后面指派就没有机会弥补，或者说使状态重新符合条件。类似一种剪枝。

使用以上两个思路优化的 DFS 被称为 Backtracking Search（回溯搜索）；

这种算法在解决 Example 2 的 N-queens 时，能够解出在 N ≤ 25 范围的问题。

现在考虑 backtracking 能否继续优化？从以下方面考虑：

• 指派定义域排序：下一个先指派定义域中的谁？按什么顺序？
• 中途过滤：能否在违反限制之前就检测到可能的风险，并且尽早规避？（使得递归深度减小）
• 数据结构：能否进一步改进问题的数据结构，使其更高效？

先从方便下手的部分开始：中途过滤。

优化方案 1: Forward Checking

思路之一是 Forward Checking，在为一个变量指派时，同时根据限制缩小其他变量（必须仅仅是有限制联系的，no further）的定义域（排除不符合限制的取值）。一旦发现有变量的定义域为空，则提前检测到了违反限制的情况，所以提前排除这种指派，重新为当前变量指派。

In general, forward checking is going to propagate information from assigned values to unassigned values, but doesn’t provide early detection for all failures (looming conflicts between unassigned and other unassigned variables).

优化方案 2: Rich Filtering Algorithm - Graph Arc Consistency Checking

这种方法还可以继续向前预测，因为在地图上色例子中，当地图两个相邻区域定义域只有相同颜色时，也希望被提前检测到。这就需要 reason from constraint to constraint（从一个限制条件推广传递至另一个），用到的技术是 arc consistency（限制图有向边一致性，arc 和 edge 都可以指图的边）。

在 Forward Checking 中，我们让每一步都按照给定的限制条件检查并更新定义域，但是某些限制条件之间可以推出另外的限制条件，让违反限制的情况更早地被检查到。我们可以通过 arc consistency 来检查。

首先给出 arc consistency 的定义：在限制图中，对于一个 constraint 对应的有向边，如果对起始结点（tail）当前定义域中任意指派，终止结点（head）当前定义域中都存在一个指派，使得二者不违反 constraint，则称这条边是一致的。

因此，我们可以发现，前面的 forward checking 只是保证了指向 new assignment（head）的任意有 constraint 结点（tail）的边具有 consistency，没有检查 “unassigned 结点之间边的 consistency”。

所以，新方法应该一开始把所有的边放在一个集合中等待遍历。每一轮检查限制条件、更新定义域时，同时对其他所有有 constraint 相连的结点也进行检查（对于 unassigned 结点，一般是双向的），如果不满足，那么从起始结点的定义域中移除违反限制的取值（正是因为从起始结点移除，所以 arc consistency 的定义是 ”起始结点任意指派 -> 终止 结点存在指派“）。非常难过的一点是，如果我们正在遍历 arc 检查 consistency 时，对某个结点（tail）移除了一个 value，那么之前所有指向这个结点（这时作为 head）所建立的 consistency 都不一定成立了，需要重新检查所有指向这个结点的边的 consistency。

这个优化算法的名称叫做 Forward Checking + AC3，可以保证每次指派后，限制图都有 graph arc consistency。

这个时候，我们发现每指派一步所进行的 checking 步骤（即 Graph Arc Consistency Checking）过于复杂，以至于我们应该把这个步骤单独提出为一个函数，如下：

每次我们递归地指派一个结点的值，我们在检查是否违反 constraint 的时候，都要调用一次 AC3 函数，进行如下检查：

1. 获取当前所有结点变量及其定义域，并将限制图中每条有向边（如果限制条件是无向的，就等价于放双向边）都放入一个队列中；
2. 当队列非空时，从队列取出一条有向边（限制条件），检查边的一致性（使用定义），如果违反，那么删去起始结点定义域中导致冲突的值，并且将当前边的起始结点作为终止结点时的所有边放入队列，等待重新检查一致性（代码就是 REMOVE-INCONSISTENT-VALUES）；
3. 重复第 2 步直至队列中没有边（所有边都通过了一致性检查，又或者至少有一条边的定义域为空，即当前指派无解）；

这里大家会发现，虽然这个算法确实提前避免违反限制的情况，但是时间复杂度是肉眼可见的大（时间复杂度 $O(n^2d^3)$，通过数据结构优化可以达到 $O(n^2d^2)$，n 为结点数量级，d 为 每个结点变量的定义域大小数量级）。所以这里就需要在 详细的检查以在浅处避免违反限制 和 简单的检查但平均递归深度较大时才能发现违反限制并放弃 这两种情况抉择。

如果数据结点相当多，不希望递归深度很大，那么 AC3 算法为优；如果限制条件相当多，结点数又相对较少，不希望在检查上浪费太多时间，那么 forward checking 算法为优。