Re: [問題] 最大流最小費用問題
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/04/03 21:01)推噓0(0推 0噓 0→)留言0則, 0人參與討論串4/5 (看更多)
※ 引述《DJWS (...)》之銘言：
: 然後min cost flow有一些莫名其妙的特例，
這邊就是我很難搞懂的地方
: 例如circulation problem/transportation problem之類的。
: 這些都不是重點，這些只是流量下限為0、supply/demand為0之類的，
: 圖論方式的演算法還是一樣沒變。
: 線性規劃的演算法可能有差一點點，我沒有仔細去研究。
書上大部分都是介紹 min cost circulation problem，因為這可以解其他所有問題。
像是 min-cost max flow 、 min-cost flow 、 transshipment 、 transportation
和 assignment 。
理論上是只要解 transshipment 就可以了，因為他跟 circulation problem 是等價
（線性時間轉換），只是實際上應用有點麻煩。
每類問題自己又有分 有向/無向 、 上下限（正負） 、 cost正負 、
supply/demand 等等變化。
雖然有技巧可以把這些都正規化成有向無上下限且cost皆為正，
但是要記起來挺麻煩的。
而且 把 cost 從負變正 和 無向轉有向 還會互相衝突？？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.167
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1428066102.A.7FA.html
※ 編輯: FRAXIS (129.170.195.167), 04/03/2015 21:03:19
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
