在现实生活中，我们经常会遇到求解最佳路径问题，比如导航软件要求从S点到G点的最短路径，A*算法就是一个有效的求解最佳路径的搜索算法。
假设我们在地图上求从S出发到达目标G的最短路径，每一个路口可以视为一个状态，最短路径问题就是在地图上找出一个从S到达G的状态序列，使得沿着这一状态序列行走的距离最短。该状态序列称为从S到G的最短路径，寻找最短路径的过程称为状态搜索。
图1：一个局部状态搜索图
图1给出一个状态搜索图的样例，其中每个节点代表一个状态，即路径中的一个路口，两个状态间的连线表示直通道路。为了找到一条从S到达G的路径，我们每次从上图中选择一个叶节点进行扩展，直到找到目标节点G为止。
问题是，在搜索图中有很多叶节点，究竟应该对哪个节点进行扩展呢？一个直观的方案是，如果某个叶节点n距离初始节点S的距离再加上节点n到目标节点G的最小距离之和最小，那么该节点处在最短路径上，应该优先扩展。我们用g(n)表示S到n的最短路径距离，用h(n)表示n到G的最短路径距离，则从S经过n到达G的总距离f(n)为：
f(n) = g(n) + h(n)
如果我们选择f(n)最小的叶节点进行扩展，将保证搜索效率最高。
然而，在实际搜索时我们无法直接利用f(n)来选择扩展节点。首先，在搜索过程中，我们并不知道当前搜索得到的S到n的路径是不是最短路径，因此当前记录的距离g’(n)并不一定等于S到n的最短距离g(n)。第二，在搜索过程中，我们还没有找到一条从n到G的最短路径，因此也就不知道h(n)是多少。
如何解决这一困难呢？一种方案是用当前得到的S到n的距离g’(n)代替未知的最短距离g(n)，并用一个估计值h’(n)代替n到G 的最短距离h(n)，基于这两个近似值得到f(n)的估计f’(n)=g’(n)+h’(n)，并基于f’(n)进行搜索。
算法首先从初始节点S开始，每次选择一个f’(n)值最小的叶节点进行扩展，直到扩展出目标G且f’(G)在所有叶节点中取值最小为止。在搜索过程中，如果遇到多条路径到达同一个节点的情况，需要更新从S到达该节点的最短路径估计g’(n)。
上述算法被称为A算法。在A算法中，对h’(n)没有明确限制，只要符合直觉即可，因此h’(n)可能比h(n)小，也可能比h(n)大，其中h(n)为n到G的最短路径。A算法不能保证找到的路径是最短路径。然而，如果对h’(n)加以限制，使得对于任何一个叶节点n，总有h’(n)<=h(n)，那么该算法找到的路径一定是最短的，此时A算法被称为A*算法。
在前述地图搜索任务中，我们可以通过城市的坐标值来计算两个城市之间的直线距离。显然，两点之间的直线距离肯定小于等于他们之间的实际最短路径距离。因此，利用这一直线距离来计算h’(n)可以满足A*算法的条件，所以一定可以搜索到一条最短路径。图2给出一个A*算法执行路径搜索的运行过程。
图2：A*算法搜索过程示意图[1]
A*算法不限于搜索地图上的最短路径，很多问题，只要可以转化为状态搜索问题，都可以使用A*搜索，比如：八数码问题、旅行商问题、传教士与野人问题等。
参考文献：
[1] An A* path finding algorithm animation, https://imgur.com/gallery/vC71luv
By：清华大学 马少平，王东