什么是A*算法？

很多朋友对于什么是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) S 到n。其次，在搜索过程中，我们还没有找到从n到G的最短路径，所以我们不知道h(n)是什么。

如何解决这个困难呢？一种解决方案是用当前获得的从S 到n 的距离g'(n) 替换未知的最短距离g(n)，并使用估计值h'(n) 替换从n 到n 的最短距离h(n)。 G，基于这两个近似产生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]