作者march20 ()
看板Prob_Solve
标题Re: [请益] TWO Shortest Paths
时间Sat Jun 24 15:42:44 2006
※ 引述《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)
1F：推 ledia:我跟 march 有一样的猜测... XD 140.112.30.56 06/24 15:59
2F：推 march20:又, NP-complete 不代表没 polynomial 71.136.254.138 06/24 16:31
3F：推 march20:time solution, 只是目前不知道有或没有 71.136.254.138 06/24 16:31
4F：推 march20:如果你真的解出来了, 可能性有二 71.136.254.138 06/24 16:32
5F：推 march20:1. 你唬烂 2. 准备拿 Turing Award XD 71.136.254.138 06/24 16:33
6F：推 march20:怪了, 怎麽 title 变成怪东西, 71.136.245.92 06/25 01:11
7F：推 march20:改回来 @@ 71.136.245.92 06/25 01:12