图论中的 A* 搜索算法

字数 2908 2025-12-19 19:36:53

图论中的 A* 搜索算法

题目描述

A*（A-Star）搜索算法是一种广泛用于路径查找和图遍历的启发式搜索算法。它在Dijkstra算法的基础上，引入了启发式函数（heuristic function）来引导搜索方向，从而有望更快地找到从起点到目标点的最短路径。其核心思想是，在每一步扩展时，不仅考虑从起点到当前节点的实际代价 g(n)，还通过启发式函数 h(n) 估计从当前节点到目标节点的剩余代价，并选择综合评估 f(n) = g(n) + h(n) 最小的节点进行扩展。

本题目要求：给定一个有向或无向图（通常为网格图或状态空间图），图中每条边带有非负权重（代表距离或代价），并给定起点 s 和目标点 t，以及一个启发式函数 h(n)（通常为节点 n 到目标 t 的直线距离、曼哈顿距离等），请使用 A* 搜索算法，找出从 s 到 t 的一条最短路径。

核心概念与性质

可采纳性（Admissibility）：启发式函数 h(n) 必须是从节点 n 到目标 t 的真实最短路径代价的 乐观估计（即 h(n) ≤ d(n, t)，其中 d(n, t) 是真实最短距离）。这保证了 A* 能够找到最优解。
一致性（Consistency，或称单调性）：对于图中任意两个相邻节点 u 和 v，需满足 h(u) ≤ w(u, v) + h(v)，其中 w(u, v) 是边 (u, v) 的权重。一致性是可采纳性的更强条件，它保证了在搜索过程中，每个节点第一次被扩展时，其 g(n) 值已经是最小值，无需后续重新更新。

解题步骤详解

第一步：数据结构准备

我们需要以下数据结构来跟踪搜索过程：

openSet（优先队列）：存储待扩展的节点，按 f(n) = g(n) + h(n) 从小到大排序。通常用二叉堆（如 C++ 的 priority_queue）实现。
gScore（字典/数组）：记录从起点 s 到每个节点 n 的已知最短实际代价 g(n)。初始时，g(s) = 0，其他节点为无穷大。
fScore（字典/数组）：记录每个节点 n 的估计总代价 f(n) = g(n) + h(n)。初始时，f(s) = h(s)。
cameFrom（字典/数组）：记录到达每个节点的前驱节点，用于最终回溯重构路径。

第二步：初始化

将起点 s 加入 openSet，设置 gScore[s] = 0，fScore[s] = h(s)。
其他所有节点的 gScore 设为无穷大（表示尚未访问或代价未知）。

第三步：主循环——扩展节点

只要 openSet 非空，就重复以下步骤：

选择节点：从 openSet 中弹出 f(n) 最小的节点 current。如果 current 就是目标 t，则搜索成功，进入路径回溯。
检查邻居：遍历 current 的所有邻居节点 neighbor。
计算试探性代价：计算从起点 s 经过 current 到达 neighbor 的试探性实际代价 tentative_g = gScore[current] + w(current, neighbor)。
更新最优代价：如果 tentative_g 小于当前记录的 gScore[neighbor]，说明找到了一条到达 neighbor 的更优路径，则执行更新：
- 更新 gScore[neighbor] = tentative_g。
- 更新 fScore[neighbor] = gScore[neighbor] + h(neighbor)。
- 更新 cameFrom[neighbor] = current。
- 如果 neighbor 不在 openSet 中，将其加入 openSet（优先队列会根据新的 fScore 自动调整顺序）。

第四步：路径重构

一旦从 openSet 弹出的 current 是目标节点 t，则通过 cameFrom 字典从 t 反向追溯到 s，得到最短路径。具体步骤：

初始化 path = [t]。
令 current = t。
当 current 不等于 s 时，将 current = cameFrom[current] 插入 path 开头。
最终 path 即为从 s 到 t 的最短路径。

第五步：处理无解情况

如果 openSet 为空（即所有可达节点都已扩展，但未找到目标 t），则说明从 s 到 t 不可达，算法结束，返回无解。

