iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
Software Development

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

近似最短路徑 (7)

11.6a 把樹合併起來

讓我們簡單描述一下把樹合併起來的過程,補上昨天 Peleg’s Distance Labelling 演算法的最後一塊拼圖。

試想一下,現在有 n 棵樹,這些樹都是以某個點往外走 L 步做出來的 BFS 樹,彼此可能有些重疊。如果我們隨意挑選一棵樹 T,並且將所有與之有交集的樹 (存在某個節點出現在T與該樹上) 全部都黏起來,得到比較大的樹 T’,這棵樹 T’ 的直徑,最多也只有 6L 而已。

重複上述步驟,將所有與 T’ 交集的 BFS 樹全部黏起來,得到 T’’,這棵 T’’ 的直徑,最多也只有 10L。換句話說,若我們重複了 k-1 次步驟,那麼樹的直徑最多會變成 (2k-1) * 2L。

氣球和氣球的外圍

假設 U 是目前我們關心的所有 BFS 樹形成的集合。
挑選一棵樹 T 以後,重複往外擴的步驟,得到一系列往外擴張的樹 T1, T2, …, Tk, ...。
擴張次數越多,直徑就會變得越大,距離標籤得到的誤差也就會越大。但是擴張次數越少,最後剩下的樹可能就會很多,也就需要更長的距離標籤才能記錄下所有的樹。因此,我們需要找出一個平衡。

我們在意的是每次擴張,可以合併多少棵樹。如果每次擴張,都能讓融合的樹的總量變成至少 R 倍以上,那麼我們就 "允許" 這次擴張,否則我們就停下來。換句話說,當我們停下來的時候 Tk 的直徑不超過 (2k-1) * 2L,如果這棵樹 Tk 融合了 X 棵樹,那麼與 Tk 有交集的樹(包含那X棵)的總數不超過 R * X。

極大獨立集的想法

Peleg 注意到,如果我們使用以下的貪婪演算法:每次挑選 U 中的任何一棵樹 T、不斷擴張直到有交集的樹不夠而停下來為止,那麼我們不妨將融合成 Tk 的 X 棵樹記錄下來、但是從母集合 U 移除所有與 Tk 有交集的樹。接著挑選新的樹、重複擴張的步驟直到 U 為空為止。

這麼一輪做完以後,那些被丟掉、但是又沒有被融合的樹們,我們將之重新蒐集回來,定義為新的 U’。重複整個貪婪演算法,直到所有的樹都被融合為止。有趣的是,所有的融合出來的樹就像是獨立集一樣,因為每次都把有交集的通通丟掉了,所以任何一個點只會出現在至多一棵融合完的樹上。

每次從 U 做完一次貪婪演算法,我們不難能證明 U’ 的大小不超過 (1-1/R) U。換句話說,貪婪演算法至多只需要重複 log |U| / log (1+1/(R-1)) ≈ O(R log |U|) 次,就會結束。也就是說,如果一開始 |U|=n、我們選取 R=2,那麼只需要 O(log n) 次貪婪演算法便能生出許多融合的樹,使得每一個點出現在至多 O(log n) 棵樹上。

這些融合的樹直徑如何?每一次至少要擴張 R=2 倍,也就是說這個擴張至多只會進行 log |U| / log R 次就會結束。因此樹的直徑不超過 (log |U| / log R - 1) * 2L,其誤差也就不超過 O(log |U| / log R) 倍了。很讚的分析吧!


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

尚未有邦友留言

立即登入留言