Re: [請益] TWO Shortest Paths
看板Prob_Solve (計算數學 Problem Solving)作者march20時間18年前 (2006/06/24 17:05)推噓0(0推 0噓 0→)留言0則, 0人參與討論串9/15 (看更多)
Btw, 這個 reduction 看來不對喔.
※ 引述《yalight (ㄚ光)》之銘言：
: ※ 引述《yalight (ㄚ光)》之銘言：
: : ^^^^^^ S 到 T 才對...囧
: 這問題應該可以 reduce 成 min-cost max-flow problem(更難).
: 但是 min-cost max-flow 有 polynomial solution.
: 所以可以證明這題不是 NP 問題...
: reduce 方法:
vvv 你是說 destination 嗎?
: 就把他想成 source 的 capacity = 2, edge 的 capacity = 1,
^^^^^^ 今天討論的是雙 source 版本
: edge 上的 cost 就是 weight, 的 min-cost max-flow problem。
目前你的 reduction 看來不完整,
來問一個問題就可以知道你的 reduction 是怎麼一回事了.
呃, 找到 max-flow 之後, 試問原題對應的解為何?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.136.254.138
※ 編輯: march20 來自: 71.136.254.138 (06/24 17:08)
※ 編輯: march20 來自: 71.136.254.138 (06/24 17:10)
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