算法复杂度分析

时间复杂度：最坏情况下，A* 会扩展所有节点（与 Dijkstra 相同），因此为 O(E log V)，其中 E 为边数，V 为节点数（基于二叉堆的优先队列）。但实际上，在好的启发式函数引导下，扩展的节点数远少于 Dijkstra。
空间复杂度：需要存储 openSet、gScore、fScore 和 cameFrom，均为 O(V)。

启发式函数设计示例

以二维网格图（允许上下左右移动，边权为 1）为例：

曼哈顿距离：h(n) = |n.x - t.x| + |n.y - t.y|。满足可采纳性和一致性（当只能向四个方向移动时）。
欧几里得距离：h(n) = sqrt((n.x - t.x)^2 + (n.y - t.y)^2)。满足可采纳性，但不一定满足一致性（但通常在实践中仍有效）。

一个简单实例

假设有一个 4x4 网格（坐标从 (0,0) 到 (3,3)），起点 s = (0,0)，目标 t = (3,3)，边权为 1，采用曼哈顿距离启发式：

h(s) = |0-3| + |0-3| = 6。
算法会优先扩展 f(n) 较小的节点（即更靠近目标的方向），从而避免探索所有节点，更快找到路径 (0,0)→(1,0)→(2,0)→(3,0)→(3,1)→(3,2)→(3,3) 或其他等价最短路径。

关键注意事项

如果启发式函数 h(n) 不是可采纳的，A* 可能无法找到最优解。
如果图中有负权边，A* 无法保证正确性（与 Dijkstra 相同）。
当 h(n) = 0 时，A* 退化为 Dijkstra 算法；当 h(n) 恰好等于真实最短距离时，A* 会直接沿最优路径扩展，效率最高。
在实现中，为避免重复扩展节点，可以在节点从 openSet 弹出后，将其标记为已访问（关闭列表），但通常通过 gScore 的比较就足够。

通过以上步骤，A* 能够有效结合实际代价与启发式信息，在保证最优性的前提下，显著减少搜索空间，是路径规划、游戏 AI、机器人导航等领域的核心算法。

