A*搜索算法（A-Star Search Algorithm）

题目描述：
A搜索算法是一种在图中找到从起始顶点到目标顶点的最短路径的算法。它广泛应用于路径规划和图遍历。与Dijkstra算法不同，A算法使用启发式函数来估算从当前顶点到目标顶点的代价，从而优先探索更有希望的路径，提高搜索效率。假设我们有一个带权图，每个边有一个非负权值（代表距离或成本），同时我们有一个启发式函数h(n)，它估算从任意顶点n到目标顶点的最小代价。要求使用A*算法找到从起始顶点s到目标顶点t的最短路径。

解题过程：

1. 算法核心思想：
   A算法结合了Dijkstra算法的实际代价（从起点到当前顶点的已知代价g(n)）和贪心最佳优先搜索的启发式代价（从当前顶点到目标的估算代价h(n)）。它维护一个优先队列（通常是最小堆），根据总代价f(n) = g(n) + h(n)来选择下一个要扩展的顶点。如果启发式函数h(n)是可采纳的（即从不高估实际代价），则A能保证找到最短路径。

2. 数据结构准备：

   • 使用一个优先队列（open set）来存储待探索的顶点，按f(n)排序。
   • 使用一个集合（closed set）来记录已探索的顶点，避免重复处理。
   • 对于每个顶点n，维护以下信息：
     • g(n)：从起点s到n的实际最短代价（已知）。
     • h(n)：从n到目标t的启发式估算代价（由启发式函数给出）。
     • f(n) = g(n) + h(n)：总估算代价。
     • parent(n)：路径中n的前驱顶点，用于重构路径。

3. 算法步骤：
   a. 初始化：

   • 将起点s加入优先队列，设置g(s) = 0，h(s)由启发式函数计算，f(s) = g(s) + h(s)，parent(s)为null。
   • closed set初始为空。

   b. 循环直到队列为空或找到目标：

   • 从优先队列中取出f(n)最小的顶点n（当前最有望的顶点）。
   • 如果n是目标t，则算法结束，通过parent指针反向重构路径。
   • 否则，将n标记为已探索（加入closed set）。
   • 遍历n的所有邻居顶点m：
     • 如果m已在closed set中，跳过（因为已探索过）。
     • 计算从s经过n到m的临时g值：temp_g = g(n) + weight(n, m)（weight是边n→m的权值）。
     • 如果m不在优先队列中（未探索过），或temp_g小于当前已知的g(m)：
       • 更新m的parent为n。
       • 设置g(m) = temp_g。
       • 计算f(m) = g(m) + h(m)（h(m)由启发式函数给出）。
       • 如果m不在优先队列中，将其加入；否则，调整其在队列中的位置（因g(m)更新可能导致f(m)减小）。

4. 启发式函数要求：

   • 为确保找到最短路径，h(n)必须可采纳（admissible）：即对任意n，h(n) ≤ 实际从n到t的最小代价。
   • 如果h(n)还满足一致性（consistency，或单调性）：对于任意边(n, m)，有h(n) ≤ weight(n, m) + h(m)，则A*在处理顶点时无需重新探索（closed set中的顶点不会重新打开），效率更高。

5. 示例说明：
   假设一个网格图，顶点是网格点，边权为1（相邻移动）。启发式h(n)使用曼哈顿距离（到目标的水平与垂直距离和）。A*会优先探索靠近目标的路径，避免像Dijkstra那样均匀扩展，从而更快找到路径。

通过以上步骤，A*能高效地找到最短路径，适用于游戏AI、地图导航等场景。关键是选择合适的启发式函数以平衡准确性和计算成本。