各类寻路算法记录

yyctt · 发表于 2024-7-15 18:33

常见的寻路算法

深度优先，广度优先，迭代加深，双向广度优先，A*, IDA*, JPS等。
寻路算法便是图的搜索。
寻路算法分为启发式和盲目式

一片空地，你要从A走到B，假设两种情况：
假设你看不见，你运气差的话，可能需要走完整片空地才能达到B点，这就是盲目式搜索，即使知道方针点，也可能走走完整个地图。
假设你能看见，即你可以看到B点，那只需要向着B的标的目的走就可以，而不会向B相反的标的目的走，这就是启发式搜索。
BFS,DFS是盲目式的，A*,IDA*,JPS则是启发式的。
图

图的概念不赘述，百度就行

图搜索的基本框架

维护一个容器存储所有要访谒的节点
初始化容器
循环
- 移除：计算节点的值，弹出最低的节点（访谒该节点）
- 扩展：获取该节点的所有邻居节点
- 存储：所有邻居节点存入容器
结束

BFS和DFS

两个算法的区别主要在于维护的容器分歧
BFS维护的是一个队列，“先进先出”, 总是访谒容器中最先进入的元素。
DFS维护的是一个栈，“后进先出”，总是访谒容器中最后一个进入的元素。

BFS和DFS对比

图中可以看到两种算法都可以找到一条从起点到终点的路径，DFS显然不是最短路径，BFS扩展点后回溯出来的的路径是最短路径，Dijkstra和A*都是基于BFS。

贪心最佳优先算法（Greedy Best First Search）

贪心最佳优先算法是一种贪心算法，BFS和DFS只是按照First in/Last in来选择下一个点，Greedy BFS是按照某些法则来选择，称之为启发式。
对于任意一个启发函数：

能够指引向着方针更近的标的目的前进。
容易计算，能满足实时性要求。

一般选择欧氏距离或者曼哈顿距离来作为启发。
对比BFS和GBFS

无障碍的情况下，GBFS的搜索速度更快，且两种算法都能找到最短路径。

在有障碍的情况下，GBFS因为过分贪心地想尽快接近方针点，导致得到的路径并不是最优解

GBFS并不是最优的算法，但它所使用的启发式思想可以借鉴。
A*算法就是在Dijsktra上插手了启发式思想。
Dijkstra

迪杰斯特拉算法是一种广为人知的最短路径算法，下面叫做Dijkstra。
Dijsktra和BFS的本质区别在于BFS是按照酬报预先定义好的挨次访谒容器中的节点，而Dijsktra是访谒当前容器中累计成本最低的节点，累计成本为g(n)。
g(n)是从起始节点到节点n的累计成本的当前最佳估计。

Dijkstra算法可以保证它访谒的节点是当前时刻容器中代价最小的节点，因此保证了算法的完备性。
伪代码：

维护一个优先队列来存储所有的节点，按g(n)从小到大进行摆列。
用初始状态Xs来初始化队列。
令g(Xs) = 0，其他节点g(n) = 9999
循环：
- 如果队列为空，返回False，跳出循环。
- 从优先队列中移除最低代价节点n。
- 标识表记标帜节点n已访谒。
- 如果节点n是方针节点，返回True，跳出循环。
- 遍历节点n的所有未访谒的邻居节点m，如果g(m)为9999，g(m) = g(n) + Cnm，将m放入队列。如果g(m) > g(n) + Cnm, 则令g(m) = g(n) + Cnm。
- 结束
结束循环

Dijkstra长处

可以保证得到的节点必然是从起点开始到当前的最小代价的路径，因此按照这一原则进行搜索，当发现方针节点后，回溯出的路径必然是最小代价的路径，即保证算法的完备性。
Dijkstra错误谬误

Dijkstra不知道方针节点位置，只能保证每一步得到的节点累计代价g(n)是最小的，它必需要向所有标的目的扩展，目的性不强，导致算法的效率也不高。

A*

A*算法在机器人、导航、游戏等范围有广泛的应用。A*可以说是Dijkstra的改良版，目的在于解决Dijkstra效率低的问题，上面说到Dijkstra不知道方针节点的位置，所以只能向所有标的目的扩展直到发现方针节点。之前提到的GBFS算法的错误谬误在于，过分存眷方针点的位置，即GBFS每次访谒的节点具有到方针节点的最小代价，但是在有障碍物的情况下路径不是最优解。
两者取长补短，诞生了A*算法，A*同时借鉴了两种算法，在Dijkstra基础上引入了启发式函数h(n)， h(n)暗示了当前节点到方针节点的成本。保证了最优性的同时，插手了方针节点的信息，提升了效率。
g(n): 对从初始节点到节点n的累计成本的当前最佳估计。
h(n): 节点n到方针节点的代价估计（即方针代价）。
f(n) = g(n) + h(n) ：从初始节点，通过当前节点n，再到方针节点的代价估计。
策略：每次访谒容器中f(n)最小的节点
伪代码跟上面Dijkstra 的一样，只不外下一节点变成了f(n)最低的节点。

A*具有完备性的条件如下

当h(n)<= h*(n)时，这里h*(n)指节点n到方针节点的真实代价。
关于h(n)的两种取法：欧氏距离和曼哈顿距离，是否满足A*的最优性。
上图中红色为真实代价h*(n)，黑色为欧氏距离作为h(n)的估计代价，黄色是采用曼哈顿距离作为h(n)的估计代价。显然，采用欧氏距离，必然满足h(n)<=h*(n)
当只考虑上下摆布四格标的目的时，曼哈顿距离满足h(n) <= h*(n)，若可沿对角线移动，曼哈顿距离不必然满足。
Dijkstra和A*对比

总的来说，A*是一个带有启发性的Dijkstra算法。

当h(n) = 0时，即f(n) = g(n)， A*就退化为Dijkstra。
当h(n) <h*(n)时，A*可以找到最短路径，但是搜索效率低，h(n)越小，意味着需要扩展的中间节点越多，效率越低，但是精度更准确，因为此时更趋近于Dijkstra算法。
当h(n) = h*(n)时，可以兼顾精度和速度，是最优状态。
当h(n) >> g(n)时，那么f(n)主要取决于h(n) ,此时A*退化为GBFS。

A*的优化

欧氏距离：

上图是采用欧氏距离作为h(n)的A*路径，过程中扩展了很多没必要的节点。原因是欧氏距离计算的h(n) << h*(n),此时h(n)会引导扩展很多不必要的节点。实际上，对于无障碍下的真实方针代价h(n)是闭式解的。
闭式解：
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
h = (dx + dy) + (根2 - 2）* min(dx, dy)

<hr/>

途中两点A，B具有不异的f(n)，即f(A) = f(B),此时A*不具有倾向性，它会依次分袂扩展两个节点，导致计算浪费在扩展无用节点上。
针对这种情况，我们可以考虑打破对称，让A*算法具有某种倾向性，来减少无用节点的扩展。最简单的做法是将h(n)值略微放大，这样做大大都情况下没问题，因为真实环境中有很多障碍物，h一般远远小于h*，所以略微放大一些不会很大地影响算法的完备性。
h = h * (1.0 + p)
p < 走一步的最小代价 / 预期最大路径消耗
除此之外，也可以倾向选择离起点终点连线距离更近的节点：
dx1 = abs(node.x - goal.x)
dy1 = abs(node.y - goal.y)
dx2 = abs(start.x - goal.x)
dy2 = abs(start.y - goal.y)
cross = abs(dx1 * dy2 - dx2*dy1)
h = h+cross*0.001
总之，新思路是打破平衡性，增强A*的目的性。

IDA*

上面提到A*和Dijkstra算法是在BFS基础上改良而来的，IDA*则是在DFS思想上改良而来的。
IDA*采用迭代加深的A*算法，由于采用了深度优先方式，所以：
不需要判重，不需要排序；
空间需求减少。
法式

设定一个较小的深度作为全局变量，进行DFS。
每进入一次DFS，当前深度+1，如果发现深度大于设定的深度limit，返回。
如果搜索途中发现了方针节点，回溯得到路径。
如果没发现方针节点，返回入口，增加深度，反复上述法式。

长处

使用回溯方式，不用保留中间状态，节省空间。
错误谬误

反复搜索：每次深度d变大，都要从头开始从头搜索。
迭代加深搜索：

迭代加深搜索是一次每次限制搜索深度的深度优先搜索。
本质是DFS，不外搜索同时带了一个深度d，当d达到设定的limit时返回，用于寻找最优解。如果一次没有找到合法的最优解，则d++，需要从头开始从头搜索。
不用BFS原因是BFS以队列为基础，队列的空间复杂度非常大，当状态斗劲多或者单个状态斗劲大时，BFS算法有必然劣势，迭代加深可以看感化DFS的方式实现BFS，空间复杂度相对较小。
当搜索树的分支斗劲多，深度每增加1搜索复杂度就会指数级增长，这是前面反复进行的部门所带来的复杂度，几乎可以忽略，因此迭代加深可以近似看作BFS。
Jump Point Search(JPS)

JPS算法又叫跳点搜索算法，在保留A*算法框架的同时，进一步优化了A*寻找后继节点的操作。
以下数据来自网络
假设场景起点终点差距200格子，需要寻路10000次。
A*寻路总时间为2.6074 x 10^11 ns
基础JPS寻路总时间为1.7037 x 10^10 ns
操作位运算优化的JPS（JPS-Bit)寻路总时间为3.2363 x 10^9 ns
操作位运算和剪枝优化的JPS（JPS-BitPrune)寻路总时间为2.0043 x 10^9 ns
操作位运算和剪枝优化和预措置的JPS（JPS-BitPrunePre)寻路总时间为9.5434 x 10^8 ns
从数据可以直不雅观看出，在此环境下，五版JPS算法寻路速度为A*的15倍，81倍，110倍，130倍，273倍，速度方面大幅超越了A*。
JPS寻路算法已经被证明是基于无权重格子，在没有预措置情况下最快的寻路算法。

流程图：

两个定义：

强迫邻居（forced neighbour）：
如果点 n 是 x 的邻居，而且点 n 的邻居有否决（不成行走的格子），而且从 parent(x)、x、n 的路径长度比其他任何从 parent(x)到 n 且不颠末 x 的路径短，此中parent(x)为路径中 x 的前一个点，则 n 为 x 的强迫邻居，x 为 n 的跳点），例如图 2 中，寻找从 S 到 E的路径时，K 为 I 的强迫邻居（I 为 K 的跳点）。这里不认为从 H 到 K 能走，因为对角线有否决（这点和论文纷歧致，但和代码一致，因为如果 H 到 K 能直接达到，会走进 H 右边的否决区，大部门的 JPS 开源代码按照论文都认为 H 到 K能走，所以存在穿越否决的情况），如果需要 H 到 K 可走，则 K 为 H的强迫邻居（H 为 K的跳点）。

跳点（jump point）：
（1）如果点 y 是起点或方针点，则 y 是跳点，例如图 2 中，S 是起点也是跳点，E 是方针点也是跳点；（2）如果 y 有邻居且是强迫邻居则 y 是跳点，例如 I 是跳点，请注意此类跳点和强迫邻居是伴生系，从上文强迫邻居的定义来看 n 是强迫邻居，x 是跳点，二者的关系是伴生的，例如图 2 中 K 的邻居只有I 是跳点，M 虽然也是 K的邻居，但 M 不是跳点，因为 K 不是 M 的强迫邻居；（3）如果 parent(y)到 y 是对角线移动，而且 y 颠末程度或垂直标的目的移动可以达到跳点，则 y 是跳点，例如图 2 中 G 是跳点，因为 parent(G)为 S，S 到 G 为对角线移动，从 G 到跳点 I 为垂直标的目的移动，I 是跳点，所以 G 也是跳点。
三个法则

法则一：JPS 搜索跳点的过程中，如果直线标的目的（为了和对角线区分，直线标的目的代表程度标的目的、垂直标的目的，下文所说的直线均为程度标的目的和垂直标的目的）、对角线标的目的都可以移动，则首先在直线标的目的搜索跳点，再在对角线标的目的搜索跳点。
法则二：（1）如果从 parent(x)到 x 是直线移动，n 是 x 的邻居，若有从 parent(x)到 n 的路径不颠末 x 且路径长度小于或等于从 parent(x)颠末 x 到 n 的路径，则走到 x 后下一个点不会走到 n；（2）果从 parent(x)到 x 是对角线移动，n 是 x 的邻居，若有从 parent(x)到 n 的路径不颠末 x 且路径长度小于从parent(x)颠末 x 到 n 的路径，则走到 x 后下一个点不会走到 n（相关证明见论文）。
法则三：只有跳点才会插手 openset，因为跳点会改变行走标的目的，而非跳点不会改变行走标的目的，最后寻找出来的路径点也只会是跳点调集的子集。
寻路过程：

若 current 当前标的目的是直线标的目的：
（1）如果 current 左后方不成走且左方可走（即左方是强迫邻居），则沿 current左前方和左方寻找不在 closedset 的跳点；
（2）如果 current 当前标的目的可走，则沿 current 当前标的目的寻找不在 closed 调集的跳点；
（3）如果 current 右后方不成走且右方可走（右方是强迫邻居），则沿 current右前方和右方寻找不在 closedset 的跳点；
若 current 当前标的目的为对角线标的目的：
（1）如果 current 当前标的目的的程度分量可走（例如 current 当前为东北标的目的，则程度分量为东），则沿 current 当前标的目的的程度分量寻找不在 closedset 的跳点；
（2）如果 current 当前标的目的可走，则沿 current 当前标的目的寻找不在 closedset的跳点；
（3）如果 current 当前标的目的的垂直分量可走（例如 current 当前为东北标的目的，则垂直分量为北），则沿 current 当前标的目的的垂直分量寻找不在 closedset 的跳点。.

参考

JPS寻路算法优化思路_popcorn丶的博客-CSDN博客

		自动登录	找回密码
密码			立即注册

各类寻路算法记录

本帖子中包含更多资源