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

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

看板Prob_Solve (計算數學 Problem Solving)作者 (...)時間9年前 (2015/03/29 10:11), 編輯推噓4(4推 0噓 40→)
留言44則, 3人參與, 最新討論串2/5 (看更多)
※ 引述《saladim (殺拉頂)》之銘言： : : 中文 最小費用最大流 : : 英文 minimum cost maximum s-t flow 古代文獻經常省略s-t : : 我猜你看到的是 中文 最小費用流 的SSPA演算法。那是不一樣的主題。 : : 英文 minimum cost flow : http://perso.ens-lyon.fr/eric.thierry/Graphes2010/amaury-pouly.pdf : 我看的是這個, 就是因為如同內文提到, 這提可以用另一種解法, 就想說一起看看證明 : 是長什麼樣子, 沒想到不只樣子有差, 連要怎麼轉化都有點疑惑. 跟我猜的一樣，你看的這篇標題就寫著 minimum cost flow 啊。 不一樣的兩個問題，無論你怎麼轉化都轉不過去。 : 另一種解法在UVA 的forum還有一個本質相同 但是我想是另一種變形的方式, : 另外看不出來cost在每個iteration有變化是因為每個arc的e.cost並沒有變化阿? : ( http://mycodebattle.com/2014/10/UVa-10806/ ) int u = ed; while (u != st) { edges[p[u]].flow += a[ed]; edges[p[u] ^ 1].flow -= a[ed]; u = edges[p[u]].from; } return true; 剩餘容量變了，圖上多出許多反方向的邊，也就是負的cost的邊。 : 這邊指的cost是指走過arc的cost, 而不是total cost. 這也是理論裡面說每個 : iteration需要變化的地方 所以我想是哪裡理解錯誤吧? 你看的文獻就不對，要怎麼跟你討論？ 但是你說的大致上是正確的， 無論是　最小費用流　還是　最小費用最大流　的SSPA都是如此。 : 另外我還會去看一下 最小費用流 跟 最小費用最大流的差別 ORZ 建議你找英文的資料，因為中文網路上幾乎沒有人把這件事搞清楚，尤其是競賽選手。 圖論算法強者tarjan有寫一本網路流的書， 它裡面有稍微提到 minimum cost maximum flow， 可以加減參考看看。 https://books.google.com.tw/books?id=m1rAB3uWwBwC : 懇請解惑~~ : 謝謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.80.89 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1427595099.A.01F.html
→
03/29 21:25, , 1F
剩餘容量變了 會影響cost嗎? 邊一開始就建好了 後面不會
03/29 21:25, 1F
→
03/29 21:25, , 2F
增加跟減少了吧?
03/29 21:25, 2F
→
03/29 21:27, , 3F
我指的是那篇blog的實作方式.....
03/29 21:27, 3F
→
03/29 23:16, , 4F
本來沒有反方向的邊，後來有了，也就連帶產生-cost
03/29 23:16, 4F
→
03/29 23:17, , 5F
他的實作方式是預先都建好反方向的邊 用xor 1得到反方向的
03/29 23:17, 5F
→
03/29 23:18, , 6F
邊 然後一開始就設定好+cost和-cost 所以他其實還是有變
03/29 23:18, 6F
→
03/29 23:18, , 7F
只是一開始就把所有變化預先弄好
03/29 23:18, 7F
→
03/29 23:19, , 8F
然後每次的最短路徑的cost也都通通不一樣
03/29 23:19, 8F
推
03/30 06:24, , 9F
saladim 你說的 cost 改變 是指改變 reduced cost 還是？
03/30 06:24, 9F
→
03/30 09:12, , 10F
指的是改變reduced cost...而reduced cost就是會變動到
03/30 09:12, 10F
→
03/30 09:13, , 11F
毎根edge的cost ==> Cost' = Cost + Pi(v) - Pi(u)
03/30 09:13, 11F
→
03/30 09:14, , 12F
我上面說的是 minmum cost flow的部分, 問題在於minmum
03/30 09:14, 12F
→
03/30 09:15, , 13F
cost "max flow" 是否同樣適用同樣理論? 如果是的話 為
03/30 09:15, 13F
→
03/30 09:16, , 14F
何實作裡面edge cost並沒有變化(在residue graph了)
03/30 09:16, 14F
→
03/30 09:17, , 15F
若是兩個問題不能用同一理論處理 那就要去找到為什麼那
03/30 09:17, 15F
→
03/30 09:18, , 16F
樣寫可以得到minmum cost max flow....所以問題分成兩部
03/30 09:18, 16F
→
03/30 09:18, , 17F
份啦~~~~
03/30 09:18, 17F
→
03/30 09:22, , 18F
Cost' = Cost + Pi(v) - Pi(u) 這個東西就是把權重調成非負
03/30 09:22, 18F
→
03/30 09:22, , 19F
方便實施dijkstra最短路徑演算法
03/30 09:22, 19F
→
03/30 09:22, , 20F
這個技巧在CLRS的johnson's algorithm也有用過
03/30 09:22, 20F
→
03/30 09:23, , 21F
前面提到 會有反向邊與-cost出現 如果不調整成非負
03/30 09:23, 21F
→
03/30 09:24, , 22F
那麼只能用floyd-warshall或bellman-ford複雜度較高的方法
03/30 09:24, 22F
→
03/30 09:25, , 23F
然後古代的文獻 基本上會把這個叫做potential什麼什麼的
03/30 09:25, 23F
→
03/30 09:25, , 24F
而不會介紹他有調成非負權重的功效
03/30 09:25, 24F
→
03/30 09:28, , 25F
這個東西是optional的 你有做或沒做 都不會影響正確結果
03/30 09:28, 25F
→
03/30 09:29, , 26F
時間複雜度差個O(V^2)而已
03/30 09:29, 26F
推
03/30 21:45, , 27F
應該沒有差到 V^2 那麼多吧.. 感覺 V^2 好大啊..
03/30 21:45, 27F
→
03/31 00:02, , 28F
再研究一下...文中貼出的參考資料調成非負跟reduced cost
03/31 00:02, 28F
→
03/31 00:03, , 29F
是兩件事情...而且發現這兩種問題 其實是有點不一樣 只
03/31 00:03, 29F
→
03/31 00:03, , 30F
不過是有些引理相同.....有一些本質上差異....
03/31 00:03, 30F
→
03/31 00:05, , 31F
ㄟ 等等 再研究一下好惹 @-@
03/31 00:05, 31F
→
03/31 08:52, , 32F
我說錯了 差V才對
03/31 08:52, 32F
→
03/31 08:54, , 33F
一開始我不知道你講的 reduced cost 是在講什麼 我用猜的
03/31 08:54, 33F
推
03/31 20:08, , 34F
reduced cost 是 mathematical programming 的概念
03/31 20:08, 34F
→
03/31 20:08, , 35F
你可以上 wiki 看解釋
03/31 20:08, 35F
→
03/31 20:09, , 36F
應用到 shortest path 的問題上時 就變成沒負邊的圖
03/31 20:09, 36F
→
04/01 09:02, , 37F
因為他一開始都沒有提到 "reduced cost" 這個詞彙
04/01 09:02, 37F
→
04/02 15:25, , 38F
雖然還沒全懂 似乎是這樣: No negative cycle => Cost'會
04/02 15:25, 38F
→
04/02 15:26, , 39F
>=0 ==> 所以可用Dijk所以reduced cost在此變成非負!!
04/02 15:26, 39F
→
04/02 15:27, , 40F
又沒有negative cycle跟integer cost就有optimal sol. 故
04/02 15:27, 40F
→
04/02 15:28, , 41F
得解...雖然就是各位先進所說的 用我的理解走一遍 ORZ
04/02 15:28, 41F
→
04/02 15:28, , 42F
其他有提到的再繼續看.....@-@||
04/02 15:28, 42F
→
04/02 15:30, , 43F
(min cost flow跟 min cost max flow有什麼關聯還沒懂..)
04/02 15:30, 43F
推
04/02 22:38, , 44F
其實 min cost flow 有很多變化形.. 所以很難搞清楚..
04/02 22:38, 44F
‣ 更多 DJWS 的文章
文章代碼(AID): #1L5rzR0V (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 DJWS 的文章
文章代碼(AID): #1L5rzR0V (Prob_Solve)