一、路径搜索算法

1. 深度优先搜索(DFS)

深度优先，顾名思义即深度越大的节点会被优先扩展。在DFS中，使用栈(Stack)数据结构来实现上述特性。DFS能够快速地找到一条路径，是一种以时间换空间的方法。将其应用到二维地图的路径规划中。

2. 广度优先搜索(BFS)

与DFS的“不撞南墙不回头”的个性不同，BFS在搜索时呈波状推进形式，一路稳扎稳打，它是一种以时间换空间的方法，能够保证搜索到的路径是优异的。为了实现波状推进搜索特性，BFS采用队列(Queue)作为openlist的数据结构。队列是一种先进先出(FIFO)的容器，相较于DFS，BFS中使用了大量的入队、出队操作，耗时增加，但是能保证找到优异路径。

3. 广度优先搜索(BFS)

启发式搜索算法(Heuristic Algorithm)就是用来解决搜索效率问题的，GBFS也是图搜索算法的一种，它的算法流程和BFS、DFS并没有本质的不同，区别仍然在于openlist采用的数据结构，GBFS使用的是优先队列(Priority Queue)，普通队列是一种先进先出的数据结构，而在优先队列中元素被赋予了优先级，较高优先级元素优先删除，也就是first in, largest out。(记住这种数据结构，后面的Dijkstra和A*算法都会用到这个结构)。

4. Dijkstra算法

Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，其流程仍然与上述算法基本一致，它也是用优先队列作为openlist的数据结构，它和GBFS的区别在于代价函数的定义。首先扩展名列前茅个节点，计算其余节点与名列前茅个节点的距离，用橙色标出已经扩展的节点，未扩展的节点仍用绿色标出，其中圆中的数值表示该节点的代价函数，字母则表示该节点没有直接到达此时已扩展节点的路径。从未扩展的节点(绿色节点)中选择代价函数最小的节点进行拓展，并更新其余节点的代价函数。

5. A*算法

对比GBFS和Dijkstra算法，两者都采用优先队列作为openlist，而代价函数的不同导致两者具有不同的优点：GBFS用节点到目标点的距离作为代价函数，将搜索方向引向目标点，搜索效率高；而Dijkstra算法采用起点到当前扩展节点的移动代价作为代价函数，能够确保路径优异。

那么可不可以将两者的代价函数进行融合，从而在保证路径优异的同时提高搜索效率？答案是肯定的，融合后的算法就是A*算法。

延伸阅读：

二、图结构

图结构是一种由数据元素集合及元素间的关系集合组成的非线性数据结构。数据元素用节点(node)表示，元素间的关系用边(edge)表示，如果两个元素相关，就用一条边将相应的节点连接起来，这两个节点称为相邻节点。根据边的方向性，可以分为无向图和有向图。

以上就是关于路径搜索算法的内容希望对大家有帮助。

上一篇

什么是托管安全服务 (MSS)?

下一篇

计算机网络的拓扑结构有哪些?