标点符(钱魏 Way)

路径规划常见算法整理

Dijkstra算法

Dijkstra 算法是一种用于计算带权有向图中单源最短路径(SSSP:Single-Source Shortest Path)的算法。其解决的问题是:给定图 G 和源顶点 v,找到从 v 至图中所有顶点的最短路径。Dijkstra 算法采用贪心算法(Greedy Algorithm)范式进行设计。在最短路径问题中,对于带权有向图 G = (V, E),Dijkstra 算法的初始实现版本未使用最小优先队列实现,其时间复杂度为 O(V2),基于 Fibonacci heap 的最小优先队列实现版本,其时间复杂度为 O(E + VlogV)。

相关资料:

Bellman-Ford 算法

Bellman–Ford 算法是求解单源最短路径问题的另外一种算法。它的原理是对图进行V-1次松弛操作,得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达 O(V*E)。

相关资料:

SPFA算法

SPFA(Shortest Path Faster Algorithm)(队列优化)算法是求单源最短路径的一种算法,它还有一个重要的功能是判负环(在差分约束系统中会得以体现),在Bellman-ford算法的基础上加上一个队列优化,减少了冗余的松弛操作,是一种高效的最短路算法。

相关资料:

A*搜索算法

A*搜索算法,俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或网络游戏的BOT的移动计算上。该算法综合了Best-First Search和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数)。

在此算法中,如果以g(n)表示从起点到任意顶点n的实际距离, h(n)表示任意顶点 n到目标顶点的估算距离(根据所采用的评估函数的不同而变化),那么A*算法的估算函数为:f(n)=g(n)+h(n)。这个公式遵循以下特性:

  • 如果 g(n)为0,即只计算任意顶点 n到目标的评估函数h(n),而不计算起点到顶点n的距离,则算法转化为使用贪心策略的Best-First Search,速度最快,但可能得不出最优解;
  • 如果 h(n)不高于实际到目标顶点的距离,则一定可以求出最优解,而且 h(n)越小,需要计算的节点越多,算法效率越低,常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离;
  • 如果 h(n)为0,即只需求出起点到任意顶点n的最短路径 g(n),而不计算任何评估函数h(n),则转化为单源最短路径问题,即Dijkstra算法,此时需要计算最多的定点

参考资料:

Floyd-Warshall算法

Floyd-Warshall算法中文亦称弗洛伊德算法,是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权(但不可存在负权回路)的最短路径问题,同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度为 O(N^3),空间复杂度为O(N^2)。

参考资料:

Johnson算法

Johnson算法主要用于求稀疏图上的所有节点对的最短路径。其主体思想是利用重新赋予权值的方法把一个原问题带负权的图转化为权值非负的图。然后再对每个节点使用一次Dijkstra算法以求出所有节点对的最短路径。时间复杂度; O(VE + V2logV)

参考资料:

Contraction Hierarchies(CH) 分层思想

参考资料:

Highway Hierarchies公路层次查询算法

参考资料:

Customizable Route Planning可定制最短路径

来自微软研究院,目前已经运用到Bing地图的公路导航中。

参考资料:

其他算法:

  • Transit-node routing
  • many-to-many algorithm
打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode
码字很辛苦,转载请注明来自标点符《路径规划常见算法整理》

评论