简单整理下最近搜集的一些路径规划算法。(都是无负权图)
基础算法
这篇文章总结的很好(http://theory.stanford.edu/~amitp/GameProgramming/)
-
dijkstra 算法 (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
优点：肯定找到最短路径，算法简单
缺点：需要遍历并记录所有节点 -
Astar (A*) 算法 (https://en.wikipedia.org/wiki/A*_search_algorithm)
对dijkastr优化，加入了评价函数f(n)=g(n)+h(n) h(n)为启发函数(heuristic function) 当h(n)=0时就是dijkstra
优点：比dijkstra快，因评价函数存在，算法会放弃掉图的边缘节点
缺点：h函数的选择决定了算法速度 -
Dstar (D*) 算法 (https://en.wikipedia.org/wiki/D*)
动态A* 算法，当图的权值变动时 -
IDAstar (IDA*) 算法 (https://en.wikipedia.org/wiki/IDA*)
对A*算法优化，深度遍历+A*
优点：空间复杂度比A*低
缺点: 会重复计算路网中的节点
业界导航算法
主要是处理大数量的地图路网数据的方法
- Customizable Route Planning (https://research.microsoft.com/pubs/145688/crp-sea.pdf)
- KIT (http://algo2.iti.kit.edu/) contraction hierarchies 和 highway hierarchies
网友评论