- Задача о максимальном потоке
-
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.
Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.
Содержание
История
После вступления США во Вторую мировую войну в 1941 году математик Джордж Бернард Данциг поступил на работу в отдел статистического управления Военно-воздушных сил США в Вашингтоне. С 1941 по 1946 годы он возглавлял подразделение анализа военных действий (Combat Analysis Branch), где работал над различными математическими проблемами.[1][2] Впоследствии c использованием работы Данцига задача о максимальном потоке была впервые решена в ходе подготовки воздушного моста во время блокады Западного Берлина, происходившей в 1948—1949 году.[3][4][5]
В 1951 году Джордж Данциг впервые сформулировал задачу в общем виде.[6]
В 1955 году, Лестер Форд и Делберт Фалкерсон (англ. Delbert Ray Fulkerson) впервые построили алгоритм, специально предназначенный для решения этой задачи. Их алгоритм получил название алгоритм Форда-Фалкерсона.[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)) с использованием динамических деревьевВариант предыдущего алгоритма, специальным образом определяющий порядок операций проталкивания и подъёма. Алгоритм двоичного блокирующего потока * Для более подробного списка, см. * и Список алгоритмов нахождения максимального потока.
Теорема о целом потоке
Если пропускные способности целые, максимальная величина потока тоже целая.
Теорема следует, например, из теоремы Форда—Фалкерсона.
Обобщения, сводящиеся к исходной задаче
Некоторые обобщения задачи о максимальном потоке легко сводятся к исходной задаче.
Произвольное число источников и/или стоков
Если источников больше одного, добавляем новую вершину 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», 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», talk at CSAIL, MIT, Tuesday, September 28 2010
- ↑ Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs, 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 (1998). «Beyond the flow decomposition barrier». J. Assoc. Comput. Mach. 45: 753–782. DOI:10.1145/290179.290181.
- ↑ Andrew V. Goldberg and Robert E. Tarjan (1988). «A new approach to the maximum-flow problem». Journal of the ACM (ACM Press) 35 (4): 921–940. DOI:10.1145/48014.61051. ISSN 0004-5411.
- ↑ Joseph Cheriyan and Kurt Mehlhorn (1999). «An analysis of the highest-level selection rule in the preflow-push max-flow algorithm». Information Processing Letters 69 (5): 239–242. DOI:10.1016/S0020-0190(99)00019-8.
- ↑ Daniel D. Sleator and Robert E. Tarjan (1983). «A data structure for dynamic trees». Journal of Computer and System Sciences 26 (3): 362–391. DOI:10.1016/0022-0000(83)90006-5. ISSN 0022-0000.
- ↑ Daniel D. Sleator and Robert E. Tarjan (1985). «Self-adjusting binary search trees». Journal of the ACM (ACM Press) 32 (3): 652–686. DOI:10.1145/3828.3835. ISSN 0004-5411.
- Eugene Lawler 4. Network Flows // Combinatorial Optimization: Networks and Matroids. — Dover, 2001. — P. 109–177. — ISBN 0486414531
Категория:- Алгоритмы на графах
Wikimedia Foundation. 2010.