Задача о максимальном потоке ({g;gcg k bgtvnbgl,ukb hkmkty)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/94/Max_flow.svg/330px-Max_flow.svg.png)
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.
Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.
История
[править | править код]После вступления США во Вторую мировую войну в 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) называется сумма потоков из источника . В статье «Транспортная сеть» доказано, что она равна сумме потоков в сток .
Задача о максимальном потоке заключается в нахождении такого потока, где величина потока максимальна.
Решения
[править | править код]Следующая таблица перечисляет некоторые алгоритмы решения задачи.
Метод | Сложность | Описание |
---|---|---|
Линейное программирование | Зависит от конкретного алгоритма. Для симплекс-метода экспоненциальна. | Представить задачу о максимальном потоке как задачу линейного программирования. Переменными являются потоки по рёбрам, а ограничениями — сохранение потока и ограничение пропускной способности. |
Алгоритм Форда-Фалкерсона | Зависит от алгоритма поиска увеличивающего пути. Требует таких поисков. | Найти любой увеличивающий путь. Увеличить поток по всем его рёбрам на минимальную из их остаточных пропускных способностей. Повторять, пока увеличивающий путь есть. Алгоритм работает только для целых пропускных способностей. В противном случае он может работать бесконечно долго, не сходясь к правильному ответу. |
Алгоритм Эдмондса-Карпа | Выполняем алгоритм Форда-Фалкерсона, каждый раз выбирая кратчайший увеличивающий путь (находится поиском в ширину). | |
Алгоритм Диница | или для единичных пропускных способностей с использованием динамических деревьев Слетора и Тарьяна[11] | Усовершенствование алгоритма Эдмондса-Карпа (но хронологически был найден раньше). На каждой итерации, используя поиск в ширину, определяем расстояния от источника до всех вершин в остаточной сети. Строим граф, содержащий только такие рёбра остаточной сети, на которых это расстояние растёт на 1. Исключаем из графа все тупиковые вершины с инцидентными им рёбрами, пока все вершины не станут нетупиковыми. (Тупиковой называется вершина, кроме источника и стока, в которую не входит ни одно ребро или из которой не исходит ни одного ребра.) На получившемся графе отыскиваем кратчайший увеличивающий путь (им будет любой путь из s в t). Исключаем из остаточной сети ребро с минимальной пропускной способностью, снова исключаем тупиковые вершины, и так пока увеличивающий путь есть. |
Алгоритм проталкивания предпотока | Вместо потока оперирует с предпотоком. Отличие в том, что для любой вершины u, кроме источника и стока, сумма входящих в неё потоков для потока должна быть строго нулевой (условие сохранения потока), а для предпотока — неотрицательной. Эта сумма называется избыточным потоком в вершину, а вершина с положительным избыточным потоком называется переполненной. Кроме того, для каждой вершины алгоритм сохраняет дополнительную характеристику, высоту, являющуюся целым неотрицательным числом. Алгоритм использует две операции: проталкивание, когда поток по ребру, идущему из более высокой в более низкую вершину, увеличивается на максимально возможную величину, и подъём, когда переполненная вершина, проталкивание из которой невозможно из-за недостаточной высоты, поднимается. Проталкивание возможно, когда ребро принадлежит остаточной сети, ведёт из более высокой вершины в более низкую, и исходная вершина переполнена. Подъём возможен, когда поднимаемая вершина переполнена, но ни одна из вершин, в которые из неё ведут рёбра остаточной сети, не ниже её. Он совершается до высоты на 1 большей, чем минимальная из высот этих вершин. Изначально высота источника V, по всем рёбрам, исходящим из источника, течёт максимально возможный поток, а остальные высоты и потоки нулевые. Операции проталкивания и подъёма выполняются до тех пор, пока это возможно. | |
Алгоритм «поднять в начало» | или с использованием динамических деревьев | Вариант предыдущего алгоритма, специальным образом определяющий порядок операций проталкивания и подъёма. |
Алгоритм двоичного блокирующего потока [1] |
Для более подробного списка, см. [2] и Список алгоритмов нахождения максимального потока.
Теорема о целом потоке
[править | править код]Если пропускные способности целые, максимальная величина потока тоже целая.
Теорема следует, например, из теоремы Форда—Фалкерсона.
Обобщения, сводящиеся к исходной задаче
[править | править код]Некоторые обобщения задачи о максимальном потоке легко сводятся к исходной задаче.
Произвольное число источников и/или стоков
[править | править код]Если источников больше одного, добавляем новую вершину S, которую делаем единственным источником. Добавляем рёбра с бесконечной пропускной способностью от S к каждому из старых источников.
Аналогично, если стоков больше одного, добавляем новую вершину T, которую делаем единственным стоком. Добавляем рёбра с бесконечной пропускной способностью от каждого из старых стоков к T.
Неориентированные рёбра
[править | править код]Каждое неориентированное ребро (u, v) заменяем на пару ориентированных рёбер (u, v) и (v, u).
Ограничение пропускной способности вершин
[править | править код]Каждую вершину v с ограниченной пропускной способностью расщепляем на две вершины vin и vout. Все рёбра, до расщепления входящие в v, теперь входят в vin. Все рёбра, до расщепления исходящие из v, теперь исходят из vout. Добавляем ребро (vin,vout) с пропускной способностью .
Ограничение пропускной способности рёбер снизу
[править | править код]В данном варианте постановки задачи значение потока каждого ребра дополнительно ограничено снизу функцией . Таким образом величина потока для любого ребра не может превысить его пропускную способность, но и не может быть меньше заданного минимума, т.е. . Для решения задачи необходимо преобразовать исходную транспортную сеть в транспортную сеть следующим образом:
- Добавь новые источник и сток .
- Для каждого ребра :
- Создай две новые вершины и .
- Установи и .
- Установи .
- Установи и .
- Установи .
В определён поток, удовлетворяющий условию об ограничении пропускной способности ребёр снизу, тогда и только тогда, когда в определен максимальный поток, в котором все рёбра вида и "насыщены". Благодаря такому построению алгоритм нахождения потока, ограниченного снизу будет следующим:
- Из построй .
- Найди поток графа , предпочитая рёбра вида и .
- Если , где - поток графа , в котором опущена пропускная способность рёбер снизу, то решения не существует.
- Иначе вычисли поток из потока , т.е. .
Ограничение пропускной способности рёбер снизу с альтернативой
[править | править код]Такой вариант задачи идентичен предыдущему с той разницей, что значение потока для каждого ребра может быть также равно , т.е. или . Несмотря на незначительное изменение условия, не существует полиноминального решения данной проблемы, если классы P и NP не равны. В качестве доказательства утверждения можно привести полиноминальную редукцию к проблеме Exact-3-SAT.
См. также
[править | править код]Примечания
[править | править код]- ↑ Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. George Dantzig (англ.) — биография в архиве MacTutor.
- ↑ Cottle, Richard; Johnson, Ellis; Wets, Roger, «George B. Dantzig (1914—2005)» Архивная копия от 7 сентября 2015 на Wayback Machine, 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» Архивная копия от 28 марта 2014 на Wayback Machine, 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» Архивная копия от 19 июля 2010 на Wayback Machine, 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.
- ↑ Алгоритм Диница . Дата обращения: 28 октября 2010. Архивировано 7 мая 2015 года.
Литература
[править | править код]- 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.