A* 算法

#A* 算法

• 什么是 A* 算法
• 与狄克斯特拉的区别
• 距离估算值
• 操作步骤
• 应用场景

#什么是 A* 算法

A*（A-Star）算法由狄克斯特拉算法发展而来，用于在加权图中求最短路径。狄克斯特拉会计算所有方向的最短路径（包括远离终点的方向），浪费了很多计算。A* 通过一个估算值引导搜索方向朝向终点，省去无用计算。

#与狄克斯特拉的区别

狄克斯特拉算法:                   A* 算法:
  只考虑「从起点到当前节点的距离」   还考虑「从当前节点到终点的估算距离」

  4  3  2                          4  3  2
  5     1     ← 大部分区域被搜索     只搜索朝向终点的区域
  6  5  4  3  4  5  6  7
  7  6  5  4  3  2  1              效率高得多！
  S          G                     S    →    G

#距离估算值

A* 的核心是距离估算值——一个由人工设定的、从当前节点到终点的大致距离。

每个节点的权重 = 实际距离（从起点到该节点）+ 估算距离（该节点到终点）

估算距离可以自由设定，常用的是：

• 曼哈顿距离：|x₁-x₂| + |y₁-y₂|（适合网格移动）
• 欧几里得距离：直线距离（适合自由移动）

距离估算值≤实际距离时，A* 一定能得到正确答案。估算值越接近实际值，效率越高。

#操作步骤

1. 从起点开始，计算周围每个邻居的权重 = 实际距离 + 估算距离
2. 选择权重最小的节点，标记为已搜索
3. 计算新搜索节点的邻居权重
4. 重复选择权重最小的节点并搜索，直到到达终点

迷宫示例（数字 = 实际距离 + 估算距离）:

  8  7  8          A* 只搜索朝向终点的区域
  7  S  6  5        S = 起点，G = 终点
  6  5  4  3  2
           1  G

  → 效率比狄克斯特拉高很多

#应用场景

• 游戏寻路：计算敌人追赶玩家的行动路线（A* 是游戏 AI 寻路的标准算法）
• GPS 导航：结合地图信息估算距离，快速规划路线
• 机器人路径规划：在障碍物中找到最短路径

#小结

• A* = 狄克斯特拉 + 距离估算值（启发式信息）
• 权重 = 实际距离 + 估算距离，引导搜索朝向终点
• 估算值≤实际距离时保证正确
• 估算值越准确，效率越高；如果不准确，可能比狄克斯特拉还慢
• 游戏寻路和 GPS 导航的标准算法