MENU

寻路算法小汇总: Dijkstra, A*, D*

• 2020 年 05 月 18 日 • 技术

Dijkstra 算法:仅考虑起点

Dijkstra

简介

Dijkstra 算法可以求出由初始点到任意其他点的最短距离以及最短路径。

Dijkstra 算法采用贪心策略,即每次都查找与该点代价最小的点。它是广度优先搜索的一种。它要求图中不存在负权边,或者,对于网格路径查找而言,不存在负的代价值(即每往外探测一个节点,都会增加这个路径的“代价”)。其时间复杂度为 O(n2)。

逻辑

首先考虑不保存路径的简单情况(即只考虑“由初始点到任意其他点的最短距离”这一情况)。

我们仅需两组集合——openlist 和 clostlist 来存储点信息,每一个点信息为具体点和其到起始点的代价。close 为已求出最短路径的点集合,open 为其余未确定最短路径的点集合。这两个组互不重叠,共同组成了所有的点。初始时,close 仅有起始点一个元素,open 为其余的所有点,点若与起始点连通,则距离存在,否则为无穷大。其后,将 open 内的距离最小的一个点移入 close,并利用新点的对外连通信息更新 open——若新点所带来的新连通信息可以让 open 内的点元素到起始点的距离缩短则刷新成新的代价,否则保持原样。之后再按此逻辑再从 open 选取点移入 close,直至 open 不含元素。此时 close 内每一个元素的离起始点的代价即为所求。

请注意上文的代价。通常而言可以以距离来理解。例如在图中,每个节点之间边的权即为距离。但在 Grid 图中,这个代价除了单纯的几何距离,也可以再叠加地形代价等,例如某一个点理解为沼泽地,那么它与最近的点的几何距离为1,但是地形代价为2(正常地形为0),那么它的代价就为3。绕行此地形点可能可以取得更小的总代价,即使在几何上不最短。

所以可以明确,假如为 Grid 图,且每个节点之间的代价就为几何距离(而不考虑地形代价等),那么 Dijkstra 算法与广度优先搜索无异

接下来来考虑保存路径的情况。

每一个节点都是由之前的节点来访问或更新的,那么就可以认为父节点指向下一个节点,即每一个节点都有其父节点。那么具体的路径就可以从终点反推出parent节点,一步一步地回溯到起点。

所以只要在每次访问新节点或者刷新出更小代价的时候,记录或者更新每一个节点的父节点,在算法执行完后,从终点根据父节点即可回溯到起点,之后再倒序输出即可。

A* 算法:同时考虑起点终点

A*

简介

A* 算法常用于求解静态路网中的最短路径、网格地图避障最短路径等。

A* 算法结合了 BFS 算法以及 Dijkstra 算法的思路与特点,它与 Dijkstra 算法很大的一个不同是,处理过程中,选取的节点会受到与终点的位置关系(距离等)的影响,即评估。这一个特性可以大大减少不需要的搜索,提高寻路效率。

A* 算法使用如下来计算代价或优先级。代价越小,即优先级越高。

f(n)=g(n)+h(n)
  • f(n) 是节点n的综合优先级。当我们选择下一个要遍历的节点时,我们总会选取综合优先级最高(值最小)的节点。
  • g(n) 是节点n距离起点的代价,通常即为。
  • h(n) 是节点n距离终点的预计代价,这也就是A*算法的启发函数。

其核心即为启发函数h(n)

  1. 倘若h(n)恒为0,即不启用启发函数来影响选取节点,此时的 A* 算法实际上就是上文的 Dijkstra 算法(因为其没有考虑终点位置)。
  2. 倘若h(n)为节点到终点确定代价,那么就可以最快的速度来找到确切路径。但是这是比较难的,因为h(n)预计,路上可能会有障碍物等等。
  3. 倘若h(n)恒小于等于实际的代价,那么 A* 算法就一定能找到最短的路径,但是h(n)与实际的误差越大,其就会访问更多的节点,耗时也就++。
  4. 倘若h(n)恒大于实际的代价,那么 A* 算法就不一定能找到最短的路径了,不过速度会较快。

通常采用的启发函数为各种距离。例如

  1. 曼哈顿距离:当前点到终点的横、纵坐标的差的绝对值的和。通常运用于上下左右移动时。
  2. 欧式距离:即两点直线距离。通常用于可任意方向移动时(例如直升机)。
  3. 对角距离:即在曼哈顿距离的基础上再增加可斜对角移动的条件,并响应更改距离。

逻辑

如上文所示,A* 算法在处理时的核心在于 openlist(还需要关注的,随时可能再被抽出来访问的)、closelist(无需再关注的)。首先将起点设为 cur 并加入 open,然后再向四周(例如:上下左右)访问安全的节点(不是障碍或者膨胀障碍),并且在访问的时候将访问到的节点的父节点设为起点(即这些节点是由父节点所请求访问的),并将这些节点和其对应的f、g、h信息加入 open 里面。

