Алгоритм Динича или алгоритм Диница - это сильно полиномиальный алгоритм для вычисления максимального потока в сети потоков , разработанный в 1970 году израильским (бывшим советским) ученым-компьютерщиком Ефимом (Хаимом) А. Диницем. [1] Алгоритм работает ввремени и аналогичен алгоритму Эдмондса – Карпа , который работает вtime, поскольку он использует кратчайшие пути увеличения. Введение понятий графа уровней и блокирующего потока позволяет алгоритму Диника достичь своей производительности.
История
Ефим Диниц изобрел этот алгоритм в ответ на предварительное упражнение в классе алгоритмов Адельсона-Вельского . В то время он не знал основных фактов об алгоритме Форда – Фулкерсона . [2]
Диниц упоминает об изобретении своего алгоритма в январе 1969 г., который был опубликован в 1970 г. в журнале « Доклады Академии Наук СССР» . В 1974 году Шимон Эвен и (его тогдашний аспирант) Алон Итаи из Техниона в Хайфе были очень любопытны и заинтригованы алгоритмом Диница, а также связанной с ним идеей Александра В. Карзанова о блокировании потока. Однако им было трудно расшифровать эти две статьи, каждая из которых была ограничена четырьмя страницами, чтобы соответствовать ограничениям журнала « Доклады Академии Наук СССР» . Даже не сдавался, и после трех дней усилий удалось разобраться в обоих документах, за исключением проблемы обслуживания многоуровневой сети. В течение следующих двух лет Эвен читал лекции по «алгоритму Динича», неправильно произнося имя автора при его популяризации. Эвен и Итаи также внесли свой вклад в этот алгоритм, объединив BFS и DFS , как сейчас обычно представляют алгоритм. [3]
В течение примерно 10 лет после изобретения алгоритма Форда – Фулкерсона было неизвестно, можно ли заставить его завершаться за полиномиальное время в общем случае иррациональных пропускных способностей ребер. Это привело к отсутствию какого-либо известного алгоритма с полиномиальным временем для решения проблемы максимального потока в общих случаях. Алгоритм Диница и алгоритм Эдмондса – Карпа (опубликованный в 1972 г.) независимо друг от друга показали, что в алгоритме Форда – Фулкерсона, если каждый увеличивающий путь является кратчайшим, то длина расширяющих путей не уменьшается, и алгоритм всегда завершается.
Определение
Позволять быть сетью с а также емкость и поток края , соответственно.
- Остаточная емкость является отображением определяется как,
- если ,
- иначе.
- если ,
- Остаточный график представляет собой график , невзвешенный , где
- .
- Путь увеличивающий является - путь в остаточном графе .
- Определять быть длиной кратчайшего пути от к в . Тогда уровень графа из график , где
- .
Алгоритм
Алгоритм Динича
- Вход : сеть .
- Выход : An - поток максимальной стоимости.
- Набор для каждого .
- Построить из из . Если, остановить и вывести .
- Найдите блокирующий поток в .
- Добавить поток дополнений от и вернитесь к шагу 2.
Анализ
Можно показать, что количество слоев в каждом блокирующем потоке увеличивается по крайней мере на 1 каждый раз, и, таким образом, имеется не более блокировка потоков в алгоритме. Для каждого из них:
- график уровня можно построить поиском в ширину в время
- блокирующий поток на графике уровней можно найти в время
с общим временем работы для каждого слоя. Как следствие, время работы алгоритма Динича равно. [6]
Используя структуру данных, называемую динамическими деревьями , время поиска блокирующего потока на каждой фазе может быть сокращено до и поэтому время работы алгоритма Динича можно улучшить до .
Особые случаи
В сетях с единичной мощностью сохраняется гораздо более жесткая временная граница. Каждый блокирующий поток можно найти в время, и можно показать, что количество фаз не превышает а также . Таким образом, алгоритм работает ввремя. [7]
В сетях, возникающих из задачи двустороннего согласования , количество фаз ограничено, поэтому приводит к ограниченный по времени. Полученный алгоритм также известен как алгоритм Хопкрофта – Карпа . В более общем смысле, эта граница верна для любой единичной сети - сети, в которой каждая вершина, за исключением источника и приемника, либо имеет одно входное ребро с пропускной способностью один, либо одно исходящее ребро с пропускной способностью единица, а все остальные мощности являются произвольными целыми числами. . [5]
Пример
Ниже приводится симуляция алгоритма Динича. На графике уровней, вершины с метками красного цвета - это значения . Пути, отмеченные синим цветом, образуют блокирующий поток.
1. | |||
---|---|---|---|
Блокирующий поток состоит из
Таким образом, блокирующий поток составляет 14 единиц, а значение расхода равно 14. Обратите внимание, что каждый путь увеличения в блокирующем потоке имеет 3 ребра. | |||
2. | |||
Блокирующий поток состоит из
Следовательно, блокирующий поток составляет 5 единиц, а значение потока равно 14 + 5 = 19. Обратите внимание, что каждый увеличивающий путь имеет 4 ребра. | |||
3. | |||
С не может быть достигнуто в , алгоритм завершается и возвращает поток с максимальным значением 19. Обратите внимание, что в каждом блокирующем потоке количество ребер в увеличивающем пути увеличивается как минимум на 1. |
Смотрите также
Заметки
- ^ Ефим Диниц (1970). «Алгоритм решения задачи максимального потока в сети с оценкой мощности» (PDF) . Доклады Академии Наук СССР . 11 : 1277–1280.
- ^ Илан Кадар; Сиван Албаглы (27 ноября 2009 г.). «Алгоритм Диница для поиска максимального потока в сети» .
- ^ Ефим Диниц. «Алгоритм Диница: исходная версия и версия даже» (PDF) . Цитировать журнал требует
|journal=
( помощь ) - ^ Это означает, что подграф, полученный в результате удаления всех насыщенных ребер (т.е. всех ребер такой, что ) не содержит пути из к . Другими словами, блокирующий поток таков, что каждый возможный путь от к содержит насыщенное ребро.
- ^ а б Тарьян 1983 , стр. 102.
- ^ Ефим Диниц (2006). «Алгоритм Диница: исходная версия и версия даже» (PDF) . В Одед Гольдрайх ; Арнольд Л. Розенберг; Алан Л. Селман (ред.). Теоретическая информатика: очерки памяти Шимона Эвена . Springer. С. 218–240. ISBN 978-3-540-32880-3.
- ^ Даже, Шимон; Тарьян, Р. Эндре (1975). «Сетевой поток и тестирование графического подключения». SIAM Journal on Computing . 4 (4): 507–518. DOI : 10.1137 / 0204043 . ISSN 0097-5397 .
Рекомендации
- Ефим Диниц (2006). «Алгоритм Диница: исходная версия и версия даже» (PDF) . В Одед Гольдрайх ; Арнольд Л. Розенберг; Алан Л. Селман (ред.). Теоретическая информатика: очерки памяти Шимона Эвена . Springer. С. 218–240. ISBN 978-3-540-32880-3.
- Tarjan, RE (1983). Структуры данных и сетевые алгоритмы .
- BH Korte; Йенс Выген (2008). «8.4 Блокирующие потоки и алгоритм Фудзишиге». Комбинаторная оптимизация: теория и алгоритмы (Алгоритмы и комбинаторика, 21) . Springer Berlin Heidelberg. С. 174–176. ISBN 978-3-540-71844-4.