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數位生活區 即時熱門文章
