最大流问题

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

一个网络最大流的例子。源点为 s,汇点为 t。数字表示流和容量。

最大流问题可以被看作是一个更复杂的网络流问题(循环问题,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]

定义

一个网络流,源点为 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. . Mathematical Programming. 2002, 91 (3): 437–445. doi:10.1007/s101070100259.
  2. Gass, Saul I.; Assad, Arjang A. . . 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. (PDF). Research Memorandum (Rand Corporation). 1955 [2017-03-07]. (原始内容存档 (PDF)于2017-02-17).
  4. Ford, L. R.; Fulkerson, D. R. . 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. . (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. . MIT News. 7 January 2014 [8 January 2014]. (原始内容存档于2014-02-26).
  8. Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. . Information Processing Letters. 1978, 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.
  9. King, V.; Rao, S.; Tarjan, R. . Journal of Algorithms. 1994, 17 (3): 447–474. doi:10.1006/jagm.1994.1044.
  10. Goldberg, A. V.; Rao, S. . ACM期刊. 1998, 45 (5): 783. doi:10.1145/290179.290181.
  11. Orlin, James B. . STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing. 2013: 765–774. doi:10.1145/2488608.2488705.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.