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

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

История

Диниц изобрел алгоритм в январе 1969 года, будучи студентом магистратуры в Георгия Адельсона-Вельского группе . Несколько десятилетий спустя он вспоминал:

На уроке «Алгоритмы» Адельсона-Вельского лектор имел привычку давать студентам задачу для обсуждения на следующем заседании в качестве упражнения. DA был изобретен в ответ на такое упражнение. В то время автору не были известны основные факты, касающиеся [ алгоритма Форда-Фалкерсона ]….

⋮

Незнание иногда имеет свои преимущества. Вполне вероятно, что DA не был бы изобретен тогда, если бы автору была известна идея возможного обесцвечивания насыщенных краев.

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

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

Определение

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

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

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

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

2. если $(v,u)\in E$,

   $c_{f}(u,v)=f(v,u)$

3. $c_{f}(u,v)=0$ в противном случае.

представляет Остаточный граф собой невзвешенный граф $G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)$, где

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

– Дополняющий путь это $s$– $t$ путь в остаточном графе $G_{f}$.

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

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

– Блокирующий поток это $s$– $t$ поток $f'$ такой, что график $G'=((V,E_{L}'),s,t)$ с $E_{L}'=\{(u,v)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}$ не содержит $s$– $t$ путь.

Алгоритм

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

Вход : сеть. $G=((V,E),c,s,t)$.

Выход : Ан $s$– $t$ поток $f$ максимального значения.

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

Анализ

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

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

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

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

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

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

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

Пример

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

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

См. также

• Алгоритм Форда – Фулкерсона
• Проблема максимального потока

Ссылки

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