Re: [請益] TWO Shortest Paths

[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)


--
※ 發信站: 批踢踢實業坊(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)
推 ledia:我跟 march 有一樣的猜測... XD
推 march20:又, NP-complete 不代表沒 polynomial
推 march20:time solution, 只是目前不知道有或沒有
推 march20:如果你真的解出來了, 可能性有二
推 march20:1. 你唬爛 2. 準備拿 Turing Award  XD
推 march20:怪了, 怎麼 title 變成怪東西,
推 march20:改回來 @@