最大流問題

在最佳化理論中,最大流問題(英語:Maximum flow problem)涉及到在一個單源點、單匯點的網絡流中找到一條最大的流。

一個網絡最大流的例子。源點為 s,匯點為 t。數字表示流和容量。

最大流問題可以被看作是一個更複雜的網絡流問題(迴圈問題,circulation problem)的特殊情況。s-t流(從源點s到匯點t)的最大值等於s-t割的最小容量,這被稱為最大流最小割定理

歷史

最大流問題最早是在1954年由泰德·哈里斯英語Ted Harris (mathematician)和F·S·羅斯(F. S. Ross)通過一個蘇聯鐵路的交通流量的簡化模型提出的。[1][2][3] 1955年,小萊斯特·倫道夫·福特德爾伯特·雷·富爾克森建立了第一個已知的演算法,福特-富爾克森演算法[4][5]

多年來,最大流問題的各種改進演算法被發現,例如傑克·埃德蒙茲英語Jack Edmonds理查德·卡普葉菲姆·迪尼茨英語Yefim Dinitz最短增廣路演算法;迪尼茨的阻塞流演算法安德魯·V·戈德堡英語Andrew V. Goldberg羅伯特·塔揚的Push-Relabel演算法;戈德堡和Rao的binary阻塞流演算法;Christiano、Kelner和亞歷山大·馬德瑞(Aleksander Madry)的電流演算法;Spielman發現一個最大流近似最佳解,但僅適用於無向圖。[6][7]

定義

 
一個網絡流,源點為 s,匯點為 t。邊上的數字為容量。

 為一個網絡,其中  分別是 的源點和匯點( )。

一個邊的容量為對映 ,記為  。它表示可以通過一條邊的流量的最大值。
一個為一個對映 ,記為  ,遵循下面兩個限制:
  1. 對於每個 ,有 (即容量限制:一個邊的流量不能超過它的容量);
  2. 對於每個 ,有 (即流的保留:流入一個節點的流的總和必須等於流出這個節點的流的總和,源點和匯點除外)。
流量定義為  ,其中  的源點,它表示從源點到匯點的流的數量。
最大流問題就是最大化 ,即從 點到 點儘可能規劃最大的流量。

解法

演算法 複雜度 描述
線性規劃
福特-富爾克森演算法 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  .

參考文獻

  1. ^ Schrijver, A. On the history of the transportation and maximum flow problems. Mathematical Programming. 2002, 91 (3): 437–445. doi:10.1007/s101070100259. 
  2. ^ 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. 
  3. ^ 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). 
  4. ^ 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. 
  5. ^ Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
  6. ^ 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). 
  7. ^ Knight, Helen. New algorithm can dramatically streamline solutions to the ‘max flow’ problem. MIT News. 7 January 2014 [8 January 2014]. (原始內容存檔於2014-02-26). 
  8. ^ 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. 
  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. 
  10. ^ Goldberg, A. V.; Rao, S. Beyond the flow decomposition barrier. ACM期刊. 1998, 45 (5): 783. doi:10.1145/290179.290181. 
  11. ^ 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.