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

看板Prob_Solve (計算數學 Problem Solving)作者 (...)時間9年前 (2015/04/03 08:51), 9年前編輯推噓1(101)
留言2則, 2人參與, 最新討論串3/5 (看更多)

04/02 15:25,
雖然還沒全懂 似乎是這樣: No negative cycle => Cost'會
04/02 15:25

04/02 15:26,
>=0 ==> 所以可用Dijk所以reduced cost在此變成非負!!
04/02 15:26

04/02 15:27,
又沒有negative cycle跟integer cost就有optimal sol. 故
04/02 15:27

04/02 15:28,
得解...雖然就是各位先進所說的 用我的理解走一遍 ORZ
04/02 15:28

04/02 15:28,
其他有提到的再繼續看.....@-@||
04/02 15:28

04/02 15:30,
(min cost flow跟 min cost max flow有什麼關聯還沒懂..)
04/02 15:30
文獻有兩類,分為 linear programming (大宗) 、圖論算法 combinatorics (極少) 所以要花點時間去轉換那些術語

04/02 22:38,
其實 min cost flow 有很多變化形.. 所以很難搞清楚..
04/02 22:38
其實沒有所謂很多變化形 主要是因為沒有人把它釐清清楚 (至少我看過的資料皆是如此) ------------------------------------- flow問題有兩類 maximum flow (最佳化問題) feasible flow (判定問題) max flow是大家最熟悉的。 CLRS講的就是 max flow,流量越大越好。 feasible flow是判斷是否存在一個流。 通常這類問題會額外設定每條邊的流量下限,不然沒有討論意義(trivial)。 順帶一提,CLRS裡面只講流量上限(就是capacity network)。 ------------------------------------- 流有兩種: st flow (有起點終點) flow (一直循環的) st flow 很經典,在 CLRS 上面介紹的就是 st flow。 st代表source/target,從起點流動到終點,有頭有尾。 通常這類問題只要設定流量上限,就有討論意義了。 如果想讓事情更複雜,可以設定下限,甚至推廣成負數。 flow 在線性規劃、或者進階的演算法課程,才會談。 沒有起點終點,水會不斷的循環流動。 通常這類問題會設定流量上限下限、supply/demand,不然沒有討論意義。 ------------------------------------- 前面2x2種排列組合,一共得到四種問題。 但是只有這兩個問題比較有討論意義,其他都不重要。 max st flow  (文獻常省略st,因為古人沒搞清楚。) feasible flow 引入了cost之後,就是先前文章提到的: min cost max st flow  (文獻常省略st,因為古人沒搞清楚。) min cost feasible flow (文獻常省略feasible,依命名慣例。) min cost max st flow在tarjan的書上有介紹一點點。 需要證明的是:cost network的最短路徑,以最少的方式增加,最終得到最佳解。 min cost flow在orlin的書上介紹的很詳細。 網路上的資料幾乎都是抄他的。 然後min cost flow有一些莫名其妙的特例, 例如circulation problem/transportation problem之類的。 這些都不是重點,這些只是流量下限為0、supply/demand為0之類的, 圖論方式的演算法還是一樣沒變。 線性規劃的演算法可能有差一點點,我沒有仔細去研究。 ------------------------------------- 再來談 reduction 學過 NP-complete 之後,我們知道問題可以互相變來變去,用一個問題解另一個問題 考慮前面提到的 2x2=4 個問題 maximum flow (沒辦法定義何謂max) (我們不討論它) --------------------------------------------------------------- feasible st flow -> feasible flow (拉一條邊從t到s) -> maximum st flow (1. 流量下限挪至supply/demand) (2. 建立s和t,s連到supply,demand連到t) 上面的問題,可以用下面的解。 引入了cost之後也一樣是這個順序。 所以最重要的其實是 min cost max st flow 的演算法。 只是 orlin 完全沒提。又因為網路上的資料都是抄 orlin 的,所以...... --------------------------------------- 再來才是真的變化形 0/1 flow minimax flow b-flow multi-commodity flow 這都很噁心,一般學生根本就不會想碰。我自己也沒有研究。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.61.177 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1428022308.A.4B7.html ※ 編輯: DJWS (111.250.61.177), 04/03/2015 09:09:34 ※ 編輯: DJWS (111.250.61.177), 04/03/2015 09:17:03 ※ 編輯: DJWS (111.250.61.177), 04/03/2015 09:19:39 ※ 編輯: DJWS (111.250.61.177), 04/03/2015 09:20:08 ※ 編輯: DJWS (111.250.68.64), 04/03/2015 13:17:21

04/06 22:07, , 1F
感謝 持續研究中 @-@
04/06 22:07, 1F

04/07 06:28, , 2F
加油!
04/07 06:28, 2F
文章代碼(AID): #1L7UGaIt (Prob_Solve)
文章代碼(AID): #1L7UGaIt (Prob_Solve)