图论中的 A* 搜索算法题目描述 A* （A-Star）搜索算法是一种广泛用于路径查找和图遍历的启发式搜索算法。它在Dijkstra算法的基础上，引入了启发式函数（heuristic function）来引导搜索方向，从而有望更快地找到从起点到目标点的最短路径。其核心思想是，在每一步扩展时，不仅考虑从起点到当前节点的实际代价 g(n) ，还通过启发式函数 h(n) 估计从当前节点到目标节点的剩余代价，并选择综合评估 f(n) = g(n) + h(n) 最小的节点进行扩展。本题目要求：给定一个有向或无向图（通常为网格图或状态空间图），图中每条边带有非负权重（代表距离或代价），并给定起点 s 和目标点 t ，以及一个启发式函数 h(n) （通常为节点 n 到目标 t 的直线距离、曼哈顿距离等），请使用 A* 搜索算法，找出从 s 到 t 的一条最短路径。核心概念与性质可采纳性（Admissibility）：启发式函数 h(n) 必须是从节点 n 到目标 t 的真实最短路径代价的乐观估计（即 h(n) ≤ d(n, t) ，其中 d(n, t) 是真实最短距离）。这保证了 A* 能够找到最优解。一致性（Consistency，或称单调性）：对于图中任意两个相邻节点 u 和 v ，需满足 h(u) ≤ w(u, v) + h(v) ，其中 w(u, v) 是边 (u, v) 的权重。一致性是可采纳性的更强条件，它保证了在搜索过程中，每个节点第一次被扩展时，其 g(n) 值已经是最小值，无需后续重新更新。解题步骤详解第一步：数据结构准备我们需要以下数据结构来跟踪搜索过程： openSet （优先队列）：存储待扩展的节点，按 f(n) = g(n) + h(n) 从小到大排序。通常用二叉堆（如 C++ 的 priority_queue ）实现。 gScore （字典/数组）：记录从起点 s 到每个节点 n 的已知最短实际代价 g(n) 。初始时， g(s) = 0 ，其他节点为无穷大。 fScore （字典/数组）：记录每个节点 n 的估计总代价 f(n) = g(n) + h(n) 。初始时， f(s) = h(s) 。 cameFrom （字典/数组）：记录到达每个节点的前驱节点，用于最终回溯重构路径。第二步：初始化将起点 s 加入 openSet ，设置 gScore[s] = 0 ， fScore[s] = h(s) 。其他所有节点的 gScore 设为无穷大（表示尚未访问或代价未知）。第三步：主循环——扩展节点只要 openSet 非空，就重复以下步骤：选择节点：从 openSet 中弹出 f(n) 最小的节点 current 。如果 current 就是目标 t ，则搜索成功，进入路径回溯。检查邻居：遍历 current 的所有邻居节点 neighbor 。计算试探性代价：计算从起点 s 经过 current 到达 neighbor 的试探性实际代价 tentative_g = gScore[current] + w(current, neighbor) 。更新最优代价：如果 tentative_g 小于当前记录的 gScore[neighbor] ，说明找到了一条到达 neighbor 的更优路径，则执行更新：更新 gScore[neighbor] = tentative_g 。更新 fScore[neighbor] = gScore[neighbor] + h(neighbor) 。更新 cameFrom[neighbor] = current 。如果 neighbor 不在 openSet 中，将其加入 openSet （优先队列会根据新的 fScore 自动调整顺序）。第四步：路径重构一旦从 openSet 弹出的 current 是目标节点 t ，则通过 cameFrom 字典从 t 反向追溯到 s ，得到最短路径。具体步骤：初始化 path = [t] 。令 current = t 。当 current 不等于 s 时，将 current = cameFrom[current] 插入 path 开头。最终 path 即为从 s 到 t 的最短路径。第五步：处理无解情况如果 openSet 为空（即所有可达节点都已扩展，但未找到目标 t ），则说明从 s 到 t 不可达，算法结束，返回无解。算法复杂度分析时间复杂度：最坏情况下，A* 会扩展所有节点（与 Dijkstra 相同），因此为 O(E log V) ，其中 E 为边数， V 为节点数（基于二叉堆的优先队列）。但实际上，在好的启发式函数引导下，扩展的节点数远少于 Dijkstra。空间复杂度：需要存储 openSet 、 gScore 、 fScore 和 cameFrom ，均为 O(V) 。启发式函数设计示例以二维网格图（允许上下左右移动，边权为 1）为例：曼哈顿距离： h(n) = |n.x - t.x| + |n.y - t.y| 。满足可采纳性和一致性（当只能向四个方向移动时）。欧几里得距离： h(n) = sqrt((n.x - t.x)^2 + (n.y - t.y)^2) 。满足可采纳性，但不一定满足一致性（但通常在实践中仍有效）。一个简单实例假设有一个 4x4 网格（坐标从 (0,0) 到 (3,3)），起点 s = (0,0) ，目标 t = (3,3) ，边权为 1，采用曼哈顿距离启发式： h(s) = |0-3| + |0-3| = 6 。算法会优先扩展 f(n) 较小的节点（即更靠近目标的方向），从而避免探索所有节点，更快找到路径 (0,0)→(1,0)→(2,0)→(3,0)→(3,1)→(3,2)→(3,3) 或其他等价最短路径。关键注意事项如果启发式函数 h(n) 不是可采纳的，A* 可能无法找到最优解。如果图中有负权边，A* 无法保证正确性（与 Dijkstra 相同）。当 h(n) = 0 时，A* 退化为 Dijkstra 算法；当 h(n) 恰好等于真实最短距离时，A* 会直接沿最优路径扩展，效率最高。在实现中，为避免重复扩展节点，可以在节点从 openSet 弹出后，将其标记为已访问（关闭列表），但通常通过 gScore 的比较就足够。通过以上步骤，A* 能够有效结合实际代价与启发式信息，在保证最优性的前提下，显著减少搜索空间，是路径规划、游戏 AI、机器人导航等领域的核心算法。