PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] TWO Shortest Paths

看板Prob_Solve (計算數學 Problem Solving)作者march20時間18年前 (2006/06/25 14:42)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串14/15 (看更多)

OK, 我搞笑了, 書沒看仔細 XD #PATH=2 時 disjoint connecting paths 是有 polynomial time solution 的 XD 以下是書上給的 reference, http://historical.ncstrl.org/litesite-data/stan/CS-TR-78-654.pdf 所以這個 reduction 無用 XD 至於原題嘛, 有點複雜. undirected version 我還沒查到. 但 directed version 依然是 NP-hard (因為是 NP, 所以也是 NP-complete) 上 google 找 disjoint edge paths 可以查到, 比如以下文章的第二頁: http://0rz.net/d31yz.. 可以知道特例 s1=s,t1=t, s2=t, t2=s 時已經是 NP-hard 了那麼原題更加是不用說了. ※ 引述《march20 ()》之銘言： : ※ 引述《march20 ()》之銘言： : : <略> : : <略> : : 如果連點都不能重複, 找 disjoint connecting paths (甚至還不是 shortest) : : 這個問題會變成 NP-complete. : : 請參閱 : : Computers and Intractability: A Guide to the Theory of NP-Completeness : : by Michael R. Garey, David S. Johnson. (Page 217) : : (如果你是學 theory 的, 這本可是必備工具書, 專門查 NP-Completeness 用的 XD) : : 如果點可以重複, 嗯, 目前不知道, 但我猜是 NP-Complete : : (看吧, 果然用到 computation theory 了吧 XD) : ok, 找到一個方法可以把 disjoint connecting paths (#path = 2) : reduce 成 two paths shortest path. : 簡單來說, 把單一點變成兩個, 中間加一條 edge 即可: : 對每個 node x, 以 x_i, x_o 取代, : 對每個 (a, x), 以 (a, x_i) 取代 : 對每個 (x, b), 以 (x_o, b) 最代 : 再加入 (x_i, x_o). : 這樣就可以用 two paths shortest path 來解 disjoint connecting paths (#path=2) : 但已知 disjoint connecting path (for #path =2) 為 NP-complete, : 所以這個問題是 NP-hard. : 又這問題是 NP (i.e. polynomial time verifiable, 不想寫出來 XD) : 所以是 NP-complete -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 71.136.229.208 ※ 編輯: march20 來自: 71.136.229.208 (06/25 14:49) ※ 編輯: march20 來自: 71.136.229.208 (06/25 14:49) ※ 編輯: march20 來自: 71.136.229.208 (06/25 14:53)