這 title 是來自一篇 paper [1]，主要是探討如何在 O(n log n) 的時間內找出一顆 minimum spanning tree (MST)。等等，找 MST 這問題不是已經有許多方法可以用 greedy 的技巧在 O(n log n) 做到了嗎? 那這篇發表日期還是在 2001 年的 paper 是有何貢獻呢？原因是這樣的：傳統的 MST 演算法跟這篇要討論的問題其實有一點不同。不同的地方在於傳統 MST 演算法是給一個 undirected graph，要在這 graph 上找一顆 MST；這篇要討論的是給一堆二維座標平面上的點，任兩點間都可以用一條線連起來，要你找出一種連法使得所有的點都被連起來，並且線段總長是最短的。
這個問題其實也有一段時間了，正式的名稱是 Euclidean Minimum Spanning Tree (EMST) [2]。這問題最簡單的做法就是把每個座標點都當成 vertex，先建出一個 complete graph，edge 上的 weight 就是兩點間距離，然後在這個 complete graph 上找 MST 就是答案了。想當然爾，建 complete graph 的時間是 O(n^2)，所以這做法最花時間的地方是建 graph。因此 EMST 的演算法要討論的重點不是 MST，而是怎樣建 graph 最好。
一般常見 EMST 的解法是利用 Delaunay Triangulation 建 graph [2]，因為用這方法建出來的 graph 是個 planar graph，而 planar graph 有個良好的特性是 |E| <= 3 * |V| - 6，其中 |E| 是 edge 的數量、|V| 是 vertex 的數量。而 Delaunay Triangulation 可以利用 Divide and Conquer 在 O(n log n) 內做到，所以整體演算法的複雜度可以控制在 O(n log n)。
以上是一般的解法XD 我這次要面對的 MST 稍微有些不同：距離的計算方式不是 Euclidean distance，而是 Manhattan distance。[1] 這篇 paper 有提到了 Delaunay Triangulation 建 graph 的做法在距離是用 Manhattan distance 來計算的情形下會失準，而且 Delaunay Triangulation 實作起來其實頗麻煩的，因此這篇 paper 主要就是提出一個新的建 graph 的方式，建出來的 graph 他們稱做 Rectilinear Spanning Graph (RSG)，他們宣稱不但 RSG 的 edge 數比起其他演算法來的更少、實作起來也較簡單。原始的 paper 中(註1)有實作三種方法加以比較 (註2)，證實他們的方法確實是更好。接下來簡單講解這篇的概念：
給定一個點 t，作者先以這個點為原點把整個座標平面分成 8 區 (paper 中的 fig. 2)，接著在每一區中都找出一個距離 t 最近的點 s，然後只把 s 跟 t 建 edge。對每個點都做一次相同的事情，這樣就可以確保建出來的 graph 至少含有一個 spanning tree。另外由於分割後的平面有對稱性的關係，因此只要先把這些座標點由小到大排序，接下來依照順序取出一個點，找出 t 右半平面的 4 個區域中距離 t 最近的點就好了。以 paper 中的 fig. 3 來說，每個點 t 都只要找 R1 ~ R4 這 4 個區域裡距離 t 最近的點即可，R5 ~ R8 會因為對稱性的關係，若有一個點 s 位在 t 的 R5 ~ R8 這 4 個區域，則 p 必在 s 的 R1 ~ R4 這 4 個區域。因此整個演算法的核心是在怎麼找出 R1 ~ R4 這些區域中各自離 s 最近的點是哪個點?
先從 R1 開始：
首先先把所有的座標點依據 x + y 由小到大做排序，然後建立一個 active set，裡面存的是 R1 區域裡還沒有其他座標點的座標點 (一開始是空的)。接著從小到大一次取出一個點 s，找找看 active set 中有沒有哪個點 t 滿足 s 位在 t 的 R1 中。若存在這樣的點，就把 s 跟 t 建一條 edge，然後把 t 從 active set 中刪掉。接著不論有沒有找到這樣的 t，都把 s 加入 active set 中。很明顯的，在 active set 中找出這樣的 t 會決定整個演算法的時間複雜度，對此，作者提出的作法如下：
假設 s 在 t 的 R1 裡，則 t 跟 s 滿足下列條件 (註3)：
$$
\left\{
\begin{array}{1}
x_t \leq x_s \\
x_t - y_t > x_s - y_s
\end{array}
\right .
$$
又因為 active set 裡的任意兩點互相不會落在對方的 R1 中，因此有個良好的性質可以用 (paper 中的 Lemma 3)：
若 $x_p \neq x_q$ 且 $x_p < x_q$，則 $x_p - y_p \leq x_q - y_q$
因此給定一個點 s，先把 active set 中的點依照 x 座標做排序，接著找出一個點 (x, y) 滿足 $x \leq x_s$，然後依照 x 座標遞減的順序依序抓出一個點，直到 $x - y \leq x_s - y_s$，找出這之中滿足 s 在其 R1 中且距離 s 最近的點 t。
這邊有一個關鍵：當然不會是每次要找 t 的時後都對 active set 做排序，取而代之的，作者提出的方法是用 binary search tree (BST，註4) 來儲存 active set，這樣每次的 query time 就可以在 O(log n) 內完成，同理，insert 跟 delete 也是。(註5)
同樣的方法可以套用在 R2 ~ R4，分析如下：
對 R2 而言：
假設 s 在 t 的 R2 裡，則 t 跟 s 滿足下列條件：
$$
\left\{
\begin{array}{1}
y_t < y_s \\
x_t - y_t \leq x_s - y_s
\end{array}
\right .
$$
active set 中的任意兩點滿足：
$y_p \leq y_q$ 則 $x_p - y_p > x_q - y_q$
當給定一個點 s ，要找 active set 中距離 s 最近的 t 且 s 在 t 的 R2 中，我們先把 active set 針對 y 座標做排序，接著找出一個點 (x, y) 滿足 $y < y_s$，然後依照 y 座標遞減的順序依序抓出一個點，直到 $x - y > x_s - y_s$，找出這之中滿足 s 在其 R2 中且距離 s 最近的點 t。
對 R3 而言：
假設 s 在 t 的 R3 裡，則 t 跟 s 滿足下列條件：
$$
\left\{
\begin{array}{1}
y_t \geq y_s \\
x_t + y_t < x_s + y_s
\end{array}
\right .
$$
active set 中的任意兩點滿足：
$ y_p < y_q $ 則 $ x_p + y_p > x_q + y_q$
當給定一個點 s ，要找 active set 中距離 s 最近的 t 且 s 在 t 的 R3 中，我們先把 active set 針對 y 座標做排序，接著找出一個點 (x, y) 滿足 $y \geq y_s$，然後依照 y 座標遞增的順序依序抓出一個點，直到 $x + y \geq x_s + y_s$，找出這之中滿足 s 在其 R3 中且距離 s 最近的點 t。
對 R4 而言：
假設 s 在 t 的 R4 裡，則 t 跟 s 滿足下列條件：
$$
\left\{
\begin{array}{1}
x_t < x_s \\
x_t + y_t \geq x_s + y_s
\end{array}
\right .
$$
active set 中的任意兩點滿足：
$x_p < x_q$ 則 $x_p + y_p \leq x_q + y_q$
當 給定一個點 s ，要找 active set 中距離 s 最近的 t 且 s 在 t 的 R4 中，我們先把 active set 針對 x 座標做排序，接著找出一個點 (x, y) 滿足 $x < x_s$，然後依照 x 座標遞減的順序依序抓出一個點，直到 $x + y < x_s + y_s$，找出這之中滿足 s 在其 R4 中且距離 s 最近的點 t。
=================== 我是分隔線 ===================
到了這裡就把整篇的概念解釋完了，希望各位沒有頭昏眼花XDD
我實作版本如下，不過現在懶得作優化，哪天有閒有心情再來修改XD
1. value_type extraction (這是這一篇提到的東西)
2. disjoint set (會用到的資料結構)
3. MST (我是實作 Kruskal's algorithm)
4. BST (我懶得做 balance ~XD)
5. RSG (在座標點不多的情形下，直接建 complete graph 反而比較好)
註釋：
註1. 原始的 paper 下載點是 [3]，但是 ACM Digital Library 的檔案要學術網路才有辦法下載，而且 [1] 其實有少了一點東西，不過要免費下載的就請乖乖下載 [1] 這一份吧XD
註2. 有寫過論文的人都知道其實這是執行時間這種事情是可以偷雞摸狗的XD 比方說故意用比較糟的方式來實作別人的演算法之類的~ 不過建出來的 graph edge 數比較少倒是真的，這點對於找 MST 還是有相當大的好處。
註3. [3] 相對應的式子是錯的，[1] 裡寫的才是對的
註4. 一般的 binary search tree (BST) 可能會有 skew 的問題，所以如果希望 query time 可以穩定在 O(log n) 的話，要記得對 BST 做 balance，或者是用其他資料結構。
註5. 這邊其實我覺得作者的講法怪怪的，因為演算法中要找的是 active set 中的一組 subset，所以 query 其實要做好幾次，這樣是否還是可以達到 O(log n) 其實我有點疑惑，不過我懶的做 amortize analysis，所以就先算了XD
Reference:
[1] http://www.ece.northwestern.edu/~haizhou/publications/zhou02ipl.pdf
[2] http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
[3] http://dl.acm.org/citation.cfm?id=370320&dl=ACM&coll=DL&CFID=524455729&CFTOKEN=70049574
沒有留言:
張貼留言