A* 搜索算法（A-Star Search Algorithm） 题目描述 A* 搜索算法是一种在图中寻找从起点到目标点的最短路径的启发式搜索算法。它结合了Dijkstra算法的完备性和贪婪最佳优先搜索的效率，通过评估函数 f(n) = g(n) + h(n) 指导搜索方向，其中 g(n) 是从起点到节点 n 的实际代价，h(n) 是从节点 n 到目标点的估计代价（启发函数）。算法要求启发函数 h(n) 是可采纳的（即不高估实际代价）以确保找到最优路径。该算法广泛应用于路径规划、游戏AI等领域。 解题过程 初始化 创建两个集合：开放列表（Open List）和关闭列表（Closed List）。开放列表存储待探索的节点，初始时包含起点；关闭列表存储已探索的节点。 为每个节点记录三个值： g(n) ：从起点到当前节点的实际代价。 h(n) ：从当前节点到目标点的估计代价（通过启发函数计算）。 f(n) = g(n) + h(n) ：节点的总评估代价。 起点的 g(start) = 0 ， f(start) = h(start) 。 选择评估节点 从开放列表中选取 f(n) 值最小的节点作为当前节点。若开放列表为空且未到达目标点，则路径不存在。 目标测试 若当前节点是目标点，则通过回溯父节点指针重构路径，算法结束。 扩展邻居节点 遍历当前节点的所有邻居节点。对每个邻居节点： 若邻居在关闭列表中，跳过。 计算临时 g_temp = g(current) + edge_cost(current, neighbor) 。 若邻居不在开放列表中，将其加入开放列表，设置 g(neighbor) = g_temp ， f(neighbor) = g_temp + h(neighbor) ，并记录父节点为当前节点。 若邻居已在开放列表中且 g_temp < g(neighbor) ，更新 g(neighbor) = g_temp 和 f(neighbor) ，并重置父节点为当前节点。 更新列表 将当前节点移入关闭列表，重复步骤2。 关键点说明 启发函数 h(n) ：必须可采纳（如曼哈顿距离、欧几里得距离）。若 h(n) 还满足一致性（单调性），则无需重新探索节点。 复杂度 ：最坏情况时间复杂度为 O(b^d)，其中 b 是分支因子，d 是路径深度。通过启发函数剪枝，实际效率远高于盲目搜索。 最优性保证 ：在 h(n) 可采纳时，A* 总能找到最短路径。