Astar 算法求解 k 短路问题

05 May 2022 3302字 12分
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 算法完全相同：

将顶点集 $V$ 划分为 OPEN、CLOSED 两个集合，前者只包含起点 S，后者包含之外的其他节点。
每次从 OPEN 集中选择最优的节点到 CLOSED 集中，然后将其后继节点放入 OPEN 集中。
重复（2）中的操作，作选取最优节点，直到到达目标，或者 OPEN 为空为止。
最后在 CLOSED 集中根据目标 T 所包含的前序节点逆序查找最后到达起点 S，这个链路的逆序即最优路径。

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)$ 应当根据实际场景决定，例如：

在一个迷宫棋盘上移动的 AI，可能会使用两点曼哈顿距离
一个离线的导航软件，可能会使用两点间的直线距离
一个在线的导航软件，可能会使用其他用户在两点间移动的平均时间

在本次求解 k 短路问题中，我将使用点 $u$ 到起点 $S$ 的最短距离 $d(u)$ 作为启发函数，求解原图的反向图中 $T\to S$ 的第 $k$ 短路，从而等价于原问题。

程序设计

首先设计一个结构用于保存图。顶点集 v 中保存了每个顶点包含的出边和入边，边集 e 中保存了每条边的起点终点与边长。构造函数用于初始化顶点集 v，接口 add 用于动态地向图中加边。

#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 用于表示距离的无穷大或不可达。

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 了。

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* 算法等。