《经典图论算法》A*搜索算法

摘要：

1，A*算法的介绍

2，A*算法原理

3，A*算法步骤

4，常见评估函数

4.1 曼哈顿距离(Manhattan Distance)

4.2 欧几里得距离(Euclidean Distance)

4.3 切比雪夫距离(Chebyshev Distance)

5，A*算法代码实现

1，A*算法的介绍

A*搜索算法(A* search algorithm)又称A*算法(A-star Algorithm)，是比较流行的启发式搜索算法之一，被广泛应用于路径优化领域。

A*算法结合了 Dijkstra 算法的优点(即保证找到最短路径)和贪心算法最佳优先搜索的优点(通过启发式函数引导搜索方向)，在大多数情况下能高效地找到最优路径。

举个例子，我们知道 BFS 搜索基本上是处于盲搜，它不知道目标值的大概方向，每次都是搜索离它最近的点。

如下图所示，如果使用 BFS 从起始点到目标点找一条最短的路径，可以看到红色框内的位置离目标点是越来越远，我们没必要提前搜索，先搜索离目标点最近的点即可。

离目标点位置越来越远的点是否可以舍弃，答案肯定是不行的，如下图所示，离目标点越来越近的点被墙挡住了，只能沿着离目标点远的点继续搜索。

2，A*算法原理

A*算法搜索的时候，我们需要确定当前位置到目标点的距离，要始终沿着离目标点最近的位置开始搜索，怎么确定这个距离呢？这里就涉及到了启发式函数的定义。

A* 算法是使用一个启发式函数 h(n) 来估计从位置 n 到目标点的代价(可以是距离，花费等)，并结合已知的从起始点到位置 n 的代价 g(n) ，综合考虑这两个值来选择搜索路径。其核心公式为：f(n)=g(n)+h(n)：

1，g(n) ：从起点到位置 n 的代价。

2，h(n) ：从位置 n 到目标点的估计代价（启发式函数）。

3，f(n) ：从起点经过位置 n 到目标点的总估计代价。

下面对这个公式进行展开讨论：

1，h(n) = 0：即启发式函数值为零，即只计算从起始点到位置 n 的代价，不需要启发函数，此时A*算法退化为Dijkstra算法，可以找到最短路径，但效率较低，因为失去了启发式搜索的优势。

2，h(n) < 实际代价：启发式函数的预估代价小于实际代价，A*算法能保证找到最短路径，但可能需要扩展更多的节点，运行较慢，并且 h(n) 越小，需要扩展的点就越多，运行就越慢，效率就越差。

3，h(n) = 实际代价：启发式函数的预估代价恰好等于实际代价，A*算法将只扩展必要的节点，运行非常快，效率也是最高的。但在实际情况中，很难完全准确的预估。

4，h(n) > 实际代价：启发式函数的预估代价大于实际代价，运行速度比较快，但找到的不一定是最优解。

5，g(n) = 0：不考虑从起始点到位置 n 的代价，只计算从位置 n 到目标点的代价，这个就是纯贪心算法，速度也是最快的，但找到的解不一定是最优的。

A*算法和Dijistra区别

Dijkstra算法计算源点到其他所有点的最短路径长度，不使用启发式函数，它是一个纯粹的广度优先搜索算法，空间和时间复杂度都很高。特别是在大规模图中，可能需要探索大量的节点，因此性能可能不佳。

A*算法通过启发式搜索策略，利用启发式函数来估算从当前节点到目标节点的成本，从而加速寻路过程。如果启发式选择得当，A*算法通常比Dijkstra算法更快，效率更高，搜索范围更小，因为它可以更直接地朝向目标节点前进。

3，A*算法步骤

1，创建一个空的开放列表(open list)，并把起始点放入其中，开放列表一般使用优先队列，节点按照 f(n) 的值进行排序，以确保优先查找 f(n) 值最小的节点。

2，创建一个空的关闭列表(closed list)，用于记录已经被探索过的节点，以避免重复探索。

3，从开放列表中取出 f(n) 值最小的节点 n 。

3.1，如果 n 是目标点，则终止并返回路径，否则，将 n 节点移到关闭列表中。

3.2，访问 n 的每个邻居节点 m：

3.2.1，如果 m 已在关闭列表中，则忽略它。

3.2.2，如果 m 不在开放列表中，计算 g(m) 、h(m) 和 f(m) ，并将它添加到开放列表中。

3.2.3，如果 m 已在开放列表中，并且通过 n 到达 m 的路径更短，则更新 g(m) 、h(m) 和 f(m) ，并设置 m 的父节点为 n。

4，重复上面的步骤 3 ，如果找到目标节点，即可通过回溯父节点来找到最短路径。如果遍历结束后仍未找到终点，说明不存在从起点到终点的路径。

A*算法的步骤是它的核心部分，主要是在第三步，一定要完全掌握。可以参考下我们前面讲的，开放列表相当于BFS中的队列，关闭列表相当于BFS中的visited数组，记录哪些点被访问过了，避免重复访问。

4，常见评估函数

上面我们讲了A*搜索算法的原理以及实现步骤，其中关于距离的启发式函数没有介绍，A*算法的性能高度依赖于启发式函数的选择，一个好的启发式函数可以显著提高搜索效率。

启发式函数比较多，常见的有曼哈顿距离，欧几里得距离，切比雪夫距离。

4.1 曼哈顿距离（Manhattan Distance）

曼哈顿距离适用于只能沿水平或垂直方向移动的网格，如城市街道，也称为城市街区距离。对于二维平面上的两个点 (x1, y1) 和 (x2, y2)，曼哈顿距离为 |x1 - x2| + |y1 - y2| 。

例如，点 (1, 3) 和 (4, 6) 的曼哈顿距离为 |1 - 4| + |3 - 6| = 3 + 3 = 6 。

4.2 欧几里得距离（Euclidean Distance）

欧几里得距离是两点之间的直线距离，对于二维平面上的两个点 (x1, y1) 和 (x2, y2)，欧几里得距离为 sqrt((x1 - x2)^2 + (y1 - y2)^2) 。

例如，点 (1, 1) 和 (4, 5) 的欧几里得距离为 sqrt((1 - 4)^2 + (1 - 5)^2) = sqrt(9 + 16) = 5 。

4.3 切比雪夫距离（Chebyshev Distance）

切比雪夫距离是两点之间的最大水平和垂直距离，对于二维平面上的两个点 (x1, y1) 和 (x2, y2)，切比雪夫距离为 max(|x1 - x2|, |y1 - y2|) 。

例如，点 (1, 1) 和 (4, 5) 的切比雪夫距离为 max(|1 - 4|, |1 - 5|) = 4 。

5，A*算法代码实现

A*算法可以看作是BFS的增强版，它根据启发式函数的引导，慢慢朝着目标点移动，我们用下面这个图来看下它怎么搜索的。

因为每次搜索的时候都会计算当前位置的上下左右四个方向，如果搜索的顺序改变可能会导致路径不同，如下图所示两张图，分别是按照右下左上和上下左右顺序搜索的两张图，其中关闭列表中的顶点包含最短路径的顶点。