A*算法详解：全局与局部择优搜索

"A*算法详解" A*算法是一种在图搜索算法中广泛使用的启发式搜索方法，它在搜索过程中利用估价函数f(n) = g(n) + h(n)，其中g(n)表示从初始节点到当前节点的实际代价，而h(n)是估计从当前节点到目标节点的启发式代价，包含了问题的特性信息。由于这个估价函数，A*算法能够在搜索过程中不断优化路径选择，确保找到最优解。 A*算法的核心在于它每次都会在Open表（待搜索节点集合）中选择估价函数值最小的节点进行扩展。搜索过程分为几个步骤： 1. 将初始节点S0加入Open表，并计算其估价函数f(S0)。 2. 当Open表为空时，说明无解，搜索终止。 3. 取出估价函数最小的节点n，将其加入Closed表（已访问节点），并检查是否达到目标状态。 4. 若节点不可扩展，返回步骤2。 5. 扩展节点n，生成子节点，并计算它们的估价函数，更新指针，并将子节点放入Open表。 6. 对Open表进行排序，确保始终选择估价最小的节点。 7. 重复以上步骤，直至找到目标或Open表为空。 A*算法具有全局择优的特性，因为它始终追求全局最优解。特别地，当估价函数f(n)简化为g(n)时，算法退化为广度优先搜索（BFS），而当f(n)简化为h(n)时，它等同于纯启发式搜索。举例来说，八数码难题（如图5-12所示）可以通过A*算法求解，搜索过程中每个节点的估价函数值代表了到达目标状态的最短路径估计。 局部择优搜索算法与全局择优搜索相对，它可能在某些情况下偏向于局部最优，但无法保证全局最优。A*算法由于其全局优化策略，常用于路径规划、游戏AI等领域，因其高效性和实用性而备受关注。