《大數據算法》一2.2　最小生成樹代價估計

本節書摘來異步社區《大數據算法》一書中的第2章，第2.1節，王宏誌　編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。

2.2　最小生成樹代價估計

本節討論最小生成樹問題的亞線性算法，首先介紹連通分量個數估計算法，接下來基於此基礎算法設計最小生成樹代價估計算法。

2.2.1　連通分量個數估計算法

連通分量個數估計問題
輸入：一個圖G=(V,G)，有n個頂點，m條邊，該圖表示為鄰接矩陣，圖中結點的最大度為d。
輸出：G中連通分量的個數。
這個算法如果用BFS實現，那麼每個點的鄰居都至少要訪問一次，因而精確解的時間複雜度為
。
下麵考慮隨機化方法。這個算法可以有效地估計連通分量的個數，得到的結果是#CC±εn的概率大於等於2/3，其中＃CC是真實連通分量的個數，並且運行時間和n無關。
這個算法的核心思想如下。設C為連通分量的個數，結點u所在連通分量的結點數記作nu，u的權重為1/nu。那麼，對於每個連通分量，有。因為nu是連通分量中結點的數量，一個連通分量所有的nu是相等的，而權重1/nu的點的個數就是這些點對應的連通分量中點的個數nu，即(同樣的思想在參考文獻［12］中35.3節的最小集合覆蓋近似算法的近似比證明裏用到過。)對每一個連通分量而言，它所對應的頂點的1/nu之和是1，那麼所有頂點的1/nu之和就是圖中連通分量的個數。
這樣就把這個問題轉化為怎樣快速地估計nu。顯然，可以通過抽樣來快速估計nu和1/nu的和，即用少部分點來表示這個和。
這個估計問題並不能通過直接的抽樣和估計來解決。考慮一個很壞的情況：所有的頂點都在一個連通分量中。這種情況下計算nu需要一次BFS，時間複雜度是O(m)，從而導致了算法不是亞線性的。
我們基於下麵的想法來估計nu的值:如果u所在的連通分量結點數很少，其規模可以通過BFS直接估計；如果u所在的連通分量很大，那麼1/nu就很小，這意味著它對整個和的貢獻很小，因此可以在幾步內完成BFS，完成不了的點就放棄，因為它對和的貢獻足夠小。
根據上述討論，對這個問題可以做這樣的估計，即估計值nu=min{nu,2/ε}。當連通分量不大時，nu是BFS可以準確算出的nu；如果連通分量大於閾值2/ε，就取nu等於2/ε。
引理2-1描述了這個估計的誤差界限。
引理2-1　對於圖。
證明　對於點u來說，連通分量結點數量小於2/ε時，估計值等於真實值,即1nu-1nu=0<ε2。當u所對應的連通分量結點數量大於等於2/ε時，誤差。因而。■
根據上述討論，算法描述如算法2-3所示。算法2-3　估計圖中連通分量個數

1　for i=1 to s=θ1ε2 do
2　　　隨機選擇點u
3　　　從u開始BFS，將訪問到的頂點存到排序序列L中，訪問完連通分量或L=2/ε時停止，nu=L
4　　　N=N+1/nu
5　返回C=N/s×n

算法的時間複雜度和精度分別如定理2-3和定理2-4所示。
定理2-3　算法2-3的運行時間是。
證明　根據算法運行過程可知，算法循環的輪數和1ε2同階。在每一循環中最多處理結點的個數是2/ε。那麼處理每個結點需要從這個結點開始做BFS，最多訪問2/ε個結點。在BFS過程中，從每個結點出發都要訪問其所有鄰居，因此，每輪的代價是d/ε。此外，還需要將其存到排序序列L中。由於L需要有序，可以用一個平衡二叉樹保存L。考慮到插入和刪除一個元素到一個具有2/ε個結點的平衡二叉樹的代價為log2/ε，運行時間是
。■
從定理2-3可以看出，該算法的運行時間和整個圖的大小沒有關係，隻和輸入的ε和頂點的度d有關係。
定理2-4　有n個頂點的圖G中，若其頂點的度至多為d，算法2-3對G中連通分量個數的估計誤差最多為±εn的概率大於2/3，即，其中C是G中連通分量的個數。
證明　對於算法2-3抽樣中的第i個結點u，令Yi=1/nu。對於整個抽樣來說，令Y等於所有的Yi相加，即。由於所有的結點都是獨立抽樣的，因而所有的E（Yi）都等於E(Y1),故。
根據上述討論可知，C的數學期望為。因此，根據Hoeffding不等式，。因為s和1ε2同階，因此，取s=4/ε2，則，根據引理。因而

補充知識：Hoeffding不等式
Hoeffding不等式是隨機算法證明中常用的一個不等式，其用於描述一個隨機變量的和與這個和的數學期望之間的關係。具體描述如下:
假設Y1,…,Ys為［0,1］區間內s個獨立同分布的隨機變量，，則
。

2.2.2　最小生成樹代價估計算法

1.問題的定義
輸入是無向有權連通圖G=(V,E)，其頂點的度最大為D,邊上的權來自整數集合{1,2，3，…,W},最大不超過W，令一棵生成樹的代價定義為這棵樹上所有邊的權重之和，問題的輸出是圖G的最小生成樹的代價。最小生成樹的例子如圖2-2所示，左圖是原圖，其最小生成樹如右圖所示，它的代價是26。

求最小生成樹的精確算法是貪心法，可以用Prim算法或Kruskal算法。其時間複雜度為O(mlogn)，是超過線性的。本小節研究求最小生成樹代價的時間亞線性算法。
2.亞線性算法思想
在設計算法的過程中，有兩個假設。第一個假設是圖組織成鄰接表的形式，這意味著可以直接訪問每個結點的所有鄰居。第二個假設是可以隨機均勻地選擇結點，這保證了可以隨機均勻抽樣。
時間亞線性算法的基本思想是利用特定子圖連通分量的數量估計最小生成樹的權重。這有一些抽象，看一個具體的例子。假設一個簡單圖G，所有邊的權重都是1或者2，我們考慮將最小生成樹的權重用權重為1和2的邊分別表示。
首先，所有的邊都是大於等於1的，把所有邊的權重都減去1，這時對於最小生成樹，權重減掉了n-1，即權重至少為1的邊的數量。剩下圖中最小生成樹的邊數等於最小生成樹中權重大於1的邊的數量，因為所有邊的權重減去1意味著剩下邊的權重在原來的圖中是2，在最小生成樹中把減掉的權重加回來就得到了整個最小生成樹的權重。因而這個最小生成樹的權重表示為:最小生成樹中權重至少為i的邊的數量)，
下麵討論#N2的計算方法。考慮這樣一件事情，把最小生成樹中所有邊的權重減掉1，剩下的就是原來權重是2的邊。如果在最小生成樹當中把這些權重是2的邊都去掉，則最小生成樹會變成若幹個連通分量。那麼，剩下的連通分量中每條邊的權重都是1，這時生成的圖變得不連通。最小生成樹需要把整個圖的所有點都連上，這就需要這些最小生成樹當中權重為2的邊來連接。那麼，最小生成樹當中權重為2的邊的數量就等於把這些連通分量連到一起所需要的邊數，即至少是這些連通分量的個數減去1。因此，#N2就是權重為1的邊構成的導出子圖的連通分量數減去1。
依次類推，如果這個圖的權重有1，2，3三種，那麼，#N3就是去掉權重為3的邊以後，在邊的權重隻是1和2的情況下，構成的導出子圖中連通分量數減去1。
引理2-2描述了一般情況下最小生成樹和連通分量的關係。
引理2-2　設Gi是G中包含所有權重小於i的邊的子圖，Ci是Gi中的連通分量個數，那麼最小生成樹中權重大於i的邊數為Ci-1。因此最小生成樹的權重為證明　令βi為最小生成樹中權重大於i的邊的個數，每條邊對最小生成樹的權重的基礎貢獻為1，每條權重大於1的邊額外貢獻了1，每條權重大於2的邊貢獻的更多，因此其中C0是把所有邊都去掉剩下的連通分量數量，即n。■
3.算法的描述
引理2-2把最小生成樹的權重和子圖的連通分量個數聯係到一起。現在的問題轉化為給定一個圖，怎樣快速地估計圖中連通分量的數量，如果能夠快速估計出連通分量的數量，則能夠有效估計出最小生成樹的權重。根據2.2.1節中的討論,最小生成樹代價估計算法如算法2-4所示,其中用於估計G中包含所有權重小於i的邊的子圖Gi中的連通分量個數，其輸入中的εW是一個參數，該參數用於在計算連通分量過程中控製從每個點開始進行BFS所訪問的最多頂點，即。算法2-4　圖G的最小生成樹代價估計算法

1　for i=1 to w-1 do
2　　　　　Ci=CCGi,d,ε2W
3　returnWMST=n-W+∑W-1i=1Ci

算法2-4的時間複雜度，是前麵講過的估計連通分量算法的複雜度和W的乘積，顯然和圖中頂點的個數無關。
下麵分析該算法的誤差，由於WMST表示W-1個連通分量權重的累加，根據定理2-4，對每個Ci，滿足，而要使WMST-WMST有界限，需要所有W-1個都滿足，此事件概率的下界是(2/3)W-1，並不能保證常數界限，因而需要在求連通分量個數的函數中設置合適的抽樣次數，以降低發生概率的上界。
引理2-3　在估計連通分量個數算法2-3中，抽樣次數，則對計算過程中的每個連通分量C都滿足。
證明　考慮定理2-4的證明，取，由公式(2-1)和(2-2)，有根據引理2-1的證明過程，取nu=min{nu,2W/ε}時，
，故■
定理2-5　算法2-4得到的結果WMST和WMST的誤差滿足PrWMST-WMST≤εWn≥23。
證明　根據引理2-3，對於每個Ci都滿足
，從而,根據並集界限，即若幹事件都發生的概率小於等於它們單獨發生的概率之和：