PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 最大流最小費用問題

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間9年前 (2015/04/03 23:54)推噓7(7推 0噓 14→)

留言21則, 3人參與討論串5/5 (看更多)

※ 引述《FRAXIS (喔喔)》之銘言： : ※ 引述《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 從負變正和無向轉有向還會互相衝突？？你寫的那些問題，就是我所謂的莫名其妙的特例。我覺得這些問題是冷知識，沒有必要鑽研。事情其實可以很簡單，考慮是st還是循環、 supply/demand 、上下限這三件事情就夠了。最後總是可以用 min cost max st flow 的演算法解決。－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－正規化的方式也很簡單，orlin那本書有介紹。　1. 下限變不見　　　（事先流一些，a supply -k , b supply +k）　2. -cost變成+cost 　　（事先流到滿，residual network完全變反向，　　　　　　　　　　　　（cost就完全變號了。SSPA就有這種情況。）　3. feasible flow變成max st flow （新增st，s連到supply，demand連到t，很直覺。) 只有這三步。很直覺，應該不會太難記。－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－至於無向邊，幾乎沒人討論。因為無向邊必須規定如何流動，這很難搞。例如可以同時雙向對流，又例如只能選擇一個方向流。前者就很智障，不就是來回不斷流來流去，單純衝流量嗎？沒有討論意義。後者的重點，已經不是流的問題了，而是 graph orientation 的問題了。所以沒人想要討論這種奇怪的東西。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.70.154 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1428076497.A.828.html

推

FRAXIS

04/04 00:16, , 1^F

04/04 00:16, 1^F

→

FRAXIS

04/04 00:16, , 2^F

04/04 00:16, 2^F

→

FRAXIS

04/04 00:17, , 3^F

04/04 00:17, 3^F