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

Re: [請益] TWO Shortest Paths

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

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

※ 引述《march20 ()》之銘言： : ※ 引述《ericbibo (^^)》之銘言： : <略> : : 可是，假如我現在把題目改成: : : 找"兩條"沒有重疊的minimum weight shortest paths， : : 一條由給定的起點 S1 到終點 D1， : : 另一條由起點 S2 到終點 D2 的話， : : 有沒有什麼方法可以解決這個問題呢? : : 我已經想這個問題好幾天了， : : 希望高手能不吝指教一下~ XD : <略> : : 推 march20:可以走到一樣的點, 但不能走相同的 edge 71.136.225.150 06/23 04:05 : : 推 march20:是這樣嗎? 71.136.225.150 06/23 04:05 : : 推 ericbibo:是的...你得到它了 ^_^ 59.104.152.115 06/23 12:04 : : 推 march20:有點懷疑這是 NP-hard problem 71.136.254.138 06/24 14:07 : 如果連點都不能重複, 找 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.245.92 ※ 編輯: march20 來自: 71.136.245.92 (06/25 04:18) ※ 編輯: march20 來自: 71.136.245.92 (06/25 04:19)