A*搜索算法

字数 2471 2025-11-04 12:00:41

A*搜索算法

A*搜索算法是一种广泛应用于路径规划和图遍历的高效算法。它结合了Dijkstra算法的完备性（保证找到最短路径）和贪心最佳优先搜索算法的启发性（倾向于探索目标方向），通过评估函数来指导搜索方向，从而在大多数情况下比两者都更快。

1. 核心思想：评估函数 f(n)

A*算法的核心在于它为图中的每个节点 n 计算一个评估函数：
f(n) = g(n) + h(n)

g(n)：这是从起始节点到当前节点 n 的实际代价。这个值是已知且准确的，就像在Dijkstra算法中记录的距离一样。
h(n)：这是从当前节点 n 到目标节点的预估代价，也称为启发式函数。这个值是一个估计，并不是精确值。h(n) 的设计质量直接决定了A*算法的效率。

算法的目标是找到一条路径，使得路径终点（目标节点）的 f(n) 值最小。

2. 算法流程详解

算法需要维护两个集合：

开放列表：一个优先队列（通常是最小堆），存放所有已发现但尚未评估的节点。节点按照其 f(n) 值进行排序，f(n) 值最小的节点拥有最高优先级。
关闭列表：一个集合（如哈希表），存放所有已经评估过的节点。这些节点的最优路径已被确定，无需再次处理。

步骤如下：

初始化：
- 将起始节点 S 加入开放列表。设置 S 的 g(S) = 0，并计算其启发值 h(S) 和评估值 f(S) = g(S) + h(S)。
- 关闭列表初始化为空。
循环开始：当开放列表不为空时，循环执行以下步骤：
a. 选择当前节点：从开放列表中取出 f(n) 值最小的节点，我们称其为当前节点 N。如果开放列表使用优先队列，这就是出队操作。
b. 目标测试：如果当前节点 N 就是目标节点 T，那么搜索成功。我们可以通过从 T 反向追踪父节点来重构路径。
c. 扩展节点：将节点 N 从开放列表移至关闭列表，表示已评估。然后，遍历 N 的所有邻居节点 M。
d. 处理邻居节点 M：对于每个邻居 M：
* 跳过已关闭节点：如果 M 在关闭列表中，直接忽略它，因为它的最短路径已经确定。
* 计算临时g值：计算从起点经过 N 到达 M 的代价：temp_g = g(N) + cost(N, M)，其中 cost(N, M) 是从 N 到 M 的边的权重。
* 判断是否发现新路径或更优路径：
* 如果 M 不在开放列表中，说明它是新发现的节点。将 M 加入开放列表，设置其 g(M) = temp_g，计算 f(M) = g(M) + h(M)，并记录 N 为 M 的父节点。
* 如果 M 已经在开放列表中，说明我们找到了一条到达 M 的新路径。比较新路径的代价 temp_g 和之前记录的 g(M)：
- 如果 temp_g < g(M)，说明新路径更优。于是更新 M 的 g(M) 为 temp_g，并相应更新 f(M)。同时，将 M 的父节点设置为 N。由于 f(M) 改变了，需要调整开放列表（优先队列）中 M 的位置。
- 如果 temp_g >= g(M)，说明新路径更差或一样，不做任何处理。
循环结束：如果开放列表为空，意味着已经遍历所有可达节点但仍未找到目标节点，此时搜索失败，不存在从起点到目标的路径。

3. 启发式函数 h(n) 的关键性质

启发式函数 h(n) 的选择至关重要，它必须满足以下条件以保证A*算法的正确性和效率：

可采纳性：h(n) 永远不能高估从当前节点 n 到目标节点的实际最小代价。即 h(n) <= h*(n)，其中 h*(n) 是真实的实际代价。这个性质保证了A*算法找到的路径一定是最短路径。
- 例子：在网格地图中，曼哈顿距离（只能上下左右移动）或直线距离（欧几里得距离）都是可采纳的，因为它们都是两点间最短路径的乐观估计。
一致性（或称单调性）：对于任意节点 n 和其邻居节点 m，满足 h(n) <= cost(n, m) + h(m)。这可以理解为启发函数不会“欺骗”你，认为从 n 到目标的代价比先走到邻居 m 再到目标的代价还要大。一致性是可采纳性的更强形式。如果 h(n) 是一致的，那么当A*算法扩展一个节点时，到达该节点的路径一定是最优路径，它的 g(n) 值无需再次被更新，算法效率更高。

4. 一个简单的例子

假设有一个4x4的网格，起点在(0,0)，目标点在(3,3)。我们可以使用曼哈顿距离作为启发式函数：h(n) = |x_n - x_goal| + |y_n - y_goal|。

起点(0,0)：g=0, h=6, f=6。加入开放列表。
取出f值最小的(0,0)进行扩展。检查其邻居(0,1)和(1,0)。
- (0,1)：g=1, h=5, f=6。加入开放列表。
- (1,0)：g=1, h=5, f=6。加入开放列表。
此时开放列表中有(0,1)和(1,0)，f值都是6。假设我们取出(0,1)进行扩展。检查其邻居(0,2), (1,1), (0,0)。
- (0,2)：g=2, h=4, f=6。加入开放列表。
- (1,1)：g=2, h=4, f=6。加入开放列表。
- (0,0)在关闭列表中，忽略。
算法持续进行，每次都会优先扩展那些看起来离目标更近（f值小）的节点，直到最终找到目标点(3,3)。

总结
A*搜索算法通过结合已知代价 g(n) 和预估代价 h(n)，智能地引导搜索方向，在保证找到最优路径的前提下，大幅减少了需要探索的节点数量，是解决最短路径问题非常强大且实用的工具。

