11.5 Agarwal-Godfrey 的 2 倍近似 Distance Oracle

Thorup-Zwick 當年在仿真圖上面的想法，是選取許多叢集中心當作障礙物、以每個點為中心張出一顆氣球，直到撞到任何一個障礙物為止。這樣的概念可以應用在非常非常多的演算法中。如果暫時不關心構造出 Distance Oracle 的時間，只在乎「我們儲存了多少東西」的話，可以發現，Throup-Zwick 的 3倍近似最短距離資料結構只需要 n^1.5 的儲存空間。而事實上，存在某些很糟的圖，如果要做到保證 3倍近似最短距離，真的必須要存 n^1.5-bits。類似地，如果是 2倍近似最短距離，那麼某些情形下真的得存到 n^2-bits 的儲存空間。

在 2010 年，羅馬尼亞出生 MIT畢業進入紐約 AT&T 實驗室的 Mihai Pătrașcu (可惜 Pătrașcu 在 2012 年因為腦癌離世了，享年 29 歲，是非常非常年輕且厲害的理論電腦科學家) 與以色列巴伊蘭大學教授 Liam Roditty 注意到，得用到 n^2-bits 儲存空間的那些圖，都必須是稠密圖。他們以此設計出了一個期望 n^{4/3}m^{1/3}-個數字的資料結構。也就是說，當圖相當稀疏(比方說，邊數 m 不到 n^2) 的時候，需要的儲存空間也少了很多。

當時在念伊利諾大學香檳分校 UIUC 的 Rachit Agarwal (現在是康乃爾大學的教授) 以及他的指導教授 Philip Brighten Godfrey (只花了三年就拿到柏克萊 PhD 了) 在 2013 年發表了一個比較簡單的兩倍近似最短距離資料結構 2-Stretch Distance Oracle。今天就來簡單介紹這個資料結構存了哪些東西。

資料結構存什麼：

1. 先定義一個點集合 L，這個集合包含隨機選取的 Õ(n/α) 個點，其中 α 是一個待定參數。
2. 對於所有圖上的點 v，我們儲存以下這些內容：
   • 到 L 之中任何一點的最短距離
   • 到 L 之中最接近的點 ℓ(v)、以及這個距離 r(v) (把所有小於這個距離的點定義為”氣球” B(v))
3. 對於任何兩個點 v 和 w，如果他們的氣球 "相鄰"、甚至有重疊：「B(v) 交集 B+(w) 非空」或是「B+(v) 交集 B(w) 非空」其中 B+(v) 的意思是氣球及其往外擴張一條邊碰到的那些點。這種情形發生的話，我們就用一個雜湊表紀錄下 v 到 w 的距離 dist(v, w)。

如何查詢最短路徑：

1. 對於 u 和 v，如果 (u, v) 有被儲存下來，就直接回傳他們之間的最短距離。
2. 如果 (u, v) 沒有被儲存下來，那我們比較他們的氣球半徑大小 r(u) 和 r(v)：如果 r(u) < r(v)，那我們回傳 dist(u, ℓ(u)) + dist(v, ℓ(u))；反之則回傳 dist(u, ℓ(v)) + dist(v, ℓ(v))。

如此一來就可以在常數時間回傳近似最短距離啦。有兩個部分要證明：一個是如何正確選取 α 使得資料結構大小恰好是期望 n^{4/3}m^{1/3}。二是要證明回傳的長度真的保證在 2倍最短距離之內。這兩個部份的證明就請大家參考下面的短論文囉~

參考資料：

http://www.cs.cornell.edu/~ragarwal/pubs/stretch2.pdf