近似最短路径 (1)

11 近似最短路径

前面介绍的所有点对最短路径演算法,好写的得花 n^3 的时间、比较快的又得仰赖矩阵相乘。如果是单一源头最短路径演算法,仰赖的 BFS 或 Dijkstra 演算法都是循序的,没办法轻易地平行化。如果我们对於距离的精确程度没有太高的要求,允许一点点的误差的话,是否有机会存在更快、或更容易平行化的演算法呢?当然是有的。

我们先来关心 APSP。这些方法大致分成两派:一派是通过预处理,对於图 G,找出一个子图 H,使得 H 上面任两点的最短距离与图 G 上面任两点的最短距离差不多、而且不会低估距离。这样的子图称为 graph spanner (span 有着生成的意思,spanner 有点像是能生出图中最短路径长度的边的集合的概念)。如果我们不限制图 H 是图 G 的子图、并且允许图 H 带有自由设定的权重的话,这样不低估但又生成近似最短距离的图 H 被称为 graph emulator (仿真图)。

第二派是走代数路线,我们可以将图上的点视为一种赋距空间 (metric space)、而任两点之间的图上距离便是它们在该空间中的距离。如果我们能够压缩这个赋距空间、或是将这个空间嵌入至维度更低的其他赋距空间,使得压缩後任两点之间的距离不失真,那麽我们便可能用更快的时间算出近似最短距离。

11.1 误差不超过 2 的 Graph Spanner

现在让我们来考虑以下的随机演算法,这个方法可以帮助我们在 Õ(n^2.5) 的时间内找出一个无向无权图中,误差不超过 2 的不低估最短路径。

  • 输入:无向无权图 G
  • 输出:图 G 的子图 H
  • 步骤:
    1. 将所有度数少於 n^{0.5} 的点,其所有相邻边全部加入 H。
    2. 让每个点以 n^{-0.5} 的机率被随机选取,令这个点集合为 S。
    3. 以 S 中的每个点为树根,做出一棵 BFS 树。把树上的边加入图 H。
    4. 重复步骤 2 和 3,重复 log n 次。

不难发现,如果一个点度数超过 n^{0.5},那麽有极高的机率,在某一次循环的步骤 2 之中会被加入集合 S。考虑任何一条 s 到 t 的最短路径,如果这条路径的边都在 H 中,那显然最短路径长会被保留。如果这条路径上某条边没被加入 H,那麽代表与该边相邻的点 v,度数很大,他旁边很高机率会有一个点 x 被选入 S,我们此时就可以顺着这个点 x 做出来的 BFS 树一路走到 t。误差是多少呢?注意到在图 H 中找出来的路线为:s → v, v → x (这条边一定存在BFS树上,注意到这个是反向行走所以图必须是无向图), x → t。这条路线长度不超过 s → v, v→ x, x→ v, v → t,也就是说是原先图 G 上面 s → t 最短路径加上两条边的长度,也就是说误差不超过 +2。

有了图 H 以後,我们就可以对每个点做一次 BFS,找出任两点之间的最短路径,耗时 O(mn),其中 m 是图 H 的边数。而 m 的期望值是 n^1.5 log n:因为步骤 2 每一轮会选出平均 n^0.5 个点,每个点会做出一棵带有最多 n-1 条边的 BFS 树。而步骤 1 至多加入 n^1.5 条边。
因此,我们就得到一个近似的最短距离演算法,虽然有误差,但是时间复杂度从 n^3 降到 n^2.5 左右啦。


<<:  DAY23 - 自学历程中的支线任务做不完

>>:  [Day20] THM DogCat

参赛心得&感想

首先要先回顾、检讨一下, 刚好遇到专案忙碌的时候, 写出来的文章有点惨不忍睹, 很多程序的细节其实没...

D36-铁人赛完赛心得

铁人赛完赛罗~~ 在完赛的这一刻,我发现,我获得的东西,比我写出来的东西还多。 - 除了看自己写出来...

30天学会C语言: Day 13-递回体验镇魂曲

递回 在函式里面可以呼叫函式本身 下面例子中,fun() 会先将参数 x 显示到视窗上,之後判断 x...

蓝底白字错误讯息

最近Windows Updata有列印问题KB5000802, 而我是用Chrome进1111人力银...

Day 29 - 这个游戏制作人疯了吧

Intro 这次写了一个小游戏。里面包含了前几次练习的功能,但是有些东西是用 class 来写出来,...