当前位置: 首页 > news >正文

寻路算法

寻路算法

寻路算法核心特性对比总表

算法 代价函数 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)做出更优的选择。

http://www.hskmm.com/?act=detail&tid=13740

相关文章:

  • 2025年9月22日 - 20243867孙堃2405
  • day 1
  • [Paper Reading] METAGPT: META PROGRAMMING FOR A MULTI-AGENT COLLABORATIVE FRAMEWORK
  • 二进制 - 20243867孙堃2405
  • 学习问题日记-1
  • 记一次生产环境内存溢出记录
  • 四舍六入五成双
  • 借助 Apache Phoenix,使用标准 SQL 和 JDBC 接口来操作 HBase
  • 学生信息管理系统
  • 如何让AI生成多页面APP原型图?AI原型设计实用指南
  • 代码随想录算法训练营第五天 | leetcode 242 349 202 1
  • CF2146 Codeforces Round 1052 (Div. 2) 游记
  • 原码补码反码与位操作
  • 接口
  • 特殊句式
  • 9月22日
  • 20250922
  • 易路斩获招聘、薪酬两大重磅人力资源奖项,尽显行业领军风范!
  • 作业
  • RAG系统嵌入模型怎么选?选型策略和踩坑指南
  • (应该写的比较清晰)D2. Max Sum OR (Hard Version)
  • Linux运维
  • day001
  • 第一次编程作业
  • 7
  • Xilnx FPGA 资源结构
  • 2025年录音转文字技术解析与实用工具评测 - 指南
  • CF2147H Maxflow GCD Coloring 题解
  • Uiverse.io 2.0 震撼发布:新增 3000+ 动效组件!适配 React、Vue
  • 问题及解决方法