A* 算法

摘要

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

A* 算法概念

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

dijkstra execution

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

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

best fit execution

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

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

A* execution

可以通过控制 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_1A_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