接下来将 cur 从 open 内移除并转入 close,然后在 open 中选 f 最小,即代价最小的节点,再按上文所示向四周访问(不在 close(倘若已在 close 则略过) 且不是障碍或者膨胀障碍)并记录父节点。请注意,倘若已在 open 里则看看由 cur 到那个节点的 f 能否更小,能则刷新,否则略过。

倘若在访问周边节点时访问到了终点则寻路成功。如果出现了 open 为空的情况则寻路结束且没有路径。

之后再按照和 Dijkstra 算法相同的方式,通过父节点信息,从终点反推即可。

D* 算法:动态最短路径,局部修正路径

简介

D* 是Dynamic A* 即动态 A* 的简写,其算法和A*类似。其主要区别则在于 D* 算法会在运算时动态地调整代价的计算方式,在应对动态地图、增量地图等条件下表现优秀。

D* 算法的核心优势在于,它可能会遇到地图改变的问题(或者实际地图与假设地图不同的情况),而立即局部修正路线的效率较上者两个更高。

因此,D 算法核心在于假设,假设没有探测到的位置为某一环境(例如畅通),并基于假设以及每次观察到的信息后进行的对变化地图区块的新路线修正来找到尽可能短的路径。即 Real-Time Replanning in Dynamic and Unknown Environments 为对 D 算法最好的诠释。

A*是正向搜索,而D* 特点是反向搜索,即从终点开始搜索过程。在初次遍历时候,与 Dijkstra 算法一致,它将每个节点的信息都保存下来。

D* 包含了下面三种增量搜索算法:

  • 原始的D*由Anthony Stentz发表。
  • Focussed D由Anthony Stentz发表,是一个增量启发式搜索算法,结合了A和原始D*的思想。
  • D Lite是由Sven Koenig和Maxim Likhachev基于LPA构建的算法。

逻辑

先在静态的情况下,假设环境畅通,来用 A* 等算法从终点开始找到一个最优路径,并记录每个节点的子节点——为什么要从终点开始的缘故。

之后机器人开始按照路径行走探测,当路径上遇到障碍的时候,将节点放入 open,重新修正局部路径。

在思考如何修正路径之前,再补充一些概念:

在 A* 算法的 close open 等前提不变的情况下,h为到终点代价,k为该点最小的h值。请注意,k 值用于 D* 算法中 openlist 的排序依据

为什么要用 k 来作为排序依据呢,原因在于 k 值的存在可以表明这里曾有一段短路径,即与外界的连通路径而言更加紧密。这样就可以在修正的时候,优先在此处附近搜索,并由此往外扩散,从而尽可能减少搜索次数。

在遇到障碍后,将障碍 h 设大(因为确实代价变大了),然后向外搜索(此点和周围点加入 open)。这个搜索的过程实际上就是 RAISE 态的传播(因为 h>k 了),它需要一直传播直到新节点的加入能使其变为 LOWER 态(h=k),在 open 里面的节点都已经无法再降低代价,即“绕”开了障碍重新找到了路。

总结

Dijkstra 和 A* 算法都是优秀的静态路径搜索,我们在这里不考虑它们路径变化之后“刷新”路径的效率。它们都是对于完全已知的地图的一种寻路算法,不适用于动态地图(增量地图),因为重新规划的效率太低。

Dijkstra 算法所认为的代价为到起始点的代价。在无特殊地形的地图上(即每个相邻点代价相同)基本可以等价于广度优先搜索,而在有权图等相邻节点间代价不同的地图上,则会优先探测(贪心)代价低的节点。这的确有利于探测出最短路径,但是不利于高效率探测到结束点的路径。因为 Dijkstra 算法在探测的时候不会考虑结束点位置的影响(不将当前点和结束点之间以代价的方式表现出来并作为排序权重)。

而 A 算法在 Dijkstra 算法的基础上,不仅仅计算到起始点的代价,更计算到终点的预计代价,并作为排序依据。因此 A 算法便可基于终点的位置,更好地有针对性地探测新节点,可以更高效率地探测。

Dijkstra 算法建立在较为抽象的图论层面,更常用于有权图等的搜索即某一点到任意点的最短路径等问题的处理,而A* 算法可以更常用于地图寻路等网格地图中。

请注意,由于 A* 算法要算两个代价,所以用到的数据较多。因此,当目标点很多时,若不要求获得具体路径而只比较路径长度时,Dijkstra 算法会更好——也更易懂。

而 D 算法则着重用于地图变化*,或动态路径搜索的情况,它可以在第一次探测完后,针对部分地图区域的障碍物信息变更等情况,做出更快的修正行为。但请注意:在障碍物信息发生变化后找到的路径,不一定是一条最短的路径——但是效率高就可以了,不是么?

最后编辑于: 2020 年 07 月 24 日
返回文章列表 文章二维码
本页链接的二维码
打赏二维码