最大流问题

维基百科,自由的百科全书
(重定向自最大流
跳转至: 导航搜索
一个网络最大流的例子。源点为 s,汇点为 t。数字表示流和容量。

在优化理论中,最大流问题涉及到在一个单源点、单汇点的网络流中找到一条最大的流。

最大流问题可以被看作是一个更复杂的网络流问题(如循环问题(circulation problem))的特殊情况,。s-t流(从源点s到汇点t)的最大值等于s-t割的最小容量,这被称为最大流最小割定理

历史[编辑]

最大流问题最早是在1954年,由T.E.Harris 和F.S.Ross通过一个苏联铁路的交通流量的简化模型提出的。[1][2][3] 1955年, 莱斯特*福特小 和 德尔伯特R.Fulkerson 创建了第一个已知的算法, Ford–Fulkerson算法[4][5]

多年来,最大流问题的各种改进算法被发现,例如Edmonds和Karp还有Dinitz的最短增广路算法;Dinitz的阻塞流算法; Goldberg 和 陶尔扬的Push-Relabel算法;Goldberg和Rao的binary阻塞流算法。 Christiano, Kelner, Madry的电流算法,Spielman 发现一个最大流近似最优解,但仅适用于无向图。[6][7]

定义[编辑]

一个网络流,源点为 s,汇点为 t。边上的数字为容量。

解法[编辑]

算法 复杂度 描述
线性规划
Ford–Fulkerson算法 O(E max| f |)
Edmonds–Karp算法 O(VE2) Ford–Fulkerson算法的特例,使用广度优先搜索寻找增广路径.
Dinic阻塞流算法 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. 
  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. 
  7. ^ Knight, Helen. New algorithm can dramatically streamline solutions to the ‘max flow’ problem. MIT News. 7 January 2014 [8 January 2014]. 
  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.  参数|title=值左起第4位存在删除符 (帮助)
  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.