【极地特快】【吃吃你的号】【科普】关于路径规划算法

qfsbsn · 发表于 2023-12-24 00:18:41

在吃吃你的号环游GM大陆的时候，我们的列车长云老师经常想要从一个地方开到另一个地方。但是由于他不知道怎么规划路径，把我抓过来当他的导航员。考虑到吃吃你的号是一辆高度智能化的列车，我决定让云老师自己选择一种他喜欢的算法来输入吃吃你的号，这样就会有最短路生成，而云老师也不用再绕路了。

一、路径规划算法概述

路径规划算法是一种寻找从起点到终点的最优路径的方法。在连续域范围内，路径规划问题通常包括环境建模、路径搜索和路径平滑三个环节。环境建模是指将现实世界中的环境信息转化为计算机可理解的模型，也就是图；路径搜索则是在图的基础上寻找最短路径；而路径平滑则是将搜索出的路径进行优化，使其成为一条实际可行的路径，也就是一个抽象转化为实际的过程。。

二、常用算法

Bellman-Ford、Floyd、Dijkstra、A*和Johnson算法都是用于解决路径规划问题的算法，它们各有特点，下面将详细介绍这五种算法的特征。

Floyd算法
Floyd 算法
是用来求任意两个结点之间的最短路的。

复杂度比较高，但是常数小，容易实现（只有三个 for）。

适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）

实现
我们定义一个数组 f[k][x][y]，表示只允许经过结点 1 到 k（也就是说，在子图 V'={1, 2,..., k} 中的路径，注意，x 与 y 不一定在这个子图中），结点 x 到结点 y 的最短路长度。

很显然，f[n][x][y] 就是结点 x 到结点 y 的最短路长度（因为 V'={1, 2, \ldots, n} 即为 V 本身，其表示的最短路径就是所求路径）。

接下来考虑如何求出 f 数组的值。

f[0][x][y]：x 与 y 的边权，或者 0，或者 +∞（f[0][x][y] 什么时候应该是 +∞？当 x 与 y 间有直接相连的边的时候，为它们的边权；当 x = y 的时候为零，因为到本身的距离为零；当 x 与 y 没有直接相连的边的时候，为 +∞）。

f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])

复制代码

（f[k-1][x][y]，为不经过 k 点的最短路径，而 f[k-1][x][k]+f[k-1][k][y]，为经过了 k 点的最短路）。

上面两行都显然是对的，所以说这个做法空间是 O(N^3)，我们需要依次增加问题规模（k 从 1 到 n），判断任意两点在当前问题规模下的最短路。

<div>for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
}
}
}</div>

复制代码

因为第一维对结果无影响，我们可以发现数组的第一维是可以省略的，于是可以直接改成

f[x][y] = min(f[x][y], f[x][k]+f[k][y])。

复制代码

证明：
我们注意到如果放在一个给定第一维 k 二维数组中，f[x][k] 与 f[k][y] 在某一行和某一列。而 f[x][y] 则是该行和该列的交叉点上的元素。

现在我们需要证明将 f[k][x][y] 直接在原地更改也不会更改它的结果：我们注意到 f[k][x][y] 的涵义是第一维为 k-1 这一行和这一列的所有元素的最小值，包含了 f[k-1][x][y]，那么在原地进行更改也不会改变最小值的值，因为如果将该三维矩阵压缩为二维，则所求结果 f[x][y] 一开始即为原 f[k-1][x][y] 的值，最后依然会成为该行和该列的最小值。

故可以压缩。

Bellman-Ford算法

Bellman–Ford 算法
Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

在国内 OI 界，你可能听说过的「SPFA」，就是 Bellman–Ford 算法的一种实现。

过程
先介绍 Bellman–Ford 算法要用到的松弛操作（Dijkstra 算法也会用到松弛操作）。

对于边 (u,v)，松弛操作对应下面的式子：

dis(v) =min(dis(v), dis(u) + w(u, v))。

复制代码

这么做的含义是显然的：我们尝试用 S → u → v（其中 S → u 的路径取最短路）这条路径去更新 v 点最短路的长度，如果这条路径更优，就进行更新。

Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

每次循环是 O(m) 的，那么最多会循环多少次呢？

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 +1，而最短路的边数最多为 n-1，因此整个算法最多执行 n-1 轮松弛操作。故总时间复杂度为 O(nm)。

但还有一种情况，如果从 S 点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 n-1 轮，因此如果第 n 轮循环时仍然存在能松弛的边，说明从 S 点出发，能够抵达一个负环。

<div>struct edge {
int v, w;
};
vector<edge> e[maxn];
int dis[maxn];
const int inf = 0x3f3f3f3f;
bool bellmanford(int n, int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0;
bool flag; // 判断一轮循环过程中是否发生松弛操作
for (int i = 1; i <= n; i++) {
flag = false;
for (int u = 1; u <= n; u++) {
if (dis[u] == inf) continue;
// 无穷大与常数加减仍然为无穷大
// 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
flag = true;
}
}
}
// 没有可以松弛的边时就停止算法
if (!flag) break;
}
// 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
return flag;
}
</div>

复制代码

Dijkstra算法

Dijkstra算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解非负权图上单源最短路径的算法。

过程
将结点分成两个集合：已确定最短路长度的点集（记为 S 集合）的和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。

初始化 dis(s)=0，其他点的 dis 均为 +∞。

然后重复这些操作：

1. 从 T 集合中，选取一个最短路长度最小的结点，移到 S 集合中。
2.对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作。

直到 T 集合为空，算法结束。

<div>struct edge {
int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
void dijkstra(int n, int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0;
for (int i = 1; i <= n; i++) {
int u = 0, mind = 0x3f3f3f3f;
for (int j = 1; j <= n; j++)
if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];
vis[u] = true;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
}
}
}</div>

复制代码

这个算法是一个O(n²)算法。可以通过队列优化变为O(m*log m).我很喜欢这个算法，所以我为它找了个流程图给你们看看。（见配图）

A*算法
A*算法是一种启发式搜索算法，它结合了最佳优先搜索和广度优先搜索的特点。A*算法通过使用启发式函数来估计节点到目标节点的代价，从而指导搜索过程。这种算法适用于有障碍物的路径规划问题，能够找到最短路径。实际上就是把Dijkstra的dis(x)函数转化为f(x)=g(x)+dis(x)，其中g(x)为起点到x节点的路径长度。

Johnson算法
Johnson 算法通过另外一种方法来给每条边重新标注边权。

我们新建一个虚拟节点（在这里我们就设它的编号为 0）。从这个点向其他所有点连一条边权为 0 的边。

接下来用 Bellman–Ford 算法求出从 0 号点到其他所有点的最短路，记为 h_i。

假如存在一条从 u 点到 v 点，边权为 w 的边，则我们将该边的边权重新设置为 w+h_u-h_v。

接下来以每个点为起点，跑 n 轮 Dijkstra 算法即可求出任意两点间的最短路了。

一开始的 Bellman–Ford 算法并不是时间上的瓶颈，若使用优先队列实现 Dijkstra 算法，该算法的时间复杂度是 O(n*m*log m)。

三、应用领域

高科技领域
路径规划算法在高科技领域有着广泛的应用。例如，在机器人领域，路径规划算法可以帮助机器人实现自主行走、避障等功能；在飞行器领域，路径规划算法可以帮助飞行器实现精确的导航和飞行控制。

日常生活
路径规划算法也渗透到了我们的日常生活中。例如，在物流管理中，路径规划算法可以帮助快递公司优化配送路线，提高配送效率；在城市交通中，路径规划算法可以帮助导航系统为用户提供最佳的出行路线。

物流管理
在物流管理中，路径规划算法的应用尤为突出。通过路径规划算法，物流公司可以优化车辆调度、货物配送等环节，降低运输成本，提高物流效率。同时，路径规划算法还可以帮助物流公司应对突发情况，如交通事故、天气恶劣等，及时调整运输计划，确保货物按时送达。

四、总结与展望

路径规划算法作为智能化的重要组成部分，在各个领域都发挥着重要作用。随着科技的不断发展，我们相信未来会有更多高效、智能的路径规划算法出现，为我们的生活带来更多便利和惊喜。

备注：本文的代码中如果多出了<div>和</div>，是编辑器的问题，无视就好。
备注2：没有备注2。看到这里，我这节车厢就到底了。接下来让我们有请矢量先生。@HoodedMurking