post on 05 May 2022 about 3399words require 12min
CC BY 4.0 （除特别声明或转载文章外）
如果这篇文章帮助到你，可以请我喝一杯咖啡~
Astar 算法是一种很常用的路径规划和图搜索、遍历算法，又被称作 A* 算法。和先前的算法相比，它有较好的性能和准确度。在本次作业中，我将使用课程上学到的知识对 Astar 算法进行分析，并用其求解 k 短路问题。
路径规划是指的是机器人的最优路径规划问题，即依据某个或某些优化准则（如工作代价最小、行走路径最短、行走时间最短等），在工作空间中找到一个从起始状态到目标状态能避开障碍物的最优路径。机器人的路径规划应用场景极丰富，最常见如游戏中 NPC 及控制角色的位置移动，百度地图等导航问题，小到家庭扫地机器人、无人机大到各公司正争相开拓的无人驾驶汽车等。
路径规划属于规划类问题，因此也同样符合之前上课提到的智能规划的定义：给定初始状态、目标状态，算法输出计算出可以从初始状态到达目标状态的动作序列（规划）。通常来说，Astar 算法应用在路径规划类场景时，可以对问题做如下抽象：给定图 $(V,E)$，图中每条边有长度 $E_i=w_i$，需要给出从起点 $S\in V$ （S=Start）到终点 $T\in V$ （T=Target）的一个最优路径或多个较优路径（例如导航软件通常会给出多条路径供参考）。当然实际问题的起点或终点也可能不止一个，但是可以在建图的时候可以调整建图方式将多个点连到一个虚拟的逻辑点上，因此下文只考虑一个起点和一个终点的情况。
k 短路问题是路径规划问题中的一个经典问题，例如在导航软件中通常会给出多条路径供用户选择。此处我简要描述 OpenJ_Bailian-2449 这道题目中的表述：
一张图中有 $N$ 个顶点，$M$ 条有向边，每条边有一个边长 $E_i$，要求给定的起点 $S$ 到给定的终点 $T$ 的路径中第 $K\ge 1$ 短的。注意这里可能存在 $S=T$，此时认为 $S\to T$ 的第 1 短路为 0。
Astar 算法的主要思想与无权图中的 BFS（广度优先搜索） 或是有权图中的 Dijkstra 算法完全相同：
Astar 算法与前两者不同之处在于其节点的扩展顺序，由以下公式确定：$f(u) = g(u) + h(u)$ 。$g(u)$ 代表的是从出发点 s 沿着已生成的路径到指定待检测节点 u 的移动开销。$h(u)$ 为启发函数，代表当前节点 u 到目标节点 g 的估计移动开销。f 值越小越优，或 f 相同时，h 小的更优。从另一个角度看，BFS 或 Dijkstra 本身就可以看作 Astar 在简单情况下的特例或是退化（$h(u)\equiv 0$）。启发函数也被认为是一种试探，由于在真正求出答案路径前，我们不确定在前面会出现什么障碍物，因此使用 $h(u)$ 去预估。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。虽然没有实际上的限制（除了要求 $h(u)$ 不能大于实际值），$h(u)$ 应当以较小的代价实时计算，或是可以预先处理。$h(u)$ 应当根据实际场景决定，例如：
在本次求解 k 短路问题中，我将使用点 $u$ 到起点 $S$ 的最短距离 $d(u)$ 作为启发函数，求解原图的反向图中 $T\to S$ 的第 $k$ 短路，从而等价于原问题。
首先设计一个结构用于保存图。顶点集 v 中保存了每个顶点包含的出边和入边，边集 e 中保存了每条边的起点终点与边长。构造函数用于初始化顶点集 v，接口 add 用于动态地向图中加边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Graph {
struct Vertex {
vector<int> o, i;
};
struct Edge : pair<int, int> {
ll len;
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n) : v(n) {}
void add(const Edge &ed) {
v[ed.first].o.push_back(e.size());
v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
};
随后实现一个 Dijkstra 算法求解 $d(u)$，用于 Astar 算法中的启发函数。此处设置了一个常量 INF 用于表示距离的无穷大或不可达。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const ll INF = 1e9;
struct Dijkstra : Graph {
vector<ll> d;
Dijkstra(int n) : Graph(n) {}
void ask(int s) {
d.assign(v.size(), INF);
priority_queue<pair<ll, int>> q;
for (q.emplace(d[s] = 0, s); !q.empty();) {
ll dis = -q.top().first;
int u = q.top().second;
if (q.pop(), d[u] < dis)
continue;
for (auto k : v[u].o)
if (d[e[k].second] > d[u] + e[k].len)
d[e[k].second] = d[u] + e[k].len,
q.emplace(-d[e[k].second], e[k].second);
}
}
};
在上述代码的基础上就能很方便的实现 Astar 了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Astar : Dijkstra {
vector<ll> ans;
Astar(int n) : Dijkstra(n) {}
void ask(int s, int t, int k) {
Dijkstra::ask(s);
if (d[t] == INF)
return;
vector<int> cnt(v.size(), 0);
priority_queue<pair<ll, int>> q;
for (q.emplace(-d[t], t); !q.empty();) {
ll dis = -q.top().first;
int u = q.top().second;
if (q.pop(), u == s)
ans.push_back(dis);
if (++cnt[u] > k) {
if (u == s)
return;
continue;
}
for (auto k : v[u].i)
q.emplace(d[u] - d[e[k].first] - e[k].len - dis, e[k].first);
}
}
};
代码提交在 vjudge，通过了该道题目的测试。运行时间为 197ms，远远优于 4000ms 的限制。
Astar 算法中外循环中每次从 OPEN 中取出点，共取 n 次。内循环中遍历它的邻接点，并将这些邻接点放入 OPEN 中，对 OPEN 进行排序。OPEN 表大小是 $O(n)$ 量级的，排序算法的理论复杂度是 $O(n\log n)$，内循环总的复杂度为 $O(n\log n+E)=O(n\log n)$。因此，Astar 算法的总时间复杂度为 $O(n^2\log n)$。得益于启发函数的引入，Astar 算法在实际运行时搜索的节点数量大大减少了，因此可以作为一个经典算法流传下来。当然，Astar 算法还存在一些问题，如：
后续的学习中我将继续考虑对 A* 算法的一些变种进行研究，例如 ARA*、D*、Block A* 算法等。
Related posts