Dijkstra 与 A* 寻路

问题

在一张网格地图上，从绿色起点走到红色终点，绕过黑色障碍。要找步数最少的路径。这是导航软件、游戏 AI、机器人路径规划最基础的问题。

Dijkstra：等距扩散

1948 年 Edsger Dijkstra 提出。核心想法：

从起点开始，像水波一样逐层扩散。第 k 步访问的所有格子，离起点恰好 k 步。

实现细节：用优先队列保证每次取出”目前已知距离最小的格子”，然后把它的邻居更新进队列。

特点：

• 保证最短路（找到的就是最优解）
• 没有方向感：起点附近所有方向都扩展，浪费很多探索
• 在演示中你会看到紫色”水波”四面八方扩散，连远离终点的方向也访问了

复杂度 $O(E \log V)$。

A*：带启发式的 Dijkstra

1968 年 Peter Hart 等人提出。核心想法：

不只看”已经走了多远”（g），还估计”还要走多远”（h）。优先扩展 f = g + h 最小的格子，即”看起来最有希望的方向”。

启发函数 h 通常用曼哈顿距离（网格上 |dx| + |dy|）或欧氏距离。只要 h 不高估真实剩余距离，A* 仍能找到最优路径，但访问的格子数大幅减少。

特点：

• 同样保证最短路（当 h 是”可接受的”）
• 朝目标方向”瞄准”扩展
• 在演示中你会看到紫色区域明显偏向终点

在演示里对比

试这个场景：起点和终点之间没有任何墙。

算法	访问格子	路径长度
Dijkstra	~600	33
A*	~35	33

A* 几乎只访问起点到终点的”直线带”。复杂场景（绕过迷宫）差距会缩小，但 A* 仍然显著优于纯 Dijkstra。

现实应用

• 游戏 AI：暗黑 / 文明 / RTS 单位的移动路径，几乎都用 A*
• 地图导航：高德百度的路径规划本质是大规模 A*（实际上更复杂的”分层”算法 + 实时路况）
• 机器人：扫地机的覆盖路径、自动驾驶的避障，都是这类思路
• NetHack / Roguelike：经典文字 RPG 的怪物追踪也是 A*

启发函数的选择

• $h = 0$ → A* 退化为 Dijkstra
• $h =$ 真实距离 → A* “走直线”
• $h >$ 真实距离 → 速度更快但可能找到次优路径

实际工程里 h 函数的设计是艺术：太松（接近 0）慢，太紧（接近真实）有时反而不优。