作者march20 ()
看板Prob_Solve
标题Re: [请益] TWO Shortest Paths
时间Sun Jun 25 14:45:53 2006
OK, 我搞笑了, 书没看仔细 XD
#PATH=2 时 disjoint connecting paths 是有 polynomial time solution 的 XD
以下是书上给的 reference,
http://historical.ncstrl.org/litesite-data/stan/CS-TR-78-654.pdf
所以这个 reduction 无用 XD
至於原题嘛, 有点复杂. undirected version 我还没查到.
但 directed version 依然是 NP-hard (因为是 NP, 所以也是 NP-complete)
上 google 找 disjoint edge paths 可以查到,
比如以下文章的第二页:
http://0rz.net/d31yz..
可以知道特例 s1=s,t1=t, s2=t, t2=s 时已经是 NP-hard 了
那麽原题更加是不用说了.
※ 引述《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 (i.e. polynomial time verifiable, 不想写出来 XD)
: 所以是 NP-complete
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 71.136.229.208
※ 编辑: march20 来自: 71.136.229.208 (06/25 14:49)
※ 编辑: march20 来自: 71.136.229.208 (06/25 14:49)
※ 编辑: march20 来自: 71.136.229.208 (06/25 14:53)