Алгоритм Dinics - Dinics algorithm

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

История

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

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

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

Определение

Позволять ${\displaystyle G=((V,E),c,f,s,t)}$ быть сетью с ${\displaystyle c(u,v)}$ и ${\displaystyle f(u,v)}$ емкость и поток края ${\displaystyle (u,v)}$, соответственно.

В остаточная емкость это отображение ${\displaystyle c_{f}\colon V\times V\to R^{+}}$ определяется как,

1. если ${\displaystyle (u,v)\in E}$,

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

2. ${\displaystyle c_{f}(u,v)=0}$ иначе.

В остаточный график невзвешенный граф ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$, куда

${\displaystyle E_{f}=\{(u,v)\in V\times V\colon \;c_{f}(u,v)>0\}}$.

An расширение пути является ${\displaystyle s}$–${\displaystyle t}$ путь в остаточном графе ${\displaystyle G_{f}}$.

Определять ${\displaystyle \operatorname {dist} (v)}$ быть длиной кратчайшего пути от ${\displaystyle s}$ к ${\displaystyle v}$ в ${\displaystyle G_{f}}$. Тогда график уровня из ${\displaystyle G_{f}}$ график ${\displaystyle G_{L}=((V,E_{L}),c_{f}|_{E_{L}},s,t)}$, куда

${\displaystyle E_{L}=\{(u,v)\in E_{f}\colon \;\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$.

А блокировка потока является ${\displaystyle s}$–${\displaystyle t}$ поток ${\displaystyle f}$ такой, что граф ${\displaystyle G'=((V,E_{L}'),s,t)}$ с ${\displaystyle E_{L}'=\{(u,v)\colon \;f(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ не содержит ${\displaystyle s}$–${\displaystyle t}$ дорожка.^[4][5]

Алгоритм

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

Вход: Сеть ${\displaystyle G=((V,E),c,s,t)}$.

Выход: An ${\displaystyle s}$–${\displaystyle t}$ поток ${\displaystyle f}$ максимальной стоимости.

1. Набор ${\displaystyle f(e)=0}$ для каждого ${\displaystyle e\in E}$.
2. Построить ${\displaystyle G_{L}}$ из ${\displaystyle G_{f}}$ из ${\displaystyle G}$. Если ${\displaystyle \operatorname {dist} (t)=\infty }$, остановить и вывести ${\displaystyle f}$.
3. Найдите блокирующий поток ${\displaystyle f'}$ в ${\displaystyle G_{L}}$.
4. Добавить поток дополнений ${\displaystyle f}$ к ${\displaystyle f'}$ и вернитесь к шагу 2.

Анализ

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

• график уровня ${\displaystyle G_{L}}$ может быть построен поиск в ширину в ${\displaystyle O(E)}$ время
• блокирующий поток на графике уровней ${\displaystyle G_{L}}$ можно найти в ${\displaystyle O(VE)}$ время

с общим временем работы ${\displaystyle O(E+VE)=O(VE)}$ для каждого слоя. Как следствие, время работы алгоритма Динича равно ${\displaystyle O(V^{2}E)}$.^[6]

Используя структуру данных под названием динамические деревья, время поиска блокирующего потока на каждой фазе можно сократить до ${\displaystyle O(E\log V)}$ и поэтому время работы алгоритма Динича можно улучшить до ${\displaystyle O(VE\log V)}$.

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

В сетях с единичной мощностью удерживаются гораздо более жесткие временные рамки. Каждый блокирующий поток можно найти в ${\displaystyle O(E)}$ время, и можно показать, что количество фаз не превышает ${\displaystyle O({\sqrt {E}})}$ и ${\displaystyle O(V^{2/3})}$. Таким образом, алгоритм работает в ${\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}$ время.^[7]

В сетях, возникающих из двудольное соответствие задачи количество фаз ограничено ${\displaystyle O({\sqrt {V}})}$, поэтому приводит к ${\displaystyle O({\sqrt {V}}E)}$ ограниченный по времени. Результирующий алгоритм также известен как Алгоритм Хопкрофта-Карпа. В общем, эта оценка верна для любого сеть единиц - сеть, в которой каждая вершина, за исключением источника и приемника, либо имеет одно входное ребро емкости единица, либо единственное исходящее ребро емкости единица, а все остальные мощности являются произвольными целыми числами.^[5]

Пример

Ниже приводится симуляция алгоритма Динича. На графике уровней ${\displaystyle G_{L}}$, вершины с метками красного цвета - это значения ${\displaystyle \operatorname {dist} (v)}$. Пути, отмеченные синим цветом, образуют блокирующий поток.

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	Блокирующий поток состоит из ${\displaystyle \{s,1,3,t\}}$ с 4 единицами протока, ${\displaystyle \{s,1,4,t\}}$ с 6 единицами потока, и ${\displaystyle \{s,2,4,t\}}$ с 4 единицами протока. Следовательно, блокирующий поток составляет 14 единиц, а значение потока ${\displaystyle |f|}$ равно 14. Обратите внимание, что каждый путь увеличения в блокирующем потоке имеет 3 края.
2.
	Блокирующий поток состоит из ${\displaystyle \{s,2,4,3,t\}}$ с 5 единицами протока. Следовательно, блокирующий поток составляет 5 единиц, а значение потока ${\displaystyle |f|}$ равно 14 + 5 = 19. Обратите внимание, что каждый дополнительный путь имеет 4 ребра.
3.
	С ${\displaystyle t}$ не может быть достигнуто в ${\displaystyle G_{f}}$, алгоритм завершает работу и возвращает поток с максимальным значением 19. Обратите внимание, что в каждом блокирующем потоке количество ребер в расширяющем пути увеличивается как минимум на 1.

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

• Алгоритм Форда – Фулкерсона
• Задача максимального расхода

Примечания

1. Ефим Диниц (1970). «Алгоритм решения задачи максимального потока в сети с оценкой мощности» (PDF). Доклады Академии Наук СССР. 11: 1277–1280.
2. Илан Кадар; Сиван Албаглы (27 ноября 2009 г.). «Алгоритм Диница для поиска максимального потока в сети».
3. Ефим Диниц. «Алгоритм Диница: исходная версия и версия даже» (PDF).
4. Это означает, что подграф, полученный в результате удаления всех насыщенных ребер (т.е. всех ребер ${\displaystyle (u,v)}$ такой, что ${\displaystyle f(u,v)=c_{f}|_{E_{L}}(u,v)}$) не содержит пути из ${\displaystyle s}$ к ${\displaystyle t}$. Другими словами, блокировка потока таков, что все возможные пути от ${\displaystyle s}$ к ${\displaystyle t}$ содержит насыщенное ребро.
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.

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

• Ефим Диниц (2006). «Алгоритм Диница: исходная версия и версия даже» (PDF). В Одед Гольдрайх; Арнольд Л. Розенберг; Алан Л. Селман (ред.). Теоретическая информатика: очерки памяти Шимон Эвен. Springer. С. 218–240. ISBN  978-3-540-32880-3.
• Тарьян, Р. Э. (1983). Структуры данных и сетевые алгоритмы.
• Б. Х. Корте; Йенс Выген (2008). «8.4 Блокирующие потоки и алгоритм Фудзишиге». Комбинаторная оптимизация: теория и алгоритмы (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. С. 174–176. ISBN  978-3-540-71844-4.