路径规划算法 [2D 模拟：A*、Dijkstra、GBFS]

Source: Dev.to

在为自动导航系统选择路径寻找算法时，最关键的权衡是什么？

我测试的三种算法

我使用 Python 和 Pygame 实现了三种经典算法：

1. Dijkstra 算法

• 在所有方向上均匀探索
• 保证绝对最短路径
• 非常慢；会探索成千上万个节点
• 最佳使用场景： 离线规划

2. A*

• 使用启发式函数引导搜索朝向目标
• 找到最短路径，速度比 Dijkstra 快 80‑90 %
• 需要一个好的启发式函数才能发挥最佳性能
• 最佳使用场景： 实际导航（Google Maps、Waze）、视频游戏、机器人

3. 贪婪最佳优先搜索（Greedy Best‑First Search）

• 仅凭启发式函数直接冲向目标
• 计算速度极快
• 往往会得到更长、次优的路径
• 最佳使用场景： 简单视频游戏、快速原型开发、对“足够好”即可的情况

速度‑最优性的权衡

测试数据展示了一个清晰的模式：

你不可能同时拥有闪电般的速度和始终完美的结果。请根据具体使用场景决定哪一点更重要。

它们在不同环境中的表现

我在两个模拟环境中测试了所有三种算法。

环境 1：经典网格

• GBFS 路径长度：114
• A* 路径长度：94（Greedy 的路径仅长 21 %）

环境 2：不规则网格

• GBFS 路径长度：196
• A* 路径长度：122（Greedy 的路径长 57 %）

在第一个环境中，GBFS 的表现还能接受；在第二个环境中则彻底失效。一个在某环境中表现尚可的算法，可能在另一环境中完全崩溃。

用户真正想要的是什么

对 64 位受访者的调查显示了 GPS 使用的优先级：

• 50 % 希望走最快的路线，即使路线复杂。
• 25 % 希望走最简洁的路线，即使更慢。

在迷宫寻找问题中：

• 32.8 % 会直接猜测出口方向（类似启发式算法 A* 与 Greedy）。
• 29.7 % 会有条不紊地探索并记住已走过的路径（类似 Dijkstra）。

人们自然会采用与算法相同的策略：速度 vs. 确定性。

哪种算法最合适？

• Dijkstra： 当你必须保证最短路径且时间不敏感时选择。
• A*： 适用于需要快速且可靠路径的情况。
• Greedy： 当速度比路径质量更重要时选择。

结论

总体而言，A* 是最稳健的算法。它在所有环境中始终能找到最优路径，同时保持可接受的计算成本。Greedy 虽然快，但在复杂环境下的可靠性会崩溃。Dijkstra 虽可靠，却对实时应用来说过于缓慢。