53
技術社區[雲棲]
《大數據算法》一2.1 時間亞線性算法概述
本節書摘來異步社區《大數據算法》一書中的第2章 ，第2.1節，王宏誌 編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。
2.1 時間亞線性算法概述
本節我們通過兩個簡單的例子來介紹時間亞線性算法的基本概念。
2.1.1 平麵圖直徑問題的亞線性算法
1.問題的定義
平麵圖直徑問題
輸入：有m個頂點的平麵圖（平麵圖可以放置在平麵上而邊不交叉），任意兩點之間的距離存儲在矩陣D中，即點i到點j的距離為Dij。輸入滿足如下條件:
1) 輸入大小是D的大小n=m2。
2) 最大的Dij是圖的直徑。
3) 點之間的距離對稱且滿足三角不等式。距離對稱意味著i到j的距離等於j到i的距離；滿足三角不等式意味著對於i、j、k來說i到j的距離加上j到k的距離要大於i到k的距離。
輸出：該圖的直徑和距離最大的Dij。
矩陣D可以通過基於動態規劃的Floyd算法得到。本小節關心的不是計算D的算法，而是以這個D為輸入，計算圖的直徑和距離最大的Dij。
計算這個問題一個直觀的想法是把D遍曆一次，從中選擇最大的Dij。但是問題沒那麼簡單，如果要求運行時間為o(n)，也就是運行時間比輸入規模n階低，應如何處理？
是否能做到呢？想精確完成這個問題是不可能的，因為如果有一個“壞人”知道處理過程，由於時間複雜度為o(n)的算法不可能訪問所有的數據，這個“壞人”就讓輸入中沒有訪問到的數據中包含最大的。這樣處理就會令亞線性方法出錯。因而，處理這個問題的時間複雜度應該是O(n)。
本小節將討論一個亞線性的近似算法，這個算法的計算結果可能不是最好的，但是可以計算出一個和原來的結果相差不多的結果。近似算法的動機就是無法在要求的時間內得到精確解，就退而求其次，求出近似的解。
補充知識:近似算法
近似算法主要用來解決優化問題，它不一定能得到最優解但能夠給出一個近似解，最優解和近似解相差很小。
對於一個近似算法來說，問題的每一個可行解都具有一個代價，最優解要求具有最大代價(最大化問題)或最小代價(最小化問題)。近似算法的目的是尋找問題的一個和精確解差距最小的近似解，因此，需要分析近似解代價與最優解代價的差距。通常衡量這種差距有三種測度：第一個測度是近似比，這是最常見的方法；第二個測度是相對誤差；第三個測度是1+ε近似。
首先看近似比的定義，設A是一個優化問題的近似算法,設n是輸入大小,C是A產生的解的代價,C*是最優解的代價。如果maxCC*,C*C≤p(n)，則A具有近似比p(n)。
為了覆蓋最大化問題和最小化問題，在近似比的定義中取C/C*和C*/C中較大者。如果是最大化問題,max{C/C*,C*/C}=C*/C；如果是最小化問題,max{C/C*,C*/C}=C/C*。由於C/C*<1當且僅當C*/C>1,所以近似比不會小於1，等於1就是精確解。近似比越大,近似解越壞，因此近似比越小越好，在算法裏麵如果能將近似比降低，那麼就是算法上的一個貢獻。
另一個常用的測度是相對誤差。對於任意輸入,近似算法的相對誤差定義為C-C*/C*,其中C是近似解的代價,C*是最優解的代價。相應的相對誤差界指的是一個近似算法相對誤差C-C*/C*的上界。
對於一個近似算法，如果其相對誤差界為ε(n)，則稱該算法為1+ε(n)近似算法。
2.平麵圖直徑問題的近似亞線性算法
該算法僅有兩步：第一步，隨機選擇k≤m。第二步，選擇使得Dkl最大的l。也就是說，隨機看算法的一行，在這行中找出最大的值作為直徑。
下麵進行算法的時間複雜度分析，對一個輸入為m×m的矩陣，算法隻需要訪問其中的一行。也就是說輸入是m的平方，而算法隻需訪問其中的m，因此時間複雜度是
讀者會想到上述算法未必得到最優解。確實不一定，但是有了幾個輸入性質的保證，可以證明該算法在最壞情況下與最優解相差很小，下麵的定理說明了這個結論,這意味著即使最壞情況下近似解也不會小於精確解的1/2。
定理2-1 平麵圖直徑問題的亞線性算法的近似比是2。
證明 假設算法的最優解是Dij，那麼根據三角不等式，對於選出的k,有Dij≤Dik+Dkj。因為Dkl是所有Dki中的最大值，因此Dik是小於等於Dkl的，Dkj也是小於等於Dkl的。綜上所述，
因此，Dij小於等於2Dkl，即近似比為2。■
2.1.2 排序鏈表搜索的亞線性算法
排序鏈表搜索問題
輸入：排序雙向有序鏈表R（R中的元素存儲在一個無序的隊列中），元素x。
輸出：如果x在R中，則返回“是”；如果x不在R中，則返回“否”。
問題的目標是確定x是否是輸入中給定的n個元素之一。n個元素存儲在一個雙向鏈表中，意味著每一個鏈表中的元素都可以訪問它的後一個以及前一個元素，但是鏈表不能隨機訪問。表中的元素存放在一個無序隊列中，意味著可以根據元素的索引隨機訪問元素。顯然，通過確定性算法不可能在o(n)時間內完成搜索，然而，如果允許隨機選擇，那麼可以在O(n)時間內完成搜索。
因為R上僅支持順序查找，因而該算法的基本思想是找出一個抽樣，在抽樣中順序查找x所在的小範圍，繼而在R中的此範圍內順序查找x。從R中抽樣S，在抽樣S中找出和x最接近的點p和q，使得x在區間［p,q)之中，接下來僅在R中p和q之間搜索x。由於p和q是以R/n為概率在S中隨機抽樣的點且在S中是相鄰的，因而S中的元素在區間［p,q)的數學期望是nS。從而算法的時間複雜度是O(R+n/R)，為了滿足時間複雜度要求，我們取R=Θ(n),則算法的時間複雜度可以達到O(n)。算法的偽代碼如算法2-1所示。算法2-1 隨機選擇算法Random_search(R,x)
1 從輸入R中等概率地隨機選取Θ(n)個元素，構成集合S。
2 掃描S中所有元素，在O(n)時間內找到最大的p,q∈S，使得p≤x≤q，且滿足S中在p和q之間沒有任何元素。
3 在輸入列表中從p元素開始搜索直到找到x(返回“是”)或者到達q元素(返回“否”)。
定理2-2證明了該算法執行時間的數學期望是O(n)，從而說明了該算法是亞線性算法。
定理2-2 上述算法時間複雜度的數學期望是O(n)。
證明 從算法的過程可以看出，算法的運行時間等於O(n)+(p，q間元素個數)。由於S包含Θ(n)個元素，R中p，q間元素的個數的期望值為O(n/S)=O(n)。這表明算法的期望運行時間為O(n)。■
2.1.3 兩個多邊形交集問題的多項式時間算法
多邊形交集問題
輸入：二維空間中兩個簡單多邊形A和B，每個都包含n個頂點。
輸出：判斷A和B是否相交。這個問題可以在O(n)時間內解決，例如，通過觀察，這個問題可以被描述成一個二維線性規劃實例，在同樣的時間裏，可以找到A,B交集中的一點或者找到一條將A，B分隔的直線，該直線包含A和B中各一個點，參見參考文獻［1］。
下麵我們討論一個能夠達到亞線性的隨機算法。這個算法假設多邊形A和B的頂點以雙向鏈表的形式存儲，每一個頂點都將下一個頂點作為後繼，按照順時針順序排列。算法的偽代碼如算法2-2所示。算法2-2 亞線性多邊形交集算法Intersection(A,B)
1 分別從A，B中等概率隨機選取Θ(n)個頂點的點集CA，CB。
2 在O(n)時間內檢測CA，CB是否相交，如不相交則生成一條將CA和CB分隔的直線L。
3 if CA和CB相交then
4 返回“True”
5 else
6 根據L判斷A和B是否相交
顯然，算法中第1行的時間複雜度為Θ（n），第2行可以利用線性時間多項式相交判定算法實現。下麵討論第6行的實現方法和時間複雜度。
令a和b分別是L上A和B的點，a1和a2是A中和a相鄰的兩個點。我們現在用如下方法定義多邊形PA。如果a1和a2中的點都與CA在L的同一側，那麼PA為空。否則，由於a在L上，a1和a2中隻可能有一個在CA的另一側。不失一般性，設此點為a1。沿著a到a1的方向遍曆A中的點，直到再次通過L，如圖2-1所示。用同樣的方法可以生成PB。則PA和PB的大小為O(n)，這個結論留給讀者證明。
顯然A和B相交當且僅當A和PB相交或者B和PA相交。我們僅考慮B和PA相交的判定，A和PB相交的判定方法類似。首先判定CB和PA是否相交，如果相交，則完成判定。否則，生成CB和PA的分隔線LB(通過上述線性算法完成)。接下來，用上述構造的算法遞歸判定B和PA在LB同一側的子多邊形QB是否和PA相關。於是，B和PA相交當且僅當QB和PA相交。因為QA和PB的期望規模都是O(n)，這個判定可以在O(n)時間完成。根據上述構造，兩個包含n個頂點的多邊形相交性判定問題轉化為常數個多邊形判定問題，每一個的輸入規模都是O(n)，因而，我們有如下結論。
結論2-1 判斷兩個n度凸多邊形的相交可以在O(n)時間內解決。
最後更新：2017-06-21 13:02:05