Задача о максимальном потоке
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.
Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.
История
После вступления США во Вторую мировую войну в 1941 году математик Джордж Бернард Данциг поступил на работу в отдел статистического управления Военно-воздушных сил США в Вашингтоне. С 1941 по 1946 годы он возглавлял подразделение анализа военных действий (Combat Analysis Branch), где работал над различными математическими проблемами.[1][2] Впоследствии c использованием работы Данцига задача о максимальном потоке была впервые решена в ходе подготовки воздушного моста во время блокады Западного Берлина, происходившей в 1948—1949 году.[3][4][5]
В 1951 году Джордж Данциг впервые сформулировал задачу в общем виде.[6]
В 1955 году, Лестер Форд и Шаблон:Translation2 впервые построили алгоритм, специально предназначенный для решения этой задачи. Их алгоритм получил название алгоритм Форда-Фалкерсона.[7][8]
В дальнейшем решение задачи много раз улучшалось.
В 2010 году исследователи Джонатан Кёлнер (Jonathan Kelner) и Александер Мондры (Aleksander Mądry) из МТИ вместе со своими коллегами Дэниелем Спилманом (en:Daniel Spielman) из Йельского университета и Шень-Хуа Тенем (en:Shang-Hua Teng) из Южно-Калифорнийского университета продемонстрировали очередное улучшение алгоритма, впервые за 10 лет.[3][9][10]
Определение
Дана транспортная сеть с источником , стоком и пропускными способностями .
- Величиной потока (value of flow) называется сумма потоков из источника . В статье «Транспортная сеть» доказано, что она равна сумме потоков в сток .
Задача о максимальном потоке заключается в нахождении такого потока, что величина потока максимальна.
Решения
Следующая таблица перечисляет некоторые алгоритмы решения задачи.
| Метод | Сложность | Описание |
|---|---|---|
| Линейное программирование | Зависит от конкретного алгоритма. Для симплекс-метода экспоненциальна. |
Представить задачу о максимальном потоке как задачу линейного программирования. Переменными являются потоки по рёбрам, а ограничениями — сохранение потока и ограничение пропускной способности. |
| Алгоритм Форда-Фалкерсона | Зависит от алгоритма поиска увеличивающего пути. Требует O(max| f |) таких поисков. |
Найти любой увеличивающий путь. Увеличить поток по всем его рёбрам на минимальную из их остаточных пропускных способностей. Повторять, пока увеличивающий путь есть. Алгоритм работает только для целых пропускных способностей. В противном случае, он может работать бесконечно долго, не сходясь к правильному ответу. |
| Алгоритм Эдмондса-Карпа | O(VE²) | Выполняем алгоритм Форда-Фалкерсона, каждый раз выбирая кратчайший увеличивающий путь (находится поиском в ширину). |
| Алгоритм Диница | O(V²E) для единичных пропускных способностей с использованием динамических деревьев Слетора и Тарьяна[11] |
Усовершенствование алгоритма Эдмондса-Карпа (но хронологически был найден раньше). На каждой итерации, используя поиск в ширину, определяем расстояния от источника до всех вершин в остаточной сети. Строим граф, содержащий только такие рёбра остаточной сети, на которых это расстояние растёт на 1. Исключаем из графа все тупиковые вершины с инцидентными им рёбрами, пока все вершины не станут нетупиковыми. (Тупиковой называется вершина, кроме источника и стока, в которую не входит ни одно ребро или из которой не исходит ни одного ребра.) На получившемся графе отыскиваем кратчайший увеличивающий путь (им будет любой путь из s в t). Исключаем из остаточной сети ребро с минимальной пропускной способностью, снова исключаем тупиковые вершины, и так пока увеличивающий путь есть. |
| Алгоритм проталкивания предпотока | O(V²E) | Вместо потока оперирует с предпотоком. Отличие в том, что для любой вершины u, кроме источника и стока, сумма входящих в неё потоков для потока должна быть строго нулевой (условие сохранения потока), а для предпотока — неотрицательной. Эта сумма называется избыточным потоком в вершину, а вершина с положительным избыточным потоком называется переполненной. Кроме того, для каждой вершины алгоритм сохраняет дополнительную характеристику, высоту, являющуюся целым неотрицательным числом. Алгоритм использует две операции: проталкивание, когда поток по ребру, идущему из более высокой в более низкую вершину, увеличивается на максимально возможную величину, и подъём, когда переполненная вершина, проталкивание из которой невозможно из-за недостаточной высоты, поднимается. Проталкивание возможно, когда ребро принадлежит остаточной сети, ведёт из более высокой вершины в более низкую, и исходная вершина переполнена. Подъём возможен, когда поднимаемая вершина переполнена, но ни одна из вершин, в которые из неё ведут рёбра остаточной сети, не ниже её. Он совершается до высоты на 1 большей, чем минимальная из высот этих вершин. Изначально высота источника V, по всем рёбрам, исходящим из источника, течёт максимально возможный поток, а остальные высоты и потоки нулевые. Операции проталкивания и подъёма выполняются до тех пор, пока это возможно. |
| Алгоритм «поднять в начало» | O(V³) O(VE log(V²/E)) с использованием динамических деревьев |
Вариант предыдущего алгоритма, специальным образом определяющий порядок операций проталкивания и подъёма. |
| Алгоритм двоичного блокирующего потока [1] |
Для более подробного списка, см. [2] и Список алгоритмов нахождения максимального потока.
Теорема о целом потоке
Если пропускные способности целые, максимальная величина потока тоже целая.
Теорема следует, например, из теоремы Форда—Фалкерсона.
Обобщения, сводящиеся к исходной задаче
Некоторые обобщения задачи о максимальном потоке легко сводятся к исходной задаче.
Произвольное число источников и/или стоков
Если источников больше одного, добавляем новую вершину S, которую делаем единственным источником. Добавляем рёбра с бесконечной пропускной способностью от S к каждому из старых источников.
Аналогично, если стоков больше одного, добавляем новую вершину T, которую делаем единственным стоком. Добавляем рёбра с бесконечной пропускной способностью от каждого из старых стоков к T.
Неориентированные рёбра
Каждое неориентированное ребро (u, v) заменяем на пару ориентированных рёбер (u, v) и (v, u).
Ограничение пропускной способности вершин
Каждую вершину v с ограниченной пропускной способностью расщепляем на две вершины vin и vout. Все рёбра, до расщепления входящие в v, теперь входят в vin. Все рёбра, до расщепления исходящие из v, теперь исходят из vout. Добавляем ребро (vin,vout) с пропускной способностью .
См. также
Примечания
- ↑ Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. George Dantzig (англ.) — биография в архиве MacTutor.
- ↑ Cottle, Richard; Johnson, Ellis; Wets, Roger, «George B. Dantzig (1914—2005)», Notices of the American Mathematical Society, v.54, no.3, March 2007. Cf. p.348
- ↑ 1 2 Hardesty, Larry, «First improvement of fundamental algorithm in 10 years», MIT News Office, September 27, 2010
- ↑ Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas, «Alcuin’s Transportation Problems and Integer Programing» Архивная копия от 7 августа 2011 на Wayback Machine, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, Germany, November 1995. Cf. p.3
- ↑ Powell, Stewart M., «The Berlin Airlift», Air Force Magazine, June 1998.
- ↑ Dantzig, G.B., «Application of the Simplex Method to a Transportation Problem», in T.C. Koopman (ed.): Activity Analysis and Production and Allocation, New York, (1951) 359—373.
- ↑ Ford, L.R., Jr.; Fulkerson, D.R., «Maximal Flow through a Network», Canadian Journal of Mathematics (1956), pp.399-404.
- ↑ Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
- ↑ Kelner, Jonathan, «Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs» Архивная копия от 24 июня 2011 на Wayback Machine, talk at CSAIL, MIT, Tuesday, September 28 2010
- ↑ Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs Архивная копия от 29 ноября 2010 на Wayback Machine, by Paul Cristiano et al., October 19, 2010.
- ↑ Алгоритм Диница
Литература
- Schrijver, Alexander, «On the history of the transportation and maximum flow problems», Mathematical Programming 91 (2002) 437—445
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.. Глава 26. Максимальный поток.
- ↑ Andrew V. Goldberg and S. Rao. Beyond the flow decomposition barrier (неопр.) // J. Assoc. Comput. Mach.. — 1998. — Т. 45. — С. 753—782. — doi:10.1145/290179.290181.
- ↑ Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem (англ.) // Journal of the ACM : journal. — ACM Press, 1988. — Vol. 35, no. 4. — P. 921—940. — ISSN 0004-5411. — doi:10.1145/48014.61051.
- ↑ Joseph Cheriyan and Kurt Mehlhorn. An analysis of the highest-level selection rule in the preflow-push max-flow algorithm (англ.) // Information Processing Letters[англ.] : journal. — 1999. — Vol. 69, no. 5. — P. 239—242. — doi:10.1016/S0020-0190(99)00019-8.
- ↑ Daniel D. Sleator and Robert E. Tarjan. A data structure for dynamic trees (англ.) // Journal of Computer and System Sciences[англ.] : journal. — 1983. — Vol. 26, no. 3. — P. 362—391. — ISSN 0022-0000. — doi:10.1016/0022-0000(83)90006-5.
- ↑ Daniel D. Sleator and Robert E. Tarjan. Self-adjusting binary search trees (англ.) // Journal of the ACM : journal. — ACM Press, 1985. — Vol. 32, no. 3. — P. 652—686. — ISSN 0004-5411. — doi:10.1145/3828.3835.
- Eugene Lawler[англ.]. 4. Network Flows // Combinatorial Optimization: Networks and Matroids (англ.). — Dover, 2001. — P. 109—177. — ISBN 0486414531.