A* 搜索算法 题目描述：A* 搜索算法是一种在图形或网格中寻找从起点到终点的最短路径的启发式搜索算法。它通过评估函数 f(n) = g(n) + h(n) 来选择最有希望的节点进行扩展，其中 g(n) 是从起点到节点 n 的实际代价，h(n) 是从节点 n 到终点的预估代价（启发式函数）。 解题过程： 核心思想与评估函数 A* 算法的目标是高效地找到最短路径。它维护两个列表： 开放列表 ：存放待考察的节点。 关闭列表 ：存放已考察过的节点，避免重复处理。 算法的关键在于一个评估函数： f(n) = g(n) + h(n) 。 g(n) 是一个确切的数值，代表从 起点 走到当前节点 n 所实际已经花费的代价（例如，移动的步数、距离）。 h(n) 是一个估计的数值，代表从当前节点 n 到 终点 的预估代价。这个函数被称为 启发式函数 。它必须是 可采纳的 ，即它永远不能高估从节点 n 到终点的实际代价。这是保证 A* 算法能找到最短路径的关键。 算法步骤 让我们通过一个简单的网格示例来一步步理解。假设我们在一个网格上，从起点 S 走到终点 E，可以上下左右移动，每次移动代价为 1。我们使用 曼哈顿距离 （两点在标准坐标系上的绝对轴距之和）作为启发式函数 h(n) 。 初始化 ： 将起点 S 加入开放列表。记录它的值： g(S) = 0 ， h(S) 为 S 到 E 的曼哈顿距离， f(S) = g(S) + h(S) 。 关闭列表为空。 循环开始 ： a. 从开放列表中选取 f(n) 值最小的节点作为当前节点。在初始时，开放列表只有 S，所以当前节点是 S。 b. 将当前节点 S 从开放列表移出，并加入关闭列表（表示已处理）。 c. 检查当前节点 S 的 所有相邻且可通行的节点 （例如，上下左右四个方向，排除障碍物）。对于每个相邻节点（我们称之为“邻居”）： * 如果这个邻居已经在关闭列表中，则忽略它。 * 如果这个邻居 不在 开放列表中： * 计算它的 g 值： g(邻居) = g(当前节点) + 移动代价 。这里移动代价是 1，所以 g(邻居) = g(S) + 1 = 1 。 * 计算它的 h 值：即该邻居到终点 E 的曼哈顿距离。 * 计算 f(邻居) = g(邻居) + h(邻居) 。 * 将这个邻居节点连同它的 f, g, h 值，以及它的 父节点 （即当前节点 S）一起加入开放列表。记录父节点是为了最后回溯找出完整路径。 * 如果这个邻居 已经在 开放列表中： * 这意味我们之前通过另一条路径到达过这个邻居。现在我们需要检查当前这条新路径是否更好（即 g 值是否更小）。 * 计算一条新的 g_temp 值： g_temp = g(当前节点) + 移动代价 。 * 如果 g_temp < g(邻居) （说明新路径更优），那么： * 更新这个邻居的 g(邻居) = g_temp 。 * 相应地更新 f(邻居) = g(邻居) + h(邻居) 。 * 将这个邻居的父节点 重新指向 当前节点。 d. 重复步骤 a，即再次从开放列表中选取 f(n) 值最小的节点作为新的当前节点。 循环终止条件 ： 成功 ：当终点 E 被加入开放列表，并成为当前节点时，说明路径已经找到。算法结束。 失败 ：如果开放列表为空，意味着已经没有任何节点可以探索，但终点始终未被找到。此时说明从起点无法到达终点。 路径回溯 当算法成功到达终点后，我们通过从终点 E 开始，不断查找每个节点的 父节点 ，一步一步回溯，直到起点 S。这个反向序列就是找到的最短路径（从 S 到 E 的正向序列）。 关键点与启发式函数 启发式函数 h(n) 的选择 ： h(n) 的选择严重影响算法效率。一个更好的启发式函数（即更接近真实代价，但永不超出）能引导算法更快地走向终点。曼哈顿距离适用于只能四方向移动的网格。 可采纳性保证最优解 ：因为 h(n) 从不高估实际代价，所以 A* 算法一定能找到最短路径。如果 h(n) 有时会高估，那么找到的路径可能不是最短的。 Dijkstra 算法是 A* 的特例 ：如果将启发式函数 h(n) 始终设为 0，A* 算法就退变成了 Dijkstra 算法，它只根据已走的距离（g(n)）做决定，虽然也能找到最短路径，但效率通常低于有良好启发式函数的 A* 。