Re: [問題] 最大流最小費用問題
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間9年前 (2015/04/03 08:51)推噓1(1推 0噓 1→)留言2則, 2人參與討論串3/5 (看更多)
→
04/02 15:25,
04/02 15:25
→
04/02 15:26,
04/02 15:26
→
04/02 15:27,
04/02 15:27
→
04/02 15:28,
04/02 15:28
→
04/02 15:28,
04/02 15:28
→
04/02 15:30,
04/02 15:30
文獻有兩類,分為 linear programming (大宗) 、圖論算法 combinatorics (極少)
所以要花點時間去轉換那些術語
推
04/02 22:38,
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
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章