作者march20 ()
看板Prob_Solve
標題Re: [請益] TWO Shortest Paths
時間Sun Jun 25 04:12:32 2006
※ 引述《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
: 所以是 NP-complete
還少做一件事: 把 destination 點做處理.
不然會有 中途經過 destination 點的問題.
簡單來說, 若 t1, t2 為 destination 點,
得把 (t1, x), (t2, x) 這種 edges 去掉.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.136.245.92
※ 編輯: march20 來自: 71.136.245.92 (06/25 04:12)