记录各种经典的搜索算法。
Dijkstra算法
该算法解决了图 ${\displaystyle G=\langle V,E\rangle }$上带权的单源最短路径问题。
A*搜索算法
A搜索算法(A search algorithm)是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或网络游戏的BOT的移动计算上。
该算法综合了BFS和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数)。
RRT*搜索算法
基于随机采样的路径规划算法。这类算法适用于高维度空间,它们以概率完备性(当时间接近无限时一定有解)来代替完备性,从而提高搜索效率。
参考链接
- Dijkstra算法,by wikipedia.
- A*搜索算法,by wikipedia.
- 路径规划 | 图搜索算法:DFS、BFS、GBFS、Dijkstra、A*,by 鬼木士.
- 路径规划 | 随机采样算法:PRM、RRT、RRT-Connect、RRT*,by 鬼木士.
- 全局路径规划:图搜索算法介绍4(RRT/RRT*),by gophae.