路径搜索算法整理(一)图搜索篇

本文主要整理各种主流路径搜索算法的帖子。

一、广搜与深搜

参考链接

DFS

利用栈进行搜索，先进后出思路，下图例子按照左枝优先搜索顺序(1,2,4,8,5,3,6,7,9)

BFS

利用队列进行搜索，先进先出思路，遍历完一个节点的所有子节点去掉该节点，然后再遍历子节点的子节点，上图搜索顺序为(1,2,3,4,5,6,7,8,9)

二、Dijkstra算法（迪杰斯特拉算法）

参考链接：

使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。

三、A*搜索

参考链接：

这个链接中有算法动画演示

A *算法原理是从起始节点开始，通过启发函数搜索并选择周围最优节点作为下一个扩展点，不断重复这个操作，直到到达目标点，最终从目标点原路返回到起始点，生成最终路径。

f ( n ) ​

g ( n ) + h ( n ) ​ f (n)​=g (n) +h (n)​

f

(

n

)

​

=

g

(

n

)

h

(

n

)

​

Dijkstra算法即为h(n)=0的A* 算法

伪代码

* 初始化open_set和close_set；
* 将起点加入open_set中，并设置优先级为0（优先级最高）；
* 如果open_set不为空，则从open_set中选取优先级最高的节点n：
    * 如果节点n为终点，则：
        * 从终点开始逐步追踪parent节点，一直达到起点；
        * 返回找到的结果路径，算法结束；
    * 如果节点n不是终点，则：
        * 将节点n从open_set中删除，并加入close_set中；
        * 遍历节点n所有的邻近节点：
            * 如果邻近节点m在close_set中，则：
                * 跳过，选取下一个邻近节点
            * 如果邻近节点m也不在open_set中，则：
                * 设置节点m的parent为节点n
                * 计算节点m的优先级
                * 将节点m加入open_set中

四、D*

Dynamic A Star

它是一种启发式的路径搜索算法，适合面对周围环境未知或者周围环境存在动态变化的场景。同A*算法类似，D-star通过一个维护一个优先队列（OpenList）来对场景中的路径节点进行搜索，所不同的是，D *不是由起始点开始搜索，而是以目标点为起始，通过将目标点置于Openlist中来开始搜索，直到机器人当前位置节点由队列中出队为止（当然如果中间某节点状态有动态改变，需要重新寻路，所以才是一个动态寻路算法）。