摘要

这篇文章讨论 A* 算法。与 Dijkstra 算法类似，A* 算法是一种寻找最优路径的算法，实际上两者存在相当多的联系。文章的第一部分讨论 A* 算法的基本概念，包括 A* 算法与 Dijkstra 算法和最优优先算法（Best First Search）之间的联系，A* 算法的一些特点及应用；在第二部分讨论 A* 算法的一些优良性质，包括可采纳性与一致性，并对这些性质给出证明，在此之前会首先给出 A* 算法的算法描述。

A* 算法概念

A* 算法是一种寻找最优路径的算法，实际上，A* 算法常常在游戏中使用，为玩家找到一条从起点到终点的最短路径，此时对象是在网格上进行移动。考虑解决这样一个寻找最优路径的算法，我们直接使用 Dijkstra 算法，后者实际上是一种动态规划的策略，每一步分别找出当前距离起点最近的网格，当终点也被找出时，算法结束。Dijkstra 算法的运行过程如下图示意：

容易看出，在图中这种情况下，Dijkstra 算法会优先访问很多明显与目标背道而驰的网格，例如左边和右边的网格，仅仅是因为这些网格距离起点有更近的距离。尽管 Dijkstra 算法一定可以找到最优的路径，但是其运行效率也较为低下。

另一种想法是利用最优优先算法（Best First Search），后者会利用到目标距离的估计函数 h(n)，在每一次迭代中总是选择 h(n) 最小的那一个网格，当终点被选择时，算法结束。最优优先算法的运行过程如下图示意：

可以看到，由于使用了启发信息 h(n)，最优优先算法并不会去访问那些明显偏离目标的网格，这使得该算法的运行速度显著高于 Dijkstra 算法。但是它的缺点也非常明显，即最优优先算法未必可以找到最优路径，它找到的只是一条可用的路径。

A* 算法的思路就是，是否可以将以上两个算法综合起来，取其精华去其糟粕，构造一种又可以找到最优路径，同时利用一定的启发信息，减少搜索的范围，从而提高搜索效率的算法。在 Dijkstra 算法中，是使用每个节点相对起点的距离作为衡量指标，记为 g(n)，每次迭代是选择 g(n) 最小的节点，直到终点被找出；而在最优优先算法中，是使用每个节点相对目标距离的估计值作为衡量指标，即 h(n)。为了将两者结合起来，A* 算法使用了 f(n) = g(n) + h(n) 作为衡量指标，同时考虑了两者。在上面的例子中，A* 算法的运行过程如下图示意：

可以通过控制 h(n) 使得 A* 算法具有不同的表现。作为两个极端，

• 当 h(n) = 0 时，A* 算法就退化成为 Dijkstra 算法，此时一定可以找到最优路径，但运行效率较低；
• 当 h(n) >> g(n) 时，此时 g(n) 的作用可以忽略不计，A* 算法退化为最优优先算法，算法的运行更快，但未必可以找到最优路径。

实际上，当 h(n) 总是不大于 n 到目标的实际最短距离时，后者记为 h*(n)，即 h(n) <= h*(n) 时，A* 算法一定可以找到一条最优路径，这个结论将在第二部分中证明。此外，如果 h(n) 总是等于 h*(n)，这意味着到目标距离的估计值总是准确的，此时 A* 算法只会沿着最优路径进行，而不会访问任何其他节点——这个条件固然是难得的，但是有必要知道当 A* 算法拥有足够信息时，A* 算法可以完美地表现。最后 h(n) 的值越大，A* 算法运行地越快，在实际应用中，有时我们未必想要最优的路径，而只是想找到一条可行的路径，此时就可以设置较大的 h(n) 来加快算法运行速度。

A* 算法的优良性质

A* 算法具有两个优良性质：