A* 搜索算法 A* 搜索算法是一种广泛应用于路径规划和图遍历的高效算法。它结合了Dijkstra算法的完备性（保证找到最短路径）和贪心最佳优先搜索算法的启发性（倾向于探索目标方向），通过评估函数来指导搜索方向，从而在大多数情况下比两者都更快。 1. 核心思想：评估函数 f(n) A* 算法的核心在于它为图中的每个节点 n 计算一个评估函数： f(n) = g(n) + h(n) g(n) ：这是从起始节点到当前节点 n 的实际代价。这个值是已知且准确的，就像在Dijkstra算法中记录的距离一样。 h(n) ：这是从当前节点 n 到目标节点的预估代价，也称为启发式函数。这个值是一个估计，并不是精确值。 h(n) 的设计质量直接决定了A* 算法的效率。算法的目标是找到一条路径，使得路径终点（目标节点）的 f(n) 值最小。 2. 算法流程详解算法需要维护两个集合：开放列表：一个优先队列（通常是最小堆），存放所有已发现但尚未评估的节点。节点按照其 f(n) 值进行排序， f(n) 值最小的节点拥有最高优先级。关闭列表：一个集合（如哈希表），存放所有已经评估过的节点。这些节点的最优路径已被确定，无需再次处理。步骤如下：初始化：将起始节点 S 加入开放列表。设置 S 的 g(S) = 0 ，并计算其启发值 h(S) 和评估值 f(S) = g(S) + h(S) 。关闭列表初始化为空。循环开始：当开放列表不为空时，循环执行以下步骤： a. 选择当前节点：从开放列表中取出 f(n) 值最小的节点，我们称其为当前节点 N 。如果开放列表使用优先队列，这就是出队操作。 b. 目标测试：如果当前节点 N 就是目标节点 T ，那么搜索成功。我们可以通过从 T 反向追踪父节点来重构路径。 c. 扩展节点：将节点 N 从开放列表移至关闭列表，表示已评估。然后，遍历 N 的所有邻居节点 M 。 d. 处理邻居节点 M ：对于每个邻居 M ： * 跳过已关闭节点：如果 M 在关闭列表中，直接忽略它，因为它的最短路径已经确定。 * 计算临时g值：计算从起点经过 N 到达 M 的代价： temp_g = g(N) + cost(N, M) ，其中 cost(N, M) 是从 N 到 M 的边的权重。 * 判断是否发现新路径或更优路径： * 如果 M 不在开放列表中，说明它是新发现的节点。将 M 加入开放列表，设置其 g(M) = temp_g ，计算 f(M) = g(M) + h(M) ，并记录 N 为 M 的父节点。 * 如果 M 已经在开放列表中，说明我们找到了一条到达 M 的新路径。比较新路径的代价 temp_g 和之前记录的 g(M) ： - 如果 temp_g < g(M) ，说明新路径更优。于是更新 M 的 g(M) 为 temp_g ，并相应更新 f(M) 。同时，将 M 的父节点设置为 N 。由于 f(M) 改变了，需要调整开放列表（优先队列）中 M 的位置。 - 如果 temp_g >= g(M) ，说明新路径更差或一样，不做任何处理。循环结束：如果开放列表为空，意味着已经遍历所有可达节点但仍未找到目标节点，此时搜索失败，不存在从起点到目标的路径。 3. 启发式函数 h(n) 的关键性质启发式函数 h(n) 的选择至关重要，它必须满足以下条件以保证A* 算法的正确性和效率：可采纳性： h(n) 永远不能高估从当前节点 n 到目标节点的实际最小代价。即 h(n) <= h*(n) ，其中 h*(n) 是真实的实际代价。这个性质保证了A* 算法找到的路径一定是最短路径。例子：在网格地图中，曼哈顿距离（只能上下左右移动）或直线距离（欧几里得距离）都是可采纳的，因为它们都是两点间最短路径的乐观估计。一致性（或称单调性）：对于任意节点 n 和其邻居节点 m ，满足 h(n) <= cost(n, m) + h(m) 。这可以理解为启发函数不会“欺骗”你，认为从 n 到目标的代价比先走到邻居 m 再到目标的代价还要大。一致性是可采纳性的更强形式。如果 h(n) 是一致的，那么当A* 算法扩展一个节点时，到达该节点的路径一定是最优路径，它的 g(n) 值无需再次被更新，算法效率更高。 4. 一个简单的例子假设有一个4x4的网格，起点在(0,0)，目标点在(3,3)。我们可以使用曼哈顿距离作为启发式函数： h(n) = |x_n - x_goal| + |y_n - y_goal| 。起点(0,0)： g=0 , h=6 , f=6 。加入开放列表。取出f值最小的(0,0)进行扩展。检查其邻居(0,1)和(1,0)。 (0,1)： g=1 , h=5 , f=6 。加入开放列表。 (1,0)： g=1 , h=5 , f=6 。加入开放列表。此时开放列表中有(0,1)和(1,0)，f值都是6。假设我们取出(0,1)进行扩展。检查其邻居(0,2), (1,1), (0,0)。 (0,2)： g=2 , h=4 , f=6 。加入开放列表。 (1,1)： g=2 , h=4 , f=6 。加入开放列表。 (0,0)在关闭列表中，忽略。算法持续进行，每次都会优先扩展那些看起来离目标更近（f值小）的节点，直到最终找到目标点(3,3)。总结 A* 搜索算法通过结合已知代价 g(n) 和预估代价 h(n) ，智能地引导搜索方向，在保证找到最优路径的前提下，大幅减少了需要探索的节点数量，是解决最短路径问题非常强大且实用的工具。