最大流問題
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/9/94/Max_flow.svg/220px-Max_flow.svg.png)
在最佳化理論中,最大流問題(英語:Maximum flow problem)涉及到在一個單源點、單匯點的網絡流中找到一條最大的流。
最大流問題可以被看作是一個更複雜的網絡流問題(迴圈問題,circulation problem)的特殊情況。s-t流(從源點s到匯點t)的最大值等於s-t割的最小容量,這被稱為最大流最小割定理。
歷史
最大流問題最早是在1954年由泰德·哈里斯和F·S·羅斯(F. S. Ross)通過一個蘇聯鐵路的交通流量的簡化模型提出的。[1][2][3] 1955年,小萊斯特·倫道夫·福特和德爾伯特·雷·富爾克森建立了第一個已知的演算法,福特-富爾克森演算法。[4][5]
多年來,最大流問題的各種改進演算法被發現,例如傑克·埃德蒙茲、理查德·卡普和葉菲姆·迪尼茨的最短增廣路演算法;迪尼茨的阻塞流演算法;安德魯·V·戈德堡和羅伯特·塔揚的Push-Relabel演算法;戈德堡和Rao的binary阻塞流演算法;Christiano、Kelner和亞歷山大·馬德瑞(Aleksander Madry)的電流演算法;Spielman發現一個最大流近似最佳解,但僅適用於無向圖。[6][7]
定義
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cb/MFP1.jpg/220px-MFP1.jpg)
設為一個網絡,其中和分別是的源點和匯點()。
- 一個邊的容量為對映,記為或。它表示可以通過一條邊的流量的最大值。
- 一個流為一個對映,記為或,遵循下面兩個限制:
- 對於每個,有(即容量限制:一個邊的流量不能超過它的容量);
- 對於每個,有(即流的保留:流入一個節點的流的總和必須等於流出這個節點的流的總和,源點和匯點除外)。
- 流量定義為 ,其中為的源點,它表示從源點到匯點的流的數量。
- 最大流問題就是最大化,即從點到點儘可能規劃最大的流量。
解法
演算法 | 複雜度 | 描述 |
---|---|---|
線性規劃 | ||
福特-富爾克森演算法 | O(E max| f |) | |
埃德蒙茲-卡普演算法 | O(VE2) | 福特-富爾克森演算法的特例,使用廣度優先搜尋尋找增廣路徑. |
迪尼茨阻塞流演算法 | O(V2E) | |
MPM (Malhotra, Pramodh-Kumar and Maheshwari)演算法[8] | O(V3) | 只適用於無環圖。參考 Original Paper. |
Dinic演算法 | O(VE log(V)) | |
push-relabel maximum flow演算法 | O(V2E) | |
Push-relabel演算法,使用FIFO vertex selection rule | O(V3) | |
Push-relabel演算法,使用 dynamic trees | ||
KRT (King, Rao, Tarjan)演算法[9] | ||
Binary阻塞流演算法[10] | ||
James B Orlin's + KRT (King, Rao, Tarjan)演算法[11] | Orlin's algorithm (頁面存檔備份,存於互聯網檔案館) solves max-flow in O(VE) time for while KRT solves it in O(VE) for . |
參考文獻
- ^ Schrijver, A. On the history of the transportation and maximum flow problems. Mathematical Programming. 2002, 91 (3): 437–445. doi:10.1007/s101070100259.
- ^ Gass, Saul I.; Assad, Arjang A. Mathematical, algorithmic and professional developments of operations research from 1951 to 1956. An Annotated Timeline of Operations Research. International Series in Operations Research & Management Science 75. 2005: 79–110. ISBN 1-4020-8116-2. doi:10.1007/0-387-25837-X_5.
- ^ Harris, T. E.; Ross, F. S. Fundamentals of a Method for Evaluating Rail Net Capacities (PDF). Research Memorandum (Rand Corporation). 1955 [2017-03-07]. (原始內容存檔 (PDF)於2017-02-17).
- ^ Ford, L. R.; Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics. 1956, 8: 399. doi:10.4153/CJM-1956-045-5.
- ^ Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
- ^ Kelner, J. A.; Lee, Y. T.; Orecchia, L.; Sidford, A. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF). 2014: 217. ISBN 978-1-61197-338-9. arXiv:1304.2338
. doi:10.1137/1.9781611973402.16. (原始內容 (PDF)存檔於2016-03-03).
- ^ Knight, Helen. New algorithm can dramatically streamline solutions to the ‘max flow’ problem. MIT News. 7 January 2014 [8 January 2014]. (原始內容存檔於2014-02-26).
- ^ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. An algorithm for finding maximum flows in networks. Information Processing Letters. 1978, 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.
- ^ King, V.; Rao, S.; Tarjan, R. A Faster Deterministic Maximum Flow Algorithm. Journal of Algorithms. 1994, 17 (3): 447–474. doi:10.1006/jagm.1994.1044.
- ^ Goldberg, A. V.; Rao, S. Beyond the flow decomposition barrier. ACM期刊. 1998, 45 (5): 783. doi:10.1145/290179.290181.
- ^ Orlin, James B. Max flows in O(nm) time, or better. STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing. 2013: 765–774. doi:10.1145/2488608.2488705.
|