Участник:Anastasy/Алгоритм Диница
Алгоритм Диница
Автор: Киреева Анастасия, группа 416
Содержание
- 1 Постановка задачи
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Постановка задачи
1.1 Общее описание алгоритма
Алгоритм Диница [1] — полиномиальный алгоритм, предназначенный для поиска максимального потока в транспортной сети. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма [math]O(n^2m)[/math], где [math]m[/math] — число ребер, а [math]n[/math] — число вершин.
Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток. Алгоритм Диница схож с алгоритмом Эдмондса-Карпа[2], но основное отличие можно понимать так: на каждой итерации поток увеличивается не вдоль одного кратчайшего пути из истока в сток, а вдоль целого набора таких путей.
1.2 Математическое описание алгоритма
Математическая постановка задачи приведена в статье "Поиск максимального потока в транспортной сети", мы будем использовать введённые в ней обозначения.
Введём необходимые определения.
Остаточной сетью [math]G^R[/math] по отношению к сети [math]G=(V, E)[/math] и некоторому потоку [math]f[/math] в ней называется сеть, в которой каждому ребру [math](u,v) \in E[/math] с пропускной способностью [math]c_{uv}[/math] и потоком [math]f_{uv}[/math] соответствуют два ребра:
- [math](u,v)[/math] с пропускной способностью [math]c_{uv}^R = c_{uv} - f_{uv}[/math]
- [math](v,u)[/math] с пропускной способностью [math]c_{vu}^R = f_{uv}[/math]
Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро [math](u,v)[/math], так и [math](v,u)[/math].
Блокирующим потоком в данной сети называется такой поток, что любой путь из истока [math]s[/math] в сток [math]t[/math] содержит насыщенное этим потоком ребро (то есть [math]c_{uv} = f_{uv}[/math] для некоторых [math]u,v \in V[/math]). Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
Блокирующий поток не обязательно максимален. Согласно теореме Форда-Фалкерсона поток будет максимальным тогда и только тогда, когда в остаточной сети [math]G^R[/math] не найдётся [math]s-t[/math] пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
Слоистая сеть для данной сети строится следующим образом. Сначала определяются длины кратчайших путей из истока [math]s[/math] до всех остальных вершин; назовём уровнем [math]{\rm level}[v][/math] вершины её расстояние от истока. Тогда в слоистую сеть включают все те рёбра [math](u,v)[/math] исходной сети, для которых верно [math]{\rm level}[u] + 1 = {\rm level}[v][/math].
Слоистая сеть ациклична. Кроме того, любой [math]s-t[/math] путь в слоистой сети является кратчайшим путём в исходной сети.
Алгоритм представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается. Алгоритм заканчивает свою работу, когда в построенной на некоторой итерации остаточной сети не найдётся [math]s-t[/math] пути.
1.3 Вычислительное ядро алгоритма
Наибольший объем вычислений приходится на:
- поиск в ширину (для построения слоистой сети)
- обход в глубину (для построения блокирующего потока)
1.4 Макроструктура алгоритма
Одним из важных шагов алгоритма является поиск блокирующего потока. Опишем, каким образом это можно сделать.
Ищем [math]s-t[/math] пути по одному обходом в глубину, пока такие пути находятся, при этом удаляем те ребра, вдоль которых невозможно дойти до стока. Для этого достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину.
1.5 Схема реализации последовательного алгоритма
Структуру алгоритма можно описать следующим образом:
- Для всех ребер [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]G^L[/math] по отношению к сети [math]G^R[/math]. Если [math]{\rm level}[t]=∞[/math], алгоритм завершает работу и выводит поток [math]f[/math].
- Ищем блокирующий поток [math]f'[/math] в сети [math]G^R[/math]
- Прибавим [math]f'[/math] к потоку [math]f[/math] и переходим к шагу 2.
1.6 Последовательная сложность алгоритма
- С помощью поиска в ширину слоистая сеть строится за время [math]O(m)[/math].
- Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Таким образом, один запуск обхода в глубину работает за [math]O(n + k)[/math], где [math]k[/math] — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет [math]O(p)[/math], где [math]p[/math] — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за [math]O(pn + \sum\limits_i{k_i})[/math]. Учитывая, что все указатели в сумме прошли расстояние [math]O(m)[/math], это дает асимптотику [math]O(pn + pk)[/math]. В худшем случае, когда блокирующий поток насыщает все рёбра, асимптотика получается [math]O(mn)[/math].
- Можно показать, что после каждой итерации расстояние между стоком и истоком строго увеличивается[1] (то есть [math]{\rm level'}[t] \gt {\rm level}[t][/math], где [math]{\rm level'}[t][/math] — расстояние до стока, полученное на следующей итерации). Так как длина кратчайшего [math]s-t[/math] пути не может превосходить [math]n - 1[/math], то и количество фаз алгоритма не превосходит [math]n - 1[/math]. Таким образом, весь алгоритм Диница выполняется за [math]O(n^2m)[/math].
1.7 Информационный граф
Для алгоритма Диница:
- Инициализация переменных
- Вызов функции поиска в ширину
- (3.1 - 3.k) выполнение функции поиска в глубину, итеративно увеличивается поток
- Вызов функции поиска в ширину. В случае существования пути до стока, переход на следующую итерацию (начиная с поиска в глубину), иначе вывод вычисленной величины потока.
Для поиска в ширину
- Инициализация расстояния до истока ([math]d[s] = 0[/math]) и текущего уровня нулю ([math]level = 0[/math]).
- Извлечение очередной вершины из множества вершин, соответствующего процессу ([math]v \in V_{node}[/math]). Вершина обрабатывается, если расстояние до нее равно текущему уровню ([math]d[v] == level [/math])
- Обход соседей вершин. В случае если вершина [math]u [/math] принадлежит [math]V_{node}[/math], значение пути до этой вершины инициализируется [math]d[u] = level + 1[/math]. Иначе она помечается для дальнейшей обработки другим процессом.
- Слияние информации по помеченным вершинам (в общем массиве помечаются все вершины, которые были помечены хотя бы один раз)
- Для всех помеченных необработанных ([math]d[v] == -1 [/math]) вершин, принадлежащих [math]V_{node}[/math], расстояние принимается равным [math]level + 1[/math]
- Если было обновлено расстояние хотя бы до одной вершины, переход на следующую итерацию, иначе выход из цикла
1.8 Ресурс параллелизма алгоритма
В приведенном варианте алгоритма поиска в ширину граф обходится по слоям, то есть на каждой итерации обрабатывается множество вершин, расстояние до которых одинаково. Число слоев не превосходит [math]n - 1[/math], таким образом, высота ярусно-параллельной формы алгоритма поиска в ширину равна [math]O(n)[/math].
Так как поиск блокирующего потока производится последовательно, его высота ярусно-параллельной формы алгоритма совпадает с его последовательной сложностью [math]O(nm)[/math].
Так как число шагов алгоритма не превосходит [math]n[/math], высота ЯПФ алгоритма Диница равна [math]O(n^2m)[/math].
В описанном алгоритме поиска в ширину вершины разделяются между процессами поровну, поэтому ширина ЯПФ поиска в ширину и алгоритма Диница равна [math]n[/math].
1.9 Входные и выходные данные алгоритма
Входные данные: Граф [math]G(V, E)[/math]. [math]n[/math] вершин [math]v_i[/math] и [math]m[/math] ребер [math]e_j = (v_j^{(1)}, v_j^{(2)}) [/math] с заданной пропускной способностью [math]c_j[/math], а также исток [math]s[/math] и сток [math]t[/math].
Объем входных данных: [math]O(m + n)[/math].
Выходные данные: величина максимального потока.
Объем выходных данных: [math]O(1)[/math].
1.10 Свойства алгоритма
В зависимости от порядка обработки ребер графа, вычисленные блокирующие потоки на соответствующих итерациях могут быть различны, кроме того, может поменяться количество итераций алгоритма Диница.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [math][2^k, k = 0, 1, ...7][/math];
- число вершин графа [5 000:20 000] с шагом 5000. Количество ребер одинаково для всех графов и равно 2 500 000.
На графике, приведенном ниже, показана зависимость производительности (количество обработанных ребер в единицу времени) от количества процессов и количества вершин графа. Время алгоритма сильно зависит от структуры графа (она влияет на количество итераций алгоритма Диница), поэтому время выполнения алгоритма в общем случае не пропорционально размеру графа.
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
3 Литература
- ↑ 1,0 1,1 Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57
- ↑ Edmonds, Jack; Karp, Richard M. (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. Association for Computing Machinery