0x27 A*

在探讨A*算法之前，我们先来回顾一下优先队列BFS算法。该算法维护了一个优先队列（二叉堆），不断从堆中取出“当前代价最小”的状态（堆顶）进行扩展。每个状态第一次从堆中被取出时，就得到了从初态到该状态的最小代价。

如果给定一个“目标状态”，需要求出从初态到目标状态的最小代价，那么优先队列BFS的这个“优先策略”显然是不完善的。一个状态的当前代价最小，只能说明从起始状态到该状态的代价很小，而在未来的搜索中，从该状态到目标状态可能会花费很大的代价；另外一些状态虽然当前代价略大，但是未来到目标状态的代价可能会很小，于是从起始状态到目标状态的总代价反而更优。优先队列BFS会优先选择前者的分支，导致求出最优解的搜索量增大。比如在上一节（115页）优先队列BFS的示意图中，产生最优解的搜索路径 $(5 + 2 + 1)$ 的后半部分就很晚才得以扩展。

为了提高搜索效率，我们很自然地想到，可以对未来可能产生的代价进行预估。详细地讲，我们设计一个“估价函数”，以任意“状态”为输入，计算出从该状态到目标状态所需代价的估计值。在搜索中，我们仍然维护一个堆，不断从堆中取出“当前代价 $+$ 未来估价”最小的状态进行扩展。

为了保证第一次从堆中取出目标状态时得到的就是最优解，我们设计的估价函数需要满足一个基本准则：

设当前状态 state 到目标状态所需代价的估计值为 $f(state)$ 。

设在未来的搜索中，实际求出的从当前状态 state 到目标状态的最小代价为 g(state)。

对于任意的 state，应该有 $f(state) \leq g(state)$ 。

也就是说，估价函数的估值不能大于未来实际代价，估价比实际代价更优。

为什么要遵守这个准则呢？我们不妨看看，如果某些估值大于未来实际代价，那么将发生什么情况。

假设我们的估价函数 $f$ 在每个状态上的值如下图所示：

根据“每次取出当前代价+未来估价最小的状态”的策略，会得到如下过程：

队列： $3 + 7,4 + 6,5 + 10$

取出： $3 + 7$

插入： $12 + 0$

队列： $4 + 6,12 + 0,5 + 10$

取出： $4 + 6$

插入：12+0

队列： $12 + 0,12 + 0,5 + 10$

取出： $12 + 0$

得到错误答案12

我们可以看到，本来在最优解搜索路径上的状态被错误地估计了较大的代价，被压在堆中无法取出，从而导致非最优解搜索路径上的状态不断扩展，直至在目标状态上产生错误的答案。

如果我们设计估价函数时遵守上述准则，保证估值不大于未来实际代价，那么即使估价不太准确，导致非最优解搜索路径上的状态 $s$ 先被扩展，但是随着“当前代价”的不断累加，在目标状态被取出之前的某个时刻：

1. 根据 $s$ 并非最优， $s$ 的“当前代价”就会大于从起始状态到目标状态的最小代价。

2. 对于最优解搜索路径上的状态 $t$ ，根据 $f(t) \leq g(t)$ ， $t$ 的“当前代价”加上 $f(t)$ 必定小于等于 $t$ 的“当前代价”加上 $g(t)$ ，而后者的含义就是从起始状态到目标状态的最小代价。

结合以上两点， $t$ 的当前代价加上 $\mathbf{f}(t)$ 小于 $s$ 的当前代价。因此， $t$ 就会被从堆中取出进行扩展，最终更新到目标状态上，产生最优解。

这种带有估价函数的优先队列BFS就称为A算法。只要保证对于任意状态state，都有f(state)≤g(state)，A算法就一定能在目标状态第一次从堆中被取出时得到最优解，并且在搜索过程中每个状态只需要被扩展一次（之后再被取出就可以直接忽略）。估价f(state)越准确、越接近g(state)，A*算法的效率就越高。如果估价始终为0，就等价于普通的优先队列BFS。

A算法提高搜索效率的关键，就在于能否设计出一个优秀的估价函数。估价函数在满足上述设计准则的前提下，还应该尽可能反映未来实际代价的变化趋势和相对大小关系，这样搜索才会较快地逼近最优解。接下来我们通过两道例题来具体地感受一下A算法。

【例题】第K短路Remmarguts'Date POJ2449

给定一张 $N$ 个点， $M$ 条边的有向图，求从起点 $S$ 到终点 $T$ 的第 $K$ 短路的长度，路径允许重复经过点或边。其中 $1 \leq S, T \leq N \leq 1000, 0 \leq M \leq 10^5, 1 \leq K \leq 1000$ 。

注：不熟悉最短路的读者可以简单浏览0x61节，或者假设我们能够在一张图上求出单源最短路（从一个点出发到其他所有点的最短路径长度），然后在此基础上考虑本题。

一个比较直接的想法是使用优先队列 BFS 进行求解。优先队列（堆）中保存一些二元组 $(x, dist)$ ，其中 $x$ 为节点编号，dist 表示从 $S$ 沿着某条路径到 $x$ 的距离。

起初，堆中只有 $(S,0)$ 。我们不断从堆中取出dist值最小的二元组 $(x, dist)$ ，然后沿着从 $x$ 出发的每条边 $(x,y)$ 进行扩展，把新的二元组 $\left(y, dist + \text{length}(x,y)\right)$ 插入到堆中（无论堆中是否已经存在一个节点编号为 $y$ 的二元组）。

上一节我们已经讲到，在优先队列BFS中，某个状态第一次从堆中被取出时，就得到了从初态到它的最小代价。读者用数学归纳法很容易得到一个推论：对于任意正整数 $i$ 和任意节点 $x$ ，当第 $i$ 次从堆中取出包含节点 $x$ 的二元组时，对应的dist值就是从 $S$ 到 $x$ 的第 $i$ 短路。所以，当扩展到的节点 $y$ 已经被取出 $K$ 次时，就没有必要再插入堆中了。最后当节点 $T$ 第 $K$ 次被取出时，就得到了 $S$ 到 $T$ 的第 $K$ 短路。

使用优先队列 BFS 在最坏情况下的复杂度为 $O(K * (N + M) * \log (N + M))$ 。这道题目给定了起点和终点，求长度最短（代价最小）的路径，可以考虑使用 A* 算法提高搜索效率。

根据估价函数的设计准则，在第 $K$ 短路中从 $\mathcal{X}$ 到 $T$ 的估计距离 $\mathrm{f}(x)$ 应该不大于第 $K$ 短路中从 $\mathcal{X}$ 到 $T$ 的实际距离 $\mathrm{g}(x)$ 。于是，我们可以把估价函数 $\operatorname {f}(x)$ 定为从 $\mathcal{X}$ 到T的最短路长度，这样不但能保证 $\mathrm{f}(x)\leq \mathrm{g}(x)$ ，还能顺应 $\mathrm{g}(x)$ 的实际变化趋势。最终我们得到了以下A*算法：

1. 预处理出各个节点 $x$ 到终点 $T$ 的最短路长度 $f(x)$ ——这等价于在反向图上以 $T$ 为起点求解单源最短路径问题，可以在 $O\big((N + M)\log (N + M)\big)$ 的时间内完成。

2. 建立一个二叉堆，存储一些二元组 $(x, dist + f(x))$ ，其中 $x$ 为节点编号，dist 表示从 $S$ 到 $x$ 当前走过的距离。起初堆中只有 $(S, 0 + f(0))$ 。

3. 从二叉堆中取出 $dist + f(x)$ 值最小的二元组 $(x, dist + f(x))$ ，然后沿着从 $x$ 出发的每条边 $(x, y)$ 进行扩展。如果节点 $y$ 被取出的次数尚未达到 $K$ ，就把新的二元组 $(y, dist + length(x, y) + f(y))$ 插入堆中。

4. 重复第 $2 \sim 3$ 步，直至第 $K$ 次取出包含终点 $T$ 的二元组，此时二元组中的dist值就是从 $S$ 到 $T$ 的第 $K$ 短路。

A* 算法的复杂度上界与优先队列 BFS 相同。不过，因为估价函数的作用，图中很

多节点访问次数都远小于 $K$ ，上述 $\mathbf{A}^*$ 算法已经能够比较快速地求出结果。

【例题】八数码Eight FOJ1077

在0x05节的“奇数码问题”中，我们已经描述了八数码的规则。在本题中，你需要求出八数码的最少移动步数，并给出一种方案。

先进行可解性判定。我们在0x05节中已经提到过，把除空格之外的所有数字排成一个序列，求出该序列的逆序对数。如果初态和终态的逆序对数奇偶性相同，那么这两个状态互相可达，否则一定不可达。

若问题有解，我们就采用 $A^*$ 算法搜索一种移动步数最少的方案。经过观察可以发现，每次移动只能把一个数字与空格交换位置，这样至多把一个数字向它在目标状态中的位置移近1步。即使每一步移动都是有意义的，从任何一个状态到目标状态的移动步数也不可能小于所有数字当前位置与目标位置的曼哈顿距离之和。

于是，对于任意状态 state，我们可以把估价函数设计为所有数字在 state 中的位置与目标状态 end 中的位置的曼哈顿距离之和，即：

其中 $state\_x_{num}$ 表示在状态 state 下数字 num 的行号， $state\_y_{num}$ 为列号。我们不断从堆中取出“从初态到当前状态 state 已经移动的步数 $+f(state)$ ”最小的状态进行扩展，当终态第一次被从堆中取出时，就得到了答案。

在 $\mathbf{A}^*$ 算法中，为了保证效率，每个状态只需要在第一次被取出时扩展一次。本题中的状态是一个八数码，并非一个简单的节点编号，所以需要使用Hash来记录每个八数码是否已经被取出并扩展过一次。我们可以选择取模配合开散列处理冲突，或STLmap等Hash方法。另外，有一种名为“康托展开”的Hash方法，可以对全排列进行编码和解码，把 $1\sim N$ 排成的序列与 $1\sim N!$ 之间的整数建立一一映射关系，非常适合八数码的Hash，感兴趣的读者可以自行查阅相关资料。

本书所附光盘中的参考程序实现了一个最基本的 A* 算法。虽然它没有用“逆序对”的结论判断是否有解，也没有用高效的线性 Hash 方法（直接采用了 STLmap，参见第 0x71 节），但足以在规定的时限内完成求解。读者可以进一步优化，提高程序的效率。