• 可采纳性定理。当 h(n) <= h*(n) 对于任意节点都成立时，A* 算法一定可以找到最优路径。
• 一致性定理。对于互为父子的两个节点i, j，不妨设 i 是 j 的父亲，满足 h(i) <= h(j） + C(i, j)，其中 C(i, j) 表示从 i 到 j 的路径长度。此时任一节点不会被重复扩展。需要说明的是，这里父子节点的概念，是相对于搜索过程形成的树形结构而言的，而非一开始的图结构。

在说明这两个性质之前，首先给出 A* 算法的算法描述：

OPEN   = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
    current = remove lowest rank item from OPEN
    add current to CLOSED
    for neighbors of current:
        cost = g(current) + movementcost(current, neighbor)
        if neighbor in OPEN and cost less than g(neighbor):
            remove neighbor from OPEN, because new path is better
        if neighbor in CLOSED and cost less than g(neighbor): 
            remove neighbor from CLOSED
        if neighbor not in OPEN and neighbor not in CLOSED:
            set g(neighbor) to cost
            add neighbor to OPEN
            set priority queue rank to g(neighbor) + h(neighbor)
            set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

其中主要是利用了 OPEN 和 CLOSE 这两个数据结构，前者存储的是已经被探测到，但还未访问过的节点；后者存储的是访问完的节点。算法的主循环无非取出 OPEN 中 f(n) 最小的节点，对其进行访问，同时利用该节点来更新其邻居节点的 f(n) 信息，直到目标节点被访问到。容易看出这个过程和 Dijkstra 算法是非常类似的，除了一点——当邻居节点已经存在于 CLOSE 表且获得了更小的 f(n) 时，需要将该节点重新加入 OPEN 表当中。

可采纳性定理

容易看出，在 A* 算法当中，被访问到的节点无非满足 f(n) <= f(t) = g(t)，其中 t 表示目标节点，显然目标节点的预测值 h(t) = 0。以下我们来证明可采纳性定理，采用反证法：

• 假设当 A* 算法找到目标节点 t 时，此时到 t 的路径并非最优路径；
• 则至少存在一个节点 t’，使得通过 t’ 到 t 存在一条更优的路径；
• 由于该路径未被发现，显然 t’ 尚未被访问，因此满足 f(t') >= g(t)；
• 由于对于任何节点都有 h(n) <= h*(n)，因此从原点经过 t’ 到 t 的实际路径长度 g(t') + h*(t') >= f(t') >= g(t)，可见这并不是一条相对于此时的 g(t) 更优的路径，与假设矛盾。

证毕。

可采纳性定理还具有一个推论——对于同一个问题的两个A* 算法，分别记为 A_1 和 A_2，其中 A_2 相对于 A_1 有更多的启发信息，即对于任一个非目标节点，都有 h_1(n) < h_2(n)，则 A_2 扩展的每一个节点必会被 A_1 扩展，反之则未必。为了理解这个推论，只需记住 A* 算法只扩展满足 f(n) <= g(t) 的节点就可以了。

一致性定理

一致性定理的条件是很有道理的，对于互为父子的两个节点 i, j，不妨设 i 是 j 的父亲。处于 i 的位置时对目标的估计显然是不如在 j 准确的，因为在位置 j 获得了更多的信息。这个条件可以表述为 h(i) <= h(j） + C(i, j)，其中 C(i, j) 表示从 i 到 j 的实际距离，即在拥有更少信息时，对目标的估计会更加乐观。

可以证明，当满足一致性定理时，是一定满足可采纳性定理的，以下归纳地证明该结论：

• 对于目标节点 t，显然满足 h(t) <= h*(t)；
• 假设对于任一节点 i，它的所有直接孩子节点都满足可采纳性定理，不妨设节点 i 通过孩子节点 j 取得最优路径；
• 根据一致性定理有，h(i) <= h(j) + C(i, j)，由于 h(j) <= h*(j)，可以得到 h(i) <= h*(j) + C(i, j) = h*(i)，因此 i 也满足可采纳性定理。

证毕。

此外，满足一致性定理时，A* 算法不再会出现回溯的情况。也就是说，处于 CLOSE 表中的节点不可能被再次扩展，它们第一次被扩展时就已经找到了一条到这些节点的最短路径。此时 A* 算法和 Dijkstra 算法就更加类似了。以下我们来证明这个结论，考虑反证法：

• 设有已经处于 CLOSE 表中的节点 a，此时到 a 的路径并非最优路径；
• 则至少存在另一个节点 b，它是 a 的直接父亲，使得通过 b 到 a 有一条更优的路径；
• 由于该路径未被发现，显然 b 尚未被访问，因此满足 f(b) >= f(a)；
• 由于对于父子节点 b 和 a 有 h(b) <= h(a） + C(a, b)，等式两边同时加上 g(b) 可得 f(b) <= (C(a, b) + g(b)) + h(a) = g'(a) + h(a)，这里用 g'(a) 表示通过从起点经过 b 到 a 的路径长度。
• 结合以上的分析可得 f(a) <= f(b) <= g'(a) + h(a)，因此 g(a) <= g'(a)，可见经过 b 到 a 并不能得到一条到 a 的更优路径，与假设矛盾。

证毕。

可以看到，当 A* 算法满足一致性条件时，每一次扩展的节点一定是到该节点的最优路径，这和 Dijkstra 算法是一致的。但是两者不同的地方在于，Dijkstra 算法在扩展该节点之前要首先扩展所有距离起点更近的点，而 A* 算法则只用扩展 f(n) 更小的点，启发信息的引入使得 A* 算法可以过滤掉很多可能性。

参考资料

[1]. http://theory.stanford.edu/~amitp/GameProgramming/index.html