寻路算法
寻路算法核心特性对比总表
算法 | 代价函数 f(n) |
数据结构 | 是否保证最短路径? | 优点 | 缺点 | 搜索行为比喻 |
---|---|---|---|---|---|---|
BFS | (隐含 f(n) = g(n) , 且权值=1) |
队列 | 是 (等权图) | 简单,保证最短路径(步数最少) | 效率低,无方向性,内存消耗大 | 圆形涟漪:均匀地向所有方向扩散 |
DFS | 无(按深度优先) | 栈 | 否 | 内存消耗相对少(仅存储一条路径) | 极易找到非常绕的路径,可能陷入死循环 | 钻探者:一条路走到黑,碰壁再回头 |
Dijkstra | f(n) = g(n) | 优先队列 | 是 (带权图) | 能处理不同权重,保证最短路径(代价最小) | 比BFS/DFS慢,无方向性,探索区域大 | 严谨的实干家:不计方向,只扩展已花费代价最小的点 |
GBFS | f(n) = h(n) | 优先队列 | 否 | 通常非常快,方向性极强 | 贪心,易被误导,结果可能非最优 | 贪婪的冒险家:只看终点方向,直奔而去 |
A* | f(n) = g(n) + h(n) | 优先队列 | 是 (启发函数可采纳时) | 效率与最优性的完美平衡,方向性好 | 启发函数设计影响性能 | 聪明的规划师:平衡已花费代价和未来预期 |
详细分解
1. 广度优先搜索(BFS)
- 核心思想:系统性地、逐层地探索所有可能的路径。
- 数据结构:队列(FIFO)。先进先出的规则保证了先被访问的节点(即离起点更近的节点)会先被扩展。
- 与Dijkstra的关系:在所有边权值都为1的图中,BFS就是Dijkstra算法。因为此时“步数最少”就等于“代价最小”。BFS是Dijkstra在等权图下的一个高效特例实现。
- 适用场景:查找社交网络中的最短关系链、解决迷宫问题(保证最短步数)、网络爬虫等。
2. 深度优先搜索(DFS)
- 核心思想:尽可能深地探索一条路径,直到无法继续再回溯。
- 数据结构:栈(LIFO)。后进先出的规则保证了总是扩展最新发现的节点。
- 与其他算法的关系:DFS与上述寻路算法哲学完全不同。它不追求最优,而是一种暴力穷举策略。在寻路中表现很差,但适用于许多其他问题(如拓扑排序、检测环路、求解数独等)。
- 适用场景:不适合用于典型的最短路径寻路。适用于需要遍历所有可能性的场景,如排列组合、图的连通性检测。
3. Dijkstra 算法
- 核心思想:追求全局最优。它总是确信地选择当前已知的、从起点出发总实际代价最小的节点进行扩展,直到到达终点。
- 代价函数:
f(n) = g(n)
。g(n)
是确切的、累积的历史成本。它完全忽略目标点的位置信息。 - 适用场景:网络路由协议(如OSPF)、地图导航(当不考虑启发式信息时)、任何需要在带权图中找单源最短路径的场景。
4. 贪心最佳优先搜索(GBFS)
- 核心思想:追求局部最优(贪婪)。它总是选择“看起来”离目标最近的点,希望这样能最快到达终点。
- 代价函数:
f(n) = h(n)
。h(n)
是一个启发式函数,是对未来成本的估计(如直线距离)。它完全忽略已经走了多远。 - 适用场景:对路径质量要求不高、但对速度要求极高的场景,或者在大规模地图中快速找到一个“还不错”的初始解。
5. A*(A-Star)算法
- 核心思想:平衡历史成本与未来估计。它不像Dijkstra那样盲目,也不像GBFS那样冲动。它的代价函数是两部分之和。
- 代价函数:
f(n) = g(n) + h(n)
。g(n)
:确保路径的正确性(朝着最短路径的方向努力)。h(n)
:引导搜索的方向性(朝着目标点的方向努力)。
- 关键:如果启发函数
h(n)
是可采纳的(即永远不会高估到达目标的实际代价),则A*保证能找到最短路径。常见的h(n)
有曼哈顿距离、对角线距离、欧几里得距离。 - 适用场景:绝大多数游戏AI的寻路、机器人路径规划。它是实践中最常用、最有效的寻路算法。
直观图示与总结
想象一下在迷宫中寻找出口:
- BFS:你会派出一大群人,手拉手并排向前走,确保不漏掉任何一条近路。稳妥但人力消耗大。
- DFS:你会随机选一条路一直走,走到死胡同就原路返回,再试下一个岔路口。运气好很快,运气差极慢。
- Dijkstra:你有一个精密的计步器。你每到一个路口,就计算从起点到这里的确切步数,然后总是从步数最少的路口继续探索。绝对能找到最短路径,但可能探索了太多死胡同。
- GBFS:你有一个指向终点的指南针。你永远选择指南针指向最准的方向前进。很快就能找到路,但找到的路可能不是最短的,因为你可能被一堵墙挡住,要绕很远。
- A:你既有一个计步器,又有一个指南针。你选择的标准是 “已走步数 + 指南针预估的剩余步数”最小的方向。既能高效地朝向目标,又不会偏离最短路径太远*。
最终建议:在需要寻找最短路径的场合,A* 算法通常是默认的最佳选择。理解其他算法有助于你更深刻地理解A的原理,并在特定约束下(如内存极度受限时考虑IDA,或网格地图中考虑JPS)做出更优的选择。