Interested Article - Задача о максимальном потоке
- 2021-10-07
- 1
В теории оптимизации и теории графов , задача о максимальном потоке заключается в нахождении такого потока по транспортной сети , что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.
Задача о максимальном потоке является частным случаем более трудных задач, как например .
История
После вступления США во Вторую мировую войну в 1941 году математик Джордж Бернард Данциг поступил на работу в отдел статистического управления Военно-воздушных сил США в Вашингтоне . С 1941 по 1946 годы он возглавлял подразделение анализа боевых действий (Combat Analysis Branch), где работал над различными математическими проблемами. Впоследствии c использованием работы Данцига задача о максимальном потоке была впервые решена в ходе подготовки воздушного моста во время блокады Западного Берлина , происходившей в 1948—1949 году.
В 1951 году Джордж Данциг впервые сформулировал задачу в общем виде.
В 1955 году, Лестер Форд и ( англ. ) впервые построили алгоритм, специально предназначенный для решения этой задачи. Их алгоритм получил название алгоритм Форда-Фалкерсона .
В дальнейшем решение задачи много раз улучшалось.
В 2010 году исследователи Джонатан Кёлнер (Jonathan Kelner) и Александер Мондры (Aleksander Mądry) из МТИ вместе со своими коллегами Дэниелем Спилманом ( ) из Йельского университета и Шень-Хуа Тенем ( ) из Южно-Калифорнийского университета продемонстрировали очередное улучшение алгоритма, впервые за 10 лет.
Определение
Дана транспортная сеть с источником , стоком и пропускными способностями .
- Величиной потока ( value of flow ) называется сумма потоков из источника . В статье « Транспортная сеть » доказано, что она равна сумме потоков в сток .
Задача о максимальном потоке заключается в нахождении такого потока, где величина потока максимальна.
Решения
Следующая таблица перечисляет некоторые алгоритмы решения задачи.
Метод | Сложность | Описание |
---|---|---|
Линейное программирование | Зависит от конкретного алгоритма. Для симплекс-метода экспоненциальна. | Представить задачу о максимальном потоке как задачу линейного программирования. Переменными являются потоки по рёбрам, а ограничениями — сохранение потока и ограничение пропускной способности. |
Алгоритм Форда-Фалкерсона | Зависит от алгоритма поиска увеличивающего пути. Требует таких поисков. | Найти любой увеличивающий путь. Увеличить поток по всем его рёбрам на минимальную из их остаточных пропускных способностей. Повторять, пока увеличивающий путь есть. Алгоритм работает только для целых пропускных способностей. В противном случае он может работать бесконечно долго, не сходясь к правильному ответу. |
Алгоритм Эдмондса-Карпа | Выполняем алгоритм Форда-Фалкерсона, каждый раз выбирая кратчайший увеличивающий путь (находится поиском в ширину ). | |
Алгоритм Диница | или для единичных пропускных способностей с использованием динамических деревьев Слетора и Тарьяна | Усовершенствование алгоритма Эдмондса-Карпа (но хронологически был найден раньше). На каждой итерации, используя поиск в ширину, определяем расстояния от источника до всех вершин в остаточной сети. Строим граф, содержащий только такие рёбра остаточной сети, на которых это расстояние растёт на 1. Исключаем из графа все тупиковые вершины с инцидентными им рёбрами, пока все вершины не станут нетупиковыми. (Тупиковой называется вершина, кроме источника и стока, в которую не входит ни одно ребро или из которой не исходит ни одного ребра.) На получившемся графе отыскиваем кратчайший увеличивающий путь (им будет любой путь из s в t). Исключаем из остаточной сети ребро с минимальной пропускной способностью, снова исключаем тупиковые вершины, и так пока увеличивающий путь есть. |
Алгоритм проталкивания предпотока | Вместо потока оперирует с предпотоком. Отличие в том, что для любой вершины u, кроме источника и стока, сумма входящих в неё потоков для потока должна быть строго нулевой (условие сохранения потока), а для предпотока — неотрицательной. Эта сумма называется избыточным потоком в вершину, а вершина с положительным избыточным потоком называется переполненной . Кроме того, для каждой вершины алгоритм сохраняет дополнительную характеристику, высоту , являющуюся целым неотрицательным числом. Алгоритм использует две операции: проталкивание , когда поток по ребру, идущему из более высокой в более низкую вершину, увеличивается на максимально возможную величину, и подъём , когда переполненная вершина, проталкивание из которой невозможно из-за недостаточной высоты, поднимается. Проталкивание возможно, когда ребро принадлежит остаточной сети, ведёт из более высокой вершины в более низкую, и исходная вершина переполнена. Подъём возможен, когда поднимаемая вершина переполнена, но ни одна из вершин, в которые из неё ведут рёбра остаточной сети, не ниже её. Он совершается до высоты на 1 большей, чем минимальная из высот этих вершин. Изначально высота источника V, по всем рёбрам, исходящим из источника, течёт максимально возможный поток, а остальные высоты и потоки нулевые. Операции проталкивания и подъёма выполняются до тех пор, пока это возможно. | |
Алгоритм «поднять в начало» | или с использованием динамических деревьев | Вариант предыдущего алгоритма, специальным образом определяющий порядок операций проталкивания и подъёма. |
Алгоритм двоичного блокирующего потока [1] |
Для более подробного списка, см. [2] и .
Теорема о целом потоке
Если пропускные способности целые, максимальная величина потока тоже целая.
Теорема следует, например, из теоремы Форда—Фалкерсона .
Обобщения, сводящиеся к исходной задаче
Некоторые обобщения задачи о максимальном потоке легко сводятся к исходной задаче.
Произвольное число источников и/или стоков
Если источников больше одного, добавляем новую вершину S, которую делаем единственным источником. Добавляем рёбра с бесконечной пропускной способностью от S к каждому из старых источников.
Аналогично, если стоков больше одного, добавляем новую вершину T, которую делаем единственным стоком. Добавляем рёбра с бесконечной пропускной способностью от каждого из старых стоков к T.
Неориентированные рёбра
Каждое неориентированное ребро (u, v) заменяем на пару ориентированных рёбер (u, v) и (v, u).
Ограничение пропускной способности вершин
Каждую вершину v с ограниченной пропускной способностью расщепляем на две вершины v in и v out . Все рёбра, до расщепления входящие в v, теперь входят в v in . Все рёбра, до расщепления исходящие из v, теперь исходят из v out . Добавляем ребро (v in ,v out ) с пропускной способностью .
Ограничение пропускной способности рёбер снизу
В данном варианте постановки задачи значение потока каждого ребра дополнительно ограничено снизу функцией . Таким образом величина потока для любого ребра не может превысить его пропускную способность, но и не может быть меньше заданного минимума, т.е. . Для решения задачи необходимо преобразовать исходную транспортную сеть в транспортную сеть следующим образом:
- Добавь новые источник и сток .
-
Для каждого ребра
:
- Создай две новые вершины и .
- Установи и .
- Установи .
- Установи и .
- Установи .
В определён поток, удовлетворяющий условию об ограничении пропускной способности ребёр снизу, тогда и только тогда, когда в определен максимальный поток, в котором все рёбра вида и "насыщены". Благодаря такому построению алгоритм нахождения потока, ограниченного снизу будет следующим:
- Из построй .
- Найди поток графа , предпочитая рёбра вида и .
- Если , где - поток графа , в котором опущена пропускная способность рёбер снизу, то решения не существует.
- Иначе вычисли поток из потока , т.е. .
Ограничение пропускной способности рёбер снизу с альтернативой
Такой вариант задачи идентичен предыдущему с той разницей, что значение потока для каждого ребра может быть также равно , т.е. или . Несмотря на незначительное изменение условия, не существует полиноминального решения данной проблемы, если классы P и NP не равны . В качестве доказательства утверждения можно привести полиноминальную редукцию к проблеме .
См. также
Примечания
- Джон Дж. О’Коннор и Эдмунд Ф. Робертсон . (англ.) — биография в архиве MacTutor .
- Cottle, Richard; Johnson, Ellis; Wets, Roger, от 7 сентября 2015 на Wayback Machine , Notices of the American Mathematical Society , v.54, no.3, March 2007. Cf. p.348
- ↑ Hardesty, Larry, от 28 марта 2014 на Wayback Machine , MIT News Office, September 27, 2010
- Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas, от 7 августа 2011 на Wayback Machine , Konrad-Zuse-Zentrum für Informationstechnik , Berlin, Germany, November 1995. Cf. p.3
- Powell, Stewart M., , Air Force Magazine , June 1998.
- Dantzig, G.B., от 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, от 24 июня 2011 на Wayback Machine , talk at CSAIL, MIT, Tuesday, September 28 2010
- от 29 ноября 2010 на Wayback Machine , by Paul Cristiano et al., October 19, 2010.
- . Дата обращения: 28 октября 2010. 7 мая 2015 года.
Литература
- Schrijver, Alexander, , Mathematical Programming 91 (2002) 437—445
- Кормен, Т. , Лейзерсон, Ч. , Ривест, Р. , Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М. : Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4 . . Глава 26. Максимальный поток.
- and . Beyond the flow decomposition barrier (неопр.) // J. Assoc. Comput. Mach.. — 1998. — Т. 45 . — С. 753—782 . — doi : .
- 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 . — doi : .
- and . An analysis of the highest-level selection rule in the preflow-push max-flow algorithm (англ.) // Vol. 69 , no. 5 . — P. 239—242 . — doi : . : journal. — 1999. —
- and Robert E. Tarjan . (англ.) // : journal. — 1983. — Vol. 26 , no. 3 . — P. 362—391 . — ISSN . — doi : .
- and Robert E. Tarjan . (англ.) // Journal of the ACM : journal. — ACM Press, 1985. — Vol. 32 , no. 3 . — P. 652—686 . — ISSN . — doi : .
- 4. Network Flows // Combinatorial Optimization: Networks and Matroids (англ.) . — Dover, 2001. — P. 109—177. — ISBN 0486414531 .
- 2021-10-07
- 1