以前覺得這應該是很簡單的東西，但我發現網路上使用priority_queue的prim演算法相關程式碼我覺得寫不好，我就把我自己的放上來。這裡順便也放上kruskal的程式碼。
prim $\ord{\left(\abs{V}+\abs{E}\right)\log{\abs{V}}}$:
kruskal $\ord{\abs{V}+\abs{E}\log{\abs{E}}}$:
2019年8月1日 星期四
2019年1月29日 星期二
[ Delaunay Triangulation ] Delaunay 三角剖分
先來說說甚麼是三角剖分 Triangulation 吧！假設平面上散布很多不重複的點，現在用一些線段將這些點連成許多的三角形，滿足所有三角形的內部不會有其他點，而且三角形的數量越多越好，這就是一個三角剖分。
Delaunay Triangulation是一種特殊的三角剖分，滿足所有的三角形其外接圓中不會出現其他的點，這樣的性質會使得所有三角形中最小的角盡量大，而且最重要的是它是 Voronoi Diagram 的對偶圖，Voronoi Diagram 直接求的話很容易有浮點誤差而且程式也不好寫，因此從Delaunay Triangulation直接轉換過去會更加方便。
還有一個很重要的點，透過Delaunay Triangulation 的邊集合可以找出平面歐幾里得距離最小生成樹。
這裡我先給出點的資料結構，方便接下來的講解：
一般來說找出 Delaunay Triangulation 的其中一個操作是要判斷一個點是不是在一個三角形的外接圓內，但直接去求外接圓圓心會有浮點誤差，因此有一個作法是將所有點投影到三維的拋物線曲面中，也就是下圖的碗狀曲面，會發現把一個圓投影上去之後，該圓會落在一個平面上，圓內的點會在平面下面，圓外的點會在平面上面，這樣就可以利用一些處理三維幾何的技術就可以避免浮點誤差的判斷點是否在外接圓內了。
範例程式碼中點在圓內輸出1，圓外輸出-1，圓上輸出0：
當然實作時並不會真正的寫一個三維點的資料結構，這樣程式碼會比較長。
Delaunay Triangulation 我所知道的有兩種，分別是隨機增量法以及分治法。隨機增量法再點隨機加入的時候複雜度是$\ord{n\log n}$，分治法則是穩定$\ord{n\log n}$，但我的實作分治法的效能是隨機增量法的三倍快。由於兩種做法都已經有詳細教學了這裡就不用文字敘述。
- 隨機增量法教學在《Computational Geometry - Algorithms and Applications》書中有提到，該書有中文版
- 分治法教學請點該網站連結
隨機增量法：
分治法：
2017年4月30日 星期日
[ Steiner tree problem in graphs ] 斯坦納樹
斯坦納樹問題是一個世界知名的NP-hard問題。在圖論上的斯坦納樹是對於一張無向圖$G=(V,E)$以及一個點集合$P \subseteq V$，通常會稱$P$集合為$terminal \; set$，對於每條邊$e=(u,v) \in E$，令$w(e)$表示它的權重。我們的目標是要從$G$的所有子圖中找出一棵生成樹$T=(V',E')$，使得$P \subseteq V'$且$\sum_{e \in E'} w(e)$最小。
簡單來說就是在圖$G$上找一棵子樹，可以把$P$中的點連通起來，且邊權總和最小
如果我們枚舉所有子圖，對每個子圖做最小生成樹演算法，就一定可以找到斯坦納樹，但是複雜度是$\ord{(\abs E + \abs V log \abs V ) \times 2^{\abs V}}$，非常糟糕。
如果$w(e)>0 ,e \in E$，且$\abs P \ll \abs V$，我們可以找到一個動態規劃的方法：
令$dp[S][i]$表示以點$i$為根，以$S \subseteq P$為$terminal \; set$構造出來的斯坦納樹，這樣我們最後的答案就會是$dp[P][u \in P]$
狀態轉移式可以寫成這樣
任兩點間的最短路徑可以用floyd在$\ord {\abs V^3}$預先算出來，狀態有$2^{\abs P}\times \abs V$個，狀態轉移為$\ord{\abs V \times 枚舉子集合的時間}$，因此總複雜度為$\ord{\abs V^3+2^{\abs P} \times \abs V^2 \times 枚舉子集合的時間 }$
其中 $2^{\abs P} \times 枚舉子集合的時間$ 只是粗略的計算，實際上它是
$$\sum_{i=1}^{\abs P} \binom{\abs P}{i} \times (2^i -1) \simeq \sum_{i=0}^{\abs P} \binom{\abs P}{i} \times 2^i = (1+2)^{\abs P} = 3^{\abs P}$$因此總複雜度可以表示為$\ord{V^3+3^{\abs P} \times \abs V^2}$，但是這其實還可以優化，令$H[j] = min(dp[T][j]+dp[S-T][j] \; : \;T \subset S)$
則$dp[S][i]=min(H[j]+dis(i,j)\; : \;j \in \abs V)$
$H$是可以被預先算出來的，因此總複雜度就降為$\ord{\abs V^3 + \abs V 3^{\abs P}+\abs V^2 2^{\abs P}}$
以下附上程式碼:
有的時候圖是稀疏圖，也就是$\ord V=\ord E$，這種時候用這種算法效率其實不是很好，我們可以在dp的過程才用一些單源最短路徑算法算出最短路徑，這樣複雜度可以變成$$\ord{\abs V 3^{\abs P}+ShortestPath(G) 2^{\abs P}}$$其中$ShortestPath(G)$是在圖$G$中計算最短路徑的時間，用dijkstra的話是$\ord{\abs E+\abs V log \abs V}$，這裡我用SPFA實作:
簡單來說就是在圖$G$上找一棵子樹，可以把$P$中的點連通起來，且邊權總和最小
如果我們枚舉所有子圖，對每個子圖做最小生成樹演算法，就一定可以找到斯坦納樹，但是複雜度是$\ord{(\abs E + \abs V log \abs V ) \times 2^{\abs V}}$，非常糟糕。
如果$w(e)>0 ,e \in E$，且$\abs P \ll \abs V$，我們可以找到一個動態規劃的方法：
令$dp[S][i]$表示以點$i$為根，以$S \subseteq P$為$terminal \; set$構造出來的斯坦納樹，這樣我們最後的答案就會是$dp[P][u \in P]$
狀態轉移式可以寫成這樣
- $dp[S][i]=min(dp[T][j]+dp[S-T][j]+dis(i,j)\; : \; j \in V,T \subset S)$
$dis(i,j)$表示$i \sim j$的最短路徑
其中 $2^{\abs P} \times 枚舉子集合的時間$ 只是粗略的計算，實際上它是
$$\sum_{i=1}^{\abs P} \binom{\abs P}{i} \times (2^i -1) \simeq \sum_{i=0}^{\abs P} \binom{\abs P}{i} \times 2^i = (1+2)^{\abs P} = 3^{\abs P}$$因此總複雜度可以表示為$\ord{V^3+3^{\abs P} \times \abs V^2}$，但是這其實還可以優化，令$H[j] = min(dp[T][j]+dp[S-T][j] \; : \;T \subset S)$
則$dp[S][i]=min(H[j]+dis(i,j)\; : \;j \in \abs V)$
$H$是可以被預先算出來的，因此總複雜度就降為$\ord{\abs V^3 + \abs V 3^{\abs P}+\abs V^2 2^{\abs P}}$
以下附上程式碼:
有的時候圖是稀疏圖，也就是$\ord V=\ord E$，這種時候用這種算法效率其實不是很好，我們可以在dp的過程才用一些單源最短路徑算法算出最短路徑，這樣複雜度可以變成$$\ord{\abs V 3^{\abs P}+ShortestPath(G) 2^{\abs P}}$$其中$ShortestPath(G)$是在圖$G$中計算最短路徑的時間，用dijkstra的話是$\ord{\abs E+\abs V log \abs V}$，這裡我用SPFA實作:
2017年2月7日 星期二
[ Minimum Arborescence / zhu_liu ] 朱劉算法 - 最小樹形圖
在有向圖中，給定一個點$r$作為生成樹的根，找出有向圖最小生成樹。
首先我們要能保證從$r$能夠走到圖上的所有點，這樣生成樹才會存在，這很簡單，一次DFS即可，再來是把圖上的所有自環移除，因為一顆樹裡面很明顯是不會有自環的。
之後就是算法的主要步驟了，可以先想一下，除了$r$以外的每一個點都有一條儘可能小的邊指向自己，最好的情況就是我們枚舉每一個點（除了根節點）並找到最小的一條指向這個點的邊，如果這些邊不構成有向環，就形成了一個所求的最小樹形圖。
但是實際上會出現環啊，但是這些環一定是獨立的，為甚麼呢？因為只有$|V|-1$條邊啊，只有是一棵樹的時候才會是連通的狀態。換句話說，如果圖連通了，就一定是最小樹形圖。
我們嘗試去換一些邊，使圖連通，在換的過程中我們總是選擇較小的邊，那麼得到的就是最小樹形圖。你可能會去枚舉一些邊把有向環拆掉，但是這樣的話可能會產生新的有向環，不是一個好做法。
朱劉算法就不直接去換邊，它也不去拆掉環，而是在不增加邊的情況下讓圖連通，怎麼做呢？就是用一個新的點代替原來圖的一個環（也就是所謂的「縮點」，和強連通分量有點像），並且修改跟這個環裡的點有關的邊的權值。
為何要修改邊的權重呢？當我們每更換一個點的入邊的時候我們就要去掉原來那個入邊，於是我們把這個點所有可能的入邊全部減少原來選取的那個入邊的權值，這樣每增加一條入邊無形中就刪去了原來那條邊。
可以發現修改邊權後，不需要把邊刪掉，直接去計算選取邊的權重和就會和換邊的結果一樣
朱劉算法主算法的過程就是：找最小入邊->判斷有沒有環(沒有環就退出，算法成功)->縮點，改權值，如此反覆，一般來說為了方便不會去記錄縮點後虛擬節點裡包含了那些點，如果需要找出最小樹形圖包含的邊，就必須要真的去記錄他。
時間複雜度來說的話，用當時論文提出的實作方式，修改邊權的部分為$\ord{|E|}$，縮點最多執行$|V|-1$次，所以總複雜度是$\ord{|V|*|E|}$。
我自己有想了一個$\ord{|E| \; log \; |E|}$的方法，需要用到一種可以合併和把裡面所有元素加上某個值 的heap，又因為每個點最多只會連出去$|V|-1$條邊，也就是heap裡面只有$|V|$個元素是有用的，所以可以在heap大小為$2|V|$時把後$|V|$個元素刪掉，用斐式堆可以做到$\ord{|E|+|V| \; log|V|}$。
以下為$\ord{|V|*|E|}$的code:
接著是$\ord{|E| \; log^2|E|}$的code，使用啟發式合併(感謝59491、編譯器幫忙debug):
接著是$\ord{|E| \; log|E|}$的code，使用skew heap:
首先我們要能保證從$r$能夠走到圖上的所有點，這樣生成樹才會存在，這很簡單，一次DFS即可，再來是把圖上的所有自環移除，因為一顆樹裡面很明顯是不會有自環的。
之後就是算法的主要步驟了，可以先想一下，除了$r$以外的每一個點都有一條儘可能小的邊指向自己，最好的情況就是我們枚舉每一個點（除了根節點）並找到最小的一條指向這個點的邊，如果這些邊不構成有向環，就形成了一個所求的最小樹形圖。
但是實際上會出現環啊，但是這些環一定是獨立的，為甚麼呢？因為只有$|V|-1$條邊啊，只有是一棵樹的時候才會是連通的狀態。換句話說，如果圖連通了，就一定是最小樹形圖。
我們嘗試去換一些邊，使圖連通，在換的過程中我們總是選擇較小的邊，那麼得到的就是最小樹形圖。你可能會去枚舉一些邊把有向環拆掉，但是這樣的話可能會產生新的有向環，不是一個好做法。
朱劉算法就不直接去換邊，它也不去拆掉環，而是在不增加邊的情況下讓圖連通，怎麼做呢？就是用一個新的點代替原來圖的一個環（也就是所謂的「縮點」，和強連通分量有點像），並且修改跟這個環裡的點有關的邊的權值。
為何要修改邊的權重呢？當我們每更換一個點的入邊的時候我們就要去掉原來那個入邊，於是我們把這個點所有可能的入邊全部減少原來選取的那個入邊的權值，這樣每增加一條入邊無形中就刪去了原來那條邊。
上圖中紅色部分是要進行縮點的有向環
每個環上的點所有可能的入邊全部減少原來選取的那個入邊的權值
接著把環縮成一個點就可以了
假設我們想要把原來縮環之前3那條邊換成4那條邊，那我們換完的結果如下:
時間複雜度來說的話，用當時論文提出的實作方式，修改邊權的部分為$\ord{|E|}$，縮點最多執行$|V|-1$次，所以總複雜度是$\ord{|V|*|E|}$。
我自己有想了一個$\ord{|E| \; log \; |E|}$的方法，需要用到一種可以合併和把裡面所有元素加上某個值 的heap，又因為每個點最多只會連出去$|V|-1$條邊，也就是heap裡面只有$|V|$個元素是有用的，所以可以在heap大小為$2|V|$時把後$|V|$個元素刪掉，用斐式堆可以做到$\ord{|E|+|V| \; log|V|}$。
以下為$\ord{|V|*|E|}$的code:
接著是$\ord{|E| \; log^2|E|}$的code，使用啟發式合併(感謝59491、編譯器幫忙debug):
接著是$\ord{|E| \; log|E|}$的code，使用skew heap:
訂閱：
文章 (Atom)