Re: [請益] TWO Shortest Paths
看板Prob_Solve (計算數學 Problem Solving)作者march20時間18年前 (2006/06/24 15:38)推噓7(7推 0噓 0→)留言7則, 2人參與討論串7/15 (看更多)
※ 引述《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)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.136.254.138
※ 編輯: march20 來自: 71.136.254.138 (06/24 15:43)
※ 編輯: march20 來自: 71.136.254.138 (06/24 15:44)
※ 編輯: march20 來自: 71.136.254.138 (06/24 15:44)
※ 編輯: march20 來自: 71.136.254.138 (06/24 15:47)
※ 編輯: march20 來自: 71.136.254.138 (06/24 15:48)
推
06/24 15:59, , 1F
06/24 15:59, 1F
推
06/24 16:31, , 2F
06/24 16:31, 2F
推
06/24 16:31, , 3F
06/24 16:31, 3F
推
06/24 16:32, , 4F
06/24 16:32, 4F
推
06/24 16:33, , 5F
06/24 16:33, 5F
推
06/25 01:11, , 6F
06/25 01:11, 6F
推
06/25 01:12, , 7F
06/25 01:12, 7F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
