※ 引述《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) 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.245.92 ※ 编辑: march20 来自: 71.136.245.92 (06/25 04:18) ※ 编辑: march20 来自: 71.136.245.92 (06/25 04:19)