搜索算法集锦

记录各种经典的搜索算法。

Dijkstra算法

该算法解决了图 ${\displaystyle G=\langle V,E\rangle }$上带权的单源最短路径问题。

A*搜索算法

A搜索算法(A search algorithm)是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或网络游戏的BOT的移动计算上。

该算法综合了BFS和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数)。

RRT*搜索算法

基于随机采样的路径规划算法。这类算法适用于高维度空间,它们以概率完备性(当时间接近无限时一定有解)来代替完备性,从而提高搜索效率。

参考链接

  1. Dijkstra算法,by wikipedia.
  2. A*搜索算法,by wikipedia.
  3. 路径规划 | 图搜索算法:DFS、BFS、GBFS、Dijkstra、A*,by 鬼木士.
  4. 路径规划 | 随机采样算法:PRM、RRT、RRT-Connect、RRT*,by 鬼木士.
  5. 全局路径规划:图搜索算法介绍4(RRT/RRT*),by gophae.