【极地特快】【吃吃你的号】【科普】关于路径规划算法
本帖最后由 qfsbsn 于 2023-12-24 22:36 编辑在吃吃你的号环游GM大陆的时候，我们的列车长云老师经常想要从一个地方开到另一个地方。但是由于他不知道怎么规划路径，把我抓过来当他的导航员。考虑到吃吃你的号是一辆高度智能化的列车，我决定让云老师自己选择一种他喜欢的算法来输入吃吃你的号，这样就会有最短路生成，而云老师也不用再绕路了。
一、路径规划算法概述
路径规划算法是一种寻找从起点到终点的最优路径的方法。在连续域范围内，路径规划问题通常包括环境建模、路径搜索和路径平滑三个环节。环境建模是指将现实世界中的环境信息转化为计算机可理解的模型，也就是图；路径搜索则是在图的基础上寻找最短路径；而路径平滑则是将搜索出的路径进行优化，使其成为一条实际可行的路径，也就是一个抽象转化为实际的过程。。
二、常用算法
Bellman-Ford、Floyd、Dijkstra、A*和Johnson算法都是用于解决路径规划问题的算法，它们各有特点，下面将详细介绍这五种算法的特征。
Floyd算法
Floyd 算法
是用来求任意两个结点之间的最短路的。
复杂度比较高，但是常数小，容易实现（只有三个 for）。
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）
实现
我们定义一个数组 f，表示只允许经过结点 1 到 k（也就是说，在子图 V'={1, 2,..., k} 中的路径，注意，x 与 y 不一定在这个子图中），结点 x 到结点 y 的最短路长度。
很显然，f 就是结点 x 到结点 y 的最短路长度（因为 V'={1, 2, \ldots, n} 即为 V 本身，其表示的最短路径就是所求路径）。
接下来考虑如何求出 f 数组的值。
f：x 与 y 的边权，或者 0，或者 +∞（f 什么时候应该是 +∞？当 x 与 y 间有直接相连的边的时候，为它们的边权；当 x = y 的时候为零，因为到本身的距离为零；当 x 与 y 没有直接相连的边的时候，为 +∞）。
f = min(f, f+f)
（f，为不经过 k 点的最短路径，而 f+f，为经过了 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 = min(f, f + f);
}
}
}</div>
因为第一维对结果无影响，我们可以发现数组的第一维是可以省略的，于是可以直接改成
f = min(f, f+f)。
证明：
我们注意到如果放在一个给定第一维 k 二维数组中，f 与 f 在某一行和某一列。而 f 则是该行和该列的交叉点上的元素。
现在我们需要证明将 f 直接在原地更改也不会更改它的结果：我们注意到 f 的涵义是第一维为 k-1 这一行和这一列的所有元素的最小值，包含了 f，那么在原地进行更改也不会改变最小值的值，因为如果将该三维矩阵压缩为二维，则所求结果 f 一开始即为原 f 的值，最后依然会成为该行和该列的最小值。
故可以压缩。
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;
int dis;
const int inf = 0x3f3f3f3f;
bool bellmanford(int n, int s) {
memset(dis, 63, sizeof(dis));
dis = 0;
bool flag;// 判断一轮循环过程中是否发生松弛操作
for (int i = 1; i <= n; i++) {
flag = false;
for (int u = 1; u <= n; u++) {
if (dis == inf) continue;
// 无穷大与常数加减仍然为无穷大
// 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
for (auto ed : e) {
int v = ed.v, w = ed.w;
if (dis > dis + w) {
dis = dis + 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;
int dis, vis;
void dijkstra(int n, int s) {
memset(dis, 63, sizeof(dis));
dis = 0;
for (int i = 1; i <= n; i++) {
int u = 0, mind = 0x3f3f3f3f;
for (int j = 1; j <= n; j++)
if (!vis && dis < mind) u = j, mind = dis;
vis = true;
for (auto ed : e) {
int v = ed.v, w = ed.w;
if (dis > dis + w) dis = dis + 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 好硬核的知识 之前好像听说过有些游戏的自动寻路功能用的就是A*算法呢 居然能在gm看到这么硬核的算法科普，Dijkstra 还是好用的，但我现在已经基本忘光了，需要复习一下 看起来好强大的感觉，收藏起来慢慢钻研{:4_114:} 彳亍，泥潭的程序员小朋友越来越多了
（看语气你是不是高中联赛选手（指 很硬核的规划算法有学到很多长脑子了 基本上都已经忘了，不过现在的工作中也不怎么需要用到了 有一种被知识填充的安全感，，， 本帖最后由 woyiwu 于 2023-12-24 00:33 编辑
老实说在论坛里面科普算法真的是我没想到的，果然论坛包罗万象，不过这个科普也太硬核了一点，有种不是这方面的人不想看，对于了解的人来说又太基础了的感觉，而且实话说有种阅读个人博客的既视感 啊啊啊，好硬核啊，要被知识彻底污染了啊{:4_92:} 你好像没有@成功（）
以及这么硬核真的可以吗，明明车号超不正经的（） 好硬核啊，有种知识从大脑流淌过的感觉（开个玩笑 很详细，这是最近的期末作业吗;P 看了一下很多东西都还给老师了，好硬核的科普教学贴（ 感觉好高端，是我无法触碰的知识了 哇塞。。是我完全不了解的知识呢{:6_176:} 是硬核的知识科普噜，泥潭真素卧虎藏龙{:6_185:} 以前数据结构考试还是很懂算法的，但是现在用不到就忘了 (´×ω×`)一脸懵地进来，一脸懵地出去……
吃吃你的……会取名欸～ 看标题还在想是什么...点进来一看一长篇关于代码的说明...一瞬间的头疼