Алгоритм Dinics - Википедия - Dinics algorithm

Алгоритм диника или же Алгоритм Диница это сильно полиномиальный алгоритм вычисления максимальный поток в проточная сеть, задуманный в 1970 году израильским (бывшим советским) ученым-компьютерщиком Ефимом (Хаимом) А. Диницем.[1] Алгоритм работает в время и похоже на Алгоритм Эдмондса – Карпа, который работает в time, поскольку он использует кратчайшие пути увеличения. Введение в концепции график уровня и блокировка потока включить алгоритм Диника для достижения его производительности.

История

Ефим Диниц изобрел этот алгоритм в ответ на предварительное упражнение в Адельсон-Вельский класс алгоритмов. В то время он не знал основных фактов, касающихся Алгоритм Форда – Фулкерсона.[2]

Диниц упоминает об изобретении своего алгоритма в январе 1969 года, который был опубликован в 1970 году в журнале. Доклады Академии Наук СССР. В 1974 году Шимон Эвен и (его тогдашний аспирант) Алон Итаи в Технион в Хайфе были очень любопытны и заинтригованы алгоритмом Диница, а также Карзанов Александр Васильевич родственная идея блокировки потока. Однако им было трудно расшифровать эти две статьи, каждая из которых была ограничена четырьмя страницами, чтобы соответствовать ограничениям журнала. Доклады Академии Наук СССР. Даже не сдавался, и после трех дней усилий удалось разобраться в обоих документах, за исключением проблемы обслуживания многоуровневой сети. В течение следующих нескольких лет Эвен читал лекции по «алгоритму Динича», неправильно произнося имя автора при его популяризации. Эвен и Итаи также внесли свой вклад в этот алгоритм, объединив BFS и DFS, как сейчас обычно представляют алгоритм.[3]

В течение примерно 10 лет после изобретения алгоритма Форда – Фулкерсона было неизвестно, можно ли заставить его завершаться за полиномиальное время в общем случае иррациональных возможностей ребер. Это привело к отсутствию какого-либо известного алгоритма с полиномиальным временем для решения проблемы максимального потока в общих случаях. Алгоритм Диница и Алгоритм Эдмондса – Карпа (опубликовано в 1972 г.) оба независимо друг от друга показали, что в алгоритме Форда – Фулкерсона, если каждый дополнительный путь является самым коротким, то длина дополнительных путей не уменьшается, и алгоритм всегда завершается.

Определение

Позволять быть сетью с и емкость и поток края , соответственно.

В остаточная емкость это отображение определяется как,
  1. если ,
  2. иначе.
В остаточный график невзвешенный граф , куда
.
An расширение пути является путь в остаточном графе .
Определять быть длиной кратчайшего пути от к в . Тогда график уровня из график , куда
.
А блокировка потока является поток такой, что граф с не содержит дорожка.[4][5]

Алгоритм

Алгоритм Динича

Вход: Сеть .
Выход: An поток максимальной стоимости.
  1. Набор для каждого .
  2. Построить из из . Если , остановить и вывести .
  3. Найдите блокирующий поток в .
  4. Добавить поток дополнений к и вернитесь к шагу 2.

Анализ

Можно показать, что количество слоев в каждом блокирующем потоке увеличивается каждый раз как минимум на 1, и, таким образом, имеется не более блокировка потоков в алгоритме. Для каждого из них:

  • график уровня может быть построен поиск в ширину в время
  • блокирующий поток на графике уровней можно найти в время

с общим временем работы для каждого слоя. Как следствие, время работы алгоритма Динича равно .[6]

Используя структуру данных под названием динамические деревья, время поиска блокирующего потока на каждой фазе можно сократить до и поэтому время работы алгоритма Динича можно улучшить до .

Особые случаи

В сетях с единичной мощностью удерживаются гораздо более жесткие временные рамки. Каждый блокирующий поток можно найти в время, и можно показать, что количество фаз не превышает и . Таким образом, алгоритм работает в время.[7]

В сетях, возникающих из двудольное соответствие задачи количество фаз ограничено , поэтому приводит к ограниченный по времени. Результирующий алгоритм также известен как Алгоритм Хопкрофта-Карпа. В общем, эта оценка верна для любого сеть единиц - сеть, в которой каждая вершина, за исключением источника и приемника, либо имеет одно входное ребро емкости единица, либо единственное исходящее ребро емкости единица, а все остальные мощности являются произвольными целыми числами.[5]

Пример

Ниже приводится симуляция алгоритма Динича. На графике уровней , вершины с метками красного цвета - это значения . Пути, отмеченные синим цветом, образуют блокирующий поток.

1.Алгоритм Dinic G1.svgАлгоритм Dinic Gf1.svgАлгоритм Dinic GL1.svg

Блокирующий поток состоит из

  1. с 4 единицами протока,
  2. с 6 единицами потока, и
  3. с 4 единицами протока.

Следовательно, блокирующий поток составляет 14 единиц, а значение потока равно 14. Обратите внимание, что каждый путь увеличения в блокирующем потоке имеет 3 края.

2.Алгоритм Dinic G2.svgАлгоритм Dinic Gf2.svgАлгоритм Dinic GL2.svg

Блокирующий поток состоит из

  1. с 5 единицами протока.

Следовательно, блокирующий поток составляет 5 единиц, а значение потока равно 14 + 5 = 19. Обратите внимание, что каждый дополнительный путь имеет 4 ребра.

3.Алгоритм Dinic G3.svgАлгоритм Dinic Gf3.svgАлгоритм Dinic GL3.svg

С не может быть достигнуто в , алгоритм завершает работу и возвращает поток с максимальным значением 19. Обратите внимание, что в каждом блокирующем потоке количество ребер в расширяющем пути увеличивается как минимум на 1.

Смотрите также

Примечания

  1. ^ Ефим Диниц (1970). «Алгоритм решения задачи максимального потока в сети с оценкой мощности» (PDF). Доклады Академии Наук СССР. 11: 1277–1280.
  2. ^ Илан Кадар; Сиван Албаглы (27 ноября 2009 г.). «Алгоритм Диница для поиска максимального потока в сети».
  3. ^ Ефим Диниц. «Алгоритм Диница: исходная версия и версия даже» (PDF). Цитировать журнал требует | журнал = (помощь)
  4. ^ Это означает, что подграф, полученный в результате удаления всех насыщенных ребер (т.е. всех ребер такой, что ) не содержит пути из к . Другими словами, блокировка потока таков, что все возможные пути от к содержит насыщенное ребро.
  5. ^ а б Тарджан 1983, п. 102.
  6. ^ Ефим Диниц (2006). «Алгоритм Диница: исходная версия и версия даже» (PDF). В Одед Гольдрайх; Арнольд Л. Розенберг; Алан Л. Селман (ред.). Теоретическая информатика: очерки памяти Шимон Эвен. Springer. С. 218–240. ISBN  978-3-540-32880-3.
  7. ^ Даже, Шимон; Тарьян, Р. Эндре (1975). «Сетевой поток и тестирование графического подключения». SIAM Журнал по вычислениям. 4 (4): 507–518. Дои:10.1137/0204043. ISSN  0097-5397.

Рекомендации