前言

A 星搜索算法发表于 1968 年属于比较老、成熟的算法，由 Stanford 研究院的 Peter Hart, Nils Nilsson 以及 Bertram Raphael 发表。介绍 A 星算法本来应该先了解 A 算法，但这里先不说 A 算法，先来感性的了解一下跟它有关的其他算法。

广度优先搜索算法

如上图所示，广度优先算法，首先从起始点出发，逐步遍历完周围的所有点，然后再遍历周围点的周围所有点，如水波一样向外扩散，直到找到终点。但这样的做法需要遍历较多点，而且并不是所有方向都值得我们去变量，使算法的计算复杂度和效率都十分低。

Dijkstra 算法

要知道的是广度优先搜索算法认为移动到所有格子的代价是一致的，但事实上不是这样的。比如，高速路和城区路的速度就不一样，所消耗的时间成本也就不一样。

上图所示，假如在绿色方格之间移动代价是褐色的三倍，也许就不能简单的走直线了。Dijkstra 算法每决定移动一个格子都会计算它离起点所需要的代价，这个代价我们即为 \(g(n)\)，\(n\) 表示移动到第 n 个方格时需要付出的代价。当然在走出第 n 步时有多个方格可以供选择，但每个方格所需要付出的代价肯定不一样，Dijkstra 算法会选择最小代价的方格。如图，它就不会简单地穿过绿色到达终点了。当 \(g(n)\) 为到起点的欧式距离或者曼哈顿距离的线性关系，那么 Dijkstra 算法就退化为广度优先搜索算法。

最佳优先搜索算法

Dijkstra 算法是根据距离起点的代价来计算下一步该选择哪一个格子的，那么如果我们最开始就预先估计下一步中的所有格子哪一个离终点更近，这样也能更快到达终点。如上图，所示每次选取都选择离终点最近的格子，然后再遍历这个格子附近的格子哪个离终点更近（一般使用 \(h(n)\) 表示第 n 个格子到终点的代价）这种算法称之为最佳优先算法。

当然这种算法很容易受到估计函数 \(h(n)\) 的影响，如果估计函数取得不当也许就不是最短路径了。

A * 搜索算法

A 星算法则是整合上述的优缺点，首先来明白几个概念：

♠ \(g(n)\) 代表移动到第 n 个方格时距离起点的代价。\(g(n)\) 的大小肯定是跟之前的 n-1 个格子的选择有关的，但是每次选择肯定都是选择代价最小的格子（如果仅用 \(g(n)\) 来衡量）。

♣ \(h(n)\) 代表移动到第 n 个方格时距离终点的估计代价（往往我们并不完全知道这个格子距离终点需要多少代价）。\(h(n)\) 的大小范围（也就是第 n 步能选择的范围）当然也是跟之前的 n-1 个格子的选择有关的，但是每次选择肯定都是选择代价最小的格子（如果仅用 \(h(n)\) 来衡量）。

♥ \(f(n)\) 是整体的估价函数，一般 \(f(n) = g(n) + h(n)\)。

算法细节

一般会用两个表来记录整个找路径的过程，一个称之为 open 表（用于存储可能的选择），另外一个称之为 closed 表（用于存储已经做的选择）：

• 首先将初始的节点 \(s_0\)（可以理解为起点的格子）放入 open 表中，因为没有其他选择-_-。此时 \(f(s_0) = g(s_0) + h(s_0)\)；
• 如果 open 表为空，表示上一步没有留下可以被选择的节点，则问题无解，退出搜索；
• 把 open 表的第一个节点取出来放入 closed 表，并记该节点为 \(n\)（即第 n 步选择的节点）。
• 考察节点 n 是否为目标节点，若是，找到问题解，退出。
• 若节点 n 不可以扩展，则转到第二步；
• 扩展节点 n（即查看这个格子周围的格子），生成子节点 \(n_i \ (i=1,2,3,\dots)\)，首先这些子节点得不在 closed 表中，也不再 open 表中，然后放入 open 表中。计算每个子节点的估价值 \(f(n_i)\)，并按估价值从小到大的顺序排好。
• 转至第二步。

由上述算可知，open 表用一个优先队列，closed 表用一个链表就可以了。

A * 算法的一些性质

首先介绍 \(f^*(n)\) 的定义：其为从初始节点 \(s_0\) 出发，经过节点 n 达到目标节点的真实计算的最小代价值（不存在估计），易得如果此点在最优路径上，那么 \(f^*\) 为选择最优路径时的代价值，并且在最优路径上的所有点有：\(f^*(n_0) = f^*(n_1) = f^*(n_2) = f^*(n_3) = \dots\)（因为 \(f^*\) 在计算经过某一个点的时候必然计算了也只计算了最优路径上其他所有的点。）

又由于 \(f^*(n) = g^*(n) + h^*(n)\)，因此 \(g^*(n)\) 为从初始节点 \(s_0\) 出发，**经过节点 n ** 时的最短路径的代价值，虽然这条路径很容易算出来，并且有可能还没找到最短的那一条，所以 \(g(n)\) 依然是对 \(g^*(n)\) 的估计。\(h^*(n)\) 则是从节点 n 出发到目标节点的最短路径的代价值，如果有多个目标节点选择最短的那一条。

A * 算法对上述进行了限制：

♥ \(g(n)\) 是对 \(g^*(n)\) 的估计，且有 \(g(n) \gt g^*(n) \ge 0\)。
♦ \(h(n)\) 会被设计为 \(h^*(n)\) 的下界，且有 \(h^*(n) \gt h^(n)\)。

可纳性

首先，搜索算法能在有限步内找到一条初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可纳的。（先只考虑有限图）对于有限图，如果从初始节点到目标节点有路径存在，则 A * 算法一定能成功结束。

这里在设计 A 星算法的 \(f(n)\) 需要满足其是递增的。那就可以简单证明一下了，因为从 \(s_0\) 离开 open 进入 closed，必有最优路径上的 \(n_1\) 加入 open，则有：

由于 \(f(n)\) 是递增易得：\(f(n_1)=f(s_0)\)，而其余点的 \(f\) 都是大于或等于 \(f(s_0)\) 的，因此肯定会选择 \(n_1\) 进行扩展，而当 \(n_1\) 进入 closed，\(n_2\) 又会加入 open。由此，可预料算法不仅会成功结束，还会以最优路径而结束。

最优性

A 星算法的搜索效率其实极大取决于 \(h(n)\)，因为 \(h(n) \e h^*(n)\) 的，所以它越大可以扩展的节点就越少，搜索的效率就越高。此外，关于 \(h(n)\) 的设计还需要满足：
对于任意节点 \(n_i\) 到其子节点 \(n_j\) 有：\(h(n_i) \le h(n_j) + c(n_i,n_j)\)。其中 \(c(n_i,n_j)\) 代表从父节点到子节点需要的代价，其实可以表示为 \(g(n_j) - g(n_i)\)。ze上式可表达为：

这不就是说 \(f\) 是递增的吗，因此 A 星算法只要在有限域内存在最优路径满足对 \(g,h\) 的设计下一定能取得最优解。