Участник:Anastasy/Алгоритм Диница: различия между версиями
Anastasy (обсуждение | вклад) |
Anastasy (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
Одним из важных шагов алгоритма является поиск блокирующего потока. Опишем, каким образом это можно сделать. | Одним из важных шагов алгоритма является поиск блокирующего потока. Опишем, каким образом это можно сделать. | ||
Ищем <math>s-t</math> пути по одному обходом в глубину, пока такие пути находятся, при этом удаляем те ребра, вдоль которых невозможно дойти до стока. Для этого достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. | Ищем <math>s-t</math> пути по одному обходом в глубину, пока такие пути находятся, при этом удаляем те ребра, вдоль которых невозможно дойти до стока. Для этого достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. | ||
| Строка 39: | Строка 40: | ||
Структуру алгоритма можно описать следующим образом: | Структуру алгоритма можно описать следующим образом: | ||
# Для всех ребер <math>(u, v) \in E</math> сети <math>G</math> присвоим <math>f_{uv}=0</math>. | # Для всех ребер <math>(u, v) \in E</math> сети <math>G</math> присвоим <math>f_{uv}=0</math>. | ||
# Построим остаточную сеть <math>G^R</math> по отношению к сети <math>G</math> и потоку <math>f</math>. Если <math>{\rm level}[t]=∞</math> алгоритм завершает работу и выводит поток <math>f</math>. | # Построим остаточную сеть <math>G^R</math> по отношению к сети <math>G</math> и потоку <math>f</math>. Если <math>{\rm level}[t]=∞</math>, алгоритм завершает работу и выводит поток <math>f</math>. | ||
# Ищем блокирующий поток <math>f'</math> в сети <math>G^R</math> | # Ищем блокирующий поток <math>f'</math> в сети <math>G^R</math> | ||
# Прибавим <math>f'</math> к потоку <math>f</math> и переходим к шагу 2. | # Прибавим <math>f'</math> к потоку <math>f</math> и переходим к шагу 2. | ||
Версия от 14:18, 20 октября 2017
Постановка задачи
Общее описание алгоритма
Алгоритм Диница [1] — полиномиальный алгоритм, предназначенный для поиска максимального потока в транспортной сети. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма [math]\displaystyle{ O(nm^2) }[/math], где [math]\displaystyle{ m }[/math] — число ребер, а [math]\displaystyle{ n }[/math] — число вершин.
Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток. Алгоритм Диница схож с алгоритмом Эдмондса-Карпа[2], но основное отличие можно понимать так: на каждой итерации поток увеличивается не вдоль одного кратчайшего пути из истока в сток, а вдоль целого набора таких путей.
Математическое описание алгоритма
Математическая постановка задачи приведена в статье "Поиск максимального потока в транспортной сети", мы будем использовать введённые в ней обозначения.
Введём необходимые определения.
Остаточной сетью [math]\displaystyle{ G^R }[/math] по отношению к сети [math]\displaystyle{ G=(V, E) }[/math] и некоторому потоку [math]\displaystyle{ f }[/math] в ней называется сеть, в которой каждому ребру [math]\displaystyle{ (u,v) \in E }[/math] с пропускной способностью [math]\displaystyle{ c_{uv} }[/math] и потоком [math]\displaystyle{ f_{uv} }[/math] соответствуют два ребра:
- [math]\displaystyle{ (u,v) }[/math] с пропускной способностью [math]\displaystyle{ c_{uv}^R = c_{uv} - f_{uv} }[/math]
- [math]\displaystyle{ (v,u) }[/math] с пропускной способностью [math]\displaystyle{ c_{vu}^R = f_{uv} }[/math]
Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро [math]\displaystyle{ (u,v) }[/math], так и [math]\displaystyle{ (v,u) }[/math].
Блокирующим потоком в данной сети называется такой поток, что любой путь из истока [math]\displaystyle{ s }[/math] в сток [math]\displaystyle{ t }[/math] содержит насыщенное этим потоком ребро (то есть [math]\displaystyle{ c_{uv} = f_{uv} }[/math] для некоторых [math]\displaystyle{ u,v \in V }[/math]). Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
Блокирующий поток не обязательно максимален. Согласно теореме Форда-Фалкерсона поток будет максимальным тогда и только тогда, когда в остаточной сети [math]\displaystyle{ G^R }[/math] не найдётся [math]\displaystyle{ s-t }[/math] пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
Слоистая сеть для данной сети строится следующим образом. Сначала определяются длины кратчайших путей из истока s до всех остальных вершин; назовём уровнем [math]\displaystyle{ {\rm level}[v] }[/math] вершины её расстояние от истока. Тогда в слоистую сеть включают все те рёбра [math]\displaystyle{ (u,v) }[/math] исходной сети, которые ведут с одного уровня на какой-либо другой, более поздний, уровень, т.е. [math]\displaystyle{ {\rm level}[u] + 1 = {\rm level}[v] }[/math] (разница расстояний не может превосходить единицы, это следует из свойства кратчайших расстояний). Таким образом, удаляются все рёбра, расположенные целиком внутри уровней, а также рёбра, ведущие назад, к предыдущим уровням.
Слоистая сеть ациклична. Кроме того, любой [math]\displaystyle{ s-t }[/math] путь в слоистой сети является кратчайшим путём в исходной сети.
Алгоритм представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается. Алгоритм заканчивает свою работу, когда в построенной на некоторой итерации остаточной сети не найдётся [math]\displaystyle{ s-t }[/math] пути.
Вычислительное ядро алгоритма
Наибольший объем вычислений приходится на:
- поиск в ширину (для построения слоистой сети)
- обход в глубину (для построения блокирующего потока)
Макроструктура алгоритма
Одним из важных шагов алгоритма является поиск блокирующего потока. Опишем, каким образом это можно сделать.
Ищем [math]\displaystyle{ s-t }[/math] пути по одному обходом в глубину, пока такие пути находятся, при этом удаляем те ребра, вдоль которых невозможно дойти до стока. Для этого достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину.
Схема реализации последовательного алгоритма
Структуру алгоритма можно описать следующим образом:
- Для всех ребер [math]\displaystyle{ (u, v) \in E }[/math] сети [math]\displaystyle{ G }[/math] присвоим [math]\displaystyle{ f_{uv}=0 }[/math].
- Построим остаточную сеть [math]\displaystyle{ G^R }[/math] по отношению к сети [math]\displaystyle{ G }[/math] и потоку [math]\displaystyle{ f }[/math]. Если [math]\displaystyle{ {\rm level}[t]=∞ }[/math], алгоритм завершает работу и выводит поток [math]\displaystyle{ f }[/math].
- Ищем блокирующий поток [math]\displaystyle{ f' }[/math] в сети [math]\displaystyle{ G^R }[/math]
- Прибавим [math]\displaystyle{ f' }[/math] к потоку [math]\displaystyle{ f }[/math] и переходим к шагу 2.
Программная реализация алгоритма
Литература
- ↑ Yefim Dinitz (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Doklady Akademii nauk SSSR.
- ↑ Edmonds, Jack; Karp, Richard M. (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. Association for Computing Machinery