A*算法（A-Star Algorithm）是一种启发式搜索算法，广泛应用于路径规划（如游戏寻路、机器人导航）、图遍历等领域。它通过结合实际代价与启发式估计代价，在保证找到最优路径的同时，显著减少搜索范围，效率远高于传统的 Dijkstra 算法或贪心搜索。
一、核心思想：评估函数 f(n)
A*算法的核心是定义一个评估函数，用于优先扩展'最有希望'到达目标的节点。该函数表示为： f(n) = g(n) + h(n)
- g(n)：从起点（Start）到当前节点 n 的实际代价（已消耗的代价）。例如，在网格地图中，若每一步移动代价为 1，则 g(n) 是起点到 n 的步数。
- h(n)：从当前节点 n 到目标节点（Goal）的估计代价（启发式预测）。它是算法的'智能'来源，需满足可采纳性（Admissible）——即不高估实际代价（否则可能错过最优解）。
- f(n)：节点 n 的总代价估计，指导搜索方向（优先扩展 f(n) 最小的节点）。
二、算法步骤
A*算法的执行流程可概括为以下步骤：
1. 初始化数据结构
- 开放列表（Open List）：优先队列（最小堆），存储待扩展的节点，按 f(n) 排序（f 最小的节点在顶部）。初始时仅包含起点。
- 关闭列表（Closed List）：集合或哈希表，存储已扩展过的节点（避免重复处理）。初始为空。
- 代价记录：维护两个字典（或数组），分别记录每个节点的 g(n)（实际代价）和 f(n)（总代价）。
2. 主循环：扩展节点
重复以下步骤直到找到目标或开放列表为空（无路径）：
- 步骤 1：从开放列表中取出 f(n) 最小的节点 n（称为当前节点）。
- 步骤 2：若 n 是目标节点，回溯路径并返回结果（算法结束）。
- 步骤 3：将 n 加入关闭列表（标记为已处理）。
- 步骤 4：遍历 n 的所有邻居节点 m（上下左右、对角线等，取决于移动规则）：
- 若 m 在关闭列表中：跳过（已处理过更优路径）。
- 计算临时 g 值：temp_g = g(n) + 从 n 到 m 的移动代价（如相邻节点代价为 1，对角线为√2）。
- 若 m 不在开放列表中，或 temp_g < g(m)（发现更优路径）：
- 更新 g(m) = temp_g。
- 计算 h(m)（启发式估计值）。
- 计算 f(m) = g(m) + h(m)。
若 m 不在开放列表中，将其加入开放列表；否则，更新其在开放列表中的优先级（因 f(m) 可能变小）。
