图搜索算法学习

本文将从图搜索算法的基本流程入手，层层递进地介绍几种图搜索算法。首先是两种针对无权图的基本图搜索算法：深度优先搜索(Depth First Search, DFS)**、广度优先搜索(Breadth First Search, BFS)。它们的区别在于 openlist(后面介绍)所选用的数据结构类型不同，前者使用栈，后者使用队列；之后引入一种启发式搜索算法：贪婪最佳优先算法*(Greedy Best First Search, GBFS)，用来提高搜索效率，但是不能确保找到最优路径；最后介绍两种在路径规划中非常经典的算法：Dijkstra 算法、**A\算法**，前者是广度优先算法(BFS)在带权图中的扩展，后者则是在前者中加入启发函数得到的算法，兼顾效率和完备性。

基本流程

下面切入正题，图搜索算法的基本流程如下：

• 创建一个容器，一般称为openlist，用来存储将要访问的节点
• 将起点加入容器
• 开始循环：
• —- 弹出：从容器中取出一个节点
• —- 扩展：获取该节点周围的节点，将这些节点放入容器

作者：鬼木士链接：https://zhuanlan.zhihu.com/p/346666812来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

图结构的邻接矩阵表示法

邻接矩阵用来表示图的边集，即节点间的相邻关系集合。设 是一个具有 n 个节点的图，它的邻接矩阵是一个 n 阶矩阵，则其中的元素 满足：

对于无向图，其邻接矩阵是对称矩阵，即 ，而有向图的邻接矩阵不一定对称，其空间复杂度均为 。以下为两个不带权图的邻接矩阵示例：

对于带权图，设 或者 上的权值为 ，则带权图的邻接矩阵定义为：

以下为两个带权图的邻接矩阵示例：

深度优先搜索(DFS)

深度优先，顾名思义即深度越大的节点会被优先扩展。在 DFS 中，使用栈(Stack)**数据结构来实现上述特性。
栈是一种后进先出(LIFO)的容器，如下图

以在下面的无权图**中找到从节点 a 到节点 i 的路径为例，说明一下 DFS 算法的工作流程

按照上节的图搜索算法的基本流程进行搜索，过程如下：

从 i 回溯得到路径：a->b->c->g->i，如下：

广度优先搜索(BFS)

与 DFS 的“不撞南墙不回头”的个性不同，BFS 在搜索时呈波状推进形式，一路稳扎稳打，它是一种以时间换空间的方法，能够保证搜索到的路径是最优的。
为了实现波状推进搜索特性，BFS 采用队列(Queue)**作为 openlist 的数据结构。队列是一种先进先出(FIFO)**的容器，如下图

其流程与上节中 DFS 类似，继续以上节的图举例，过程如下，首先创建一个队列作为容器，将节点 a 加入队列

接着将节点 a 弹出队列，将节点 a 周围没有访问过的节点加入队列

按照上面的流程不断地弹出、扩展节点，直到找到节点 i 为止，完整流程如下图：

从终点回溯，i 的父节点为 f，f 的父节点为 e，e 的父节点为 a，这样就可以得到 a 到 i 的最短路径为：a->e->f->i，如下

显而易见，相较于 DFS，BFS 中使用了大量的入队、出队操作，耗时增加，但是能保证找到最优路径。

Dijkstra 算法

上面的算法中，只有广度优先搜索(BFS)具有完备性，能够保证搜索到最优路径。但是可以看到 BFS 算法搜索到的路径只有向上/下/左/右移动这四个动作，它们是没有权值或者说权值都相同的，只能用于无权图的路径规划，无法实现能够对角移动的路径规划。因此下面介绍一种能用于带权图的图搜索算法——Dijkstra 算法(狄克斯特拉算法)。
Dijkstra 算法是从一个顶点到其余各顶点的最短路径算法，其流程仍然与上述算法基本一致，它也是用优先队列作为 openlist 的数据结构，它和 GBFS 的区别在于代价函数的定义，Dijkstra 算的定义为：

其中表示从起点到当前点的移动代价。
作者：鬼木士链接：https://zhuanlan.zhihu.com/p/346666812来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
以下图为例，计算起点 a 到终点 i 的最短路径，箭头上的数值表示两个节点间的距离

首先扩展第一个节点，计算其余节点与第一个节点的距离，用橙色标出已经扩展的节点，未扩展的节点仍用绿色标出，其中圆中的数值表示该节点的代价函数，字母则表示该节点没有直接到达此时已扩展节点的路径。从未扩展的节点(绿色节点)中选择代价函数最小的节点进行拓展，并更新其余节点的代价函数，如下图

重复进行上面的步骤，直到所有节点都已扩展。

最后标出起点到终点的最短路径

A*算法

对比 GBFS 和 Dijkstra 算法，两者都采用优先队列作为 openlist，而代价函数的不同导致两者具有不同的优点：GBFS 用节点到目标点的距离作为代价函数，将搜索方向引向目标点，搜索效率高；而 Dijkstra 算法采用起点到当前扩展节点的移动代价作为代价函数，能够确保路径最优。
那么可不可以将两者的代价函数进行融合，从而在保证路径最优的同时提高搜索效率？答案是肯定的，融合后的算法就是A*算法。
A算法也是一种启发式算法，它的代价函数表示为：

其中 为起点到当前扩展节点的移动代价函数， 是启发函数，用节点到目标点的距离函数来表示。
根据这个式子，可以得到 A算法的几个特点：

• 如果令 ，A算法就退化为 Dijkstra 算法；如果令 _，_A算法就退化为 GBFS 算法。
• 能否找到最优路径的关键是启发函数 的选取，如果 在大部分情况下比从当前节点到目标点的移动代价小，则能找到最优路径。
• 由于 A* 算法的启发函数是位置上的距离，因此在不带位置信息的图数据中不适用。