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

题目描述
A*搜索算法是一种用于在图中寻找从起点到目标节点的最短路径的启发式搜索算法。它结合了Dijkstra算法的完备性和贪婪最佳优先搜索的效率，通过评估函数 f(n) = g(n) + h(n) 指导搜索方向，其中：

• g(n) 是从起点到节点 n 的实际代价
• h(n) 是从节点 n 到目标节点的预估代价（启发函数）

解题步骤详解

1. 初始化数据结构

   • 创建优先队列（OPEN表）用于存储待探索节点，按 f(n) 值排序
   • 创建集合（CLOSED表）记录已探索节点
   • 初始化起点的 g(起点)=0, f(起点)=h(起点)
   • 将起点加入OPEN表

2. 主循环流程

   • 当OPEN表非空时循环：
     a. 从OPEN表中取出f值最小的节点作为当前节点
     b. 若当前节点是目标节点，则重构路径并结束
     c. 将当前节点移入CLOSED表

3. 邻居节点处理

   • 遍历当前节点的所有邻居：
     a. 若邻居在CLOSED表中，则跳过
     b. 计算临时g值：g_temp = g(当前) + 边权值
     c. 若邻居不在OPEN表或g_temp < 原g值：
     • 更新g(邻居) = g_temp
     • 计算f(邻居) = g(邻居) + h(邻居)
     • 记录父节点指针（用于路径重构）
     • 若邻居不在OPEN表则加入

4. 路径重构

   • 从目标节点开始，沿父节点指针回溯至起点
   • 反转路径序列得到最终路径

关键特性说明

• 启发函数 h(n) 必须可采纳（不高估实际代价）才能保证最优性
• 若h(n)满足一致性（三角不等式），则节点只需处理一次
• 当h(n)=0时退化为Dijkstra算法，当g(n)=0时退化为贪婪搜索

实例演示
假设网格图中：

• 起点(0,0)，目标(2,2)
• 使用曼哈顿距离作为h(n)
• 算法会优先探索f值小的节点，逐步逼近目标
• 最终输出路径为[(0,0),(1,0),(2,0),(2,1),(2,2)]（具体取决于实际障碍）

该算法通过平衡实际代价和预估代价，显著减少了需要探索的节点数量，在路径规划等领域应用广泛。