iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
Software Development

圖論與演算法之間的相互應用系列 第 26

近似最短路徑 (6)

11.6 距離標籤 Distance Labellings

最短距離資料結構 Distance Oracles 有一個非常極端的形式,那就是距離標籤:透過預處理,給予圖上的每一個點 v 一個二元字串 L(v),作為標籤 (labels)。這個標籤可以儲存任何的訊息。但是,當我們想要知道某兩個點 u 和 v 之間的最短距離的時候,只能依靠 L(u) 和 L(v) 這兩個標籤的資訊,就必須要推算出最短距離。

昨天說明的 Agarwal-Godfrey Distance Oracle 滿足上述 (Approximate) Distance Labeling 的條件:對於每個節點,我們只要在標籤寫下與之有關的所有距離即可。查詢的時候由於已經從標籤上得知 dist(u, ℓ(u))、 dist(v, ℓ(u))、 dist(u, ℓ(v))、 dist(v, ℓ(v)) 這幾個數值,可以直接算出近似距離。

這個距離標籤有什麼好處呢?最直接的好處就是,經過預處理以後,我們不需要記住整張圖、甚至在查詢的時候也只需要存取兩張標籤,對於常見資料庫的存取負擔是極小的。

以色列魏茨曼科學研究學院的教授 David Peleg 在 1999 年提出了 Distance Labelling 的概念。
在 Peleg 提出的論文 中利用了樹覆蓋的概念,來得出 O(log n)-近似距離標籤。我們今天會先介紹大方向,然後明天繼續把細節補完:

對於每一個點 v,我們將它的「距離 L 以內」的 BFS 樹刻劃出來。選取 L=1, 2, 4, 8, ...,我們就會得到 log n 棵樹。總共有 n log n 棵,每一層 L 有 n 棵 BFS 樹。對於每一層距離 L,同一個點可能出現在多棵 BFS 樹裡面。如果我們可以把這些樹稍加合併,使得每一個點只出現在至多 O(log n) 棵樹上,而且同時不犧牲太多距離 (原本對於某一層 L,樹上任意兩點的距離不超過 2L,但是合併一些樹以後,樹上任何兩點的距離可能會超過 2L)。在我們的例子中,這個距離會被犧牲 log n倍。

這麼一來,我們能對每一個節點定義他的距離標籤,這個標籤大小是 O(log^3 n)-bits 的:
有 log n 個不同的 L 數值
每一個不同的 L,我們記錄下這個點出現所在的 "被合併過的BFS樹" 的編號,對於一個固定的 L,最多有 O(log n) 個不同的編號,因為出現在至多 O(log n) 棵樹上。
每一棵樹的編號是一個 O(log n)-bits 的整數,因為合併前至多只有 n log n 棵樹,因此合併後也只有這麼多,我們可以將他們重新編號。

要怎麼估計 u 和 v 的最短距離呢?很簡單,把它們的距離標籤拿出來看看:對於每一層 L,檢查他們所出現的那些樹的編號。如果 u 和 v 出現在同一棵樹上,代表他們距離不超過 (log n)L。如果 u 和 v 沒有出現在同一棵樹,那麼代表他們的最短距離一定超過 L。

剩下什麼細節呢?剩下把 BFS 樹合併的方法。方法單純,而且與氣球的概念非常類似。這個我們明天繼續~


上一篇
近似最短路徑 (5)
下一篇
近似最短路徑 (7)
系列文
圖論與演算法之間的相互應用30

尚未有邦友留言

立即登入留言