\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

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]$

狀態轉移式可以寫成這樣
  • $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$的最短路徑
任兩點間的最短路徑可以用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實作:

沒有留言:

張貼留言