Участник:Anastasy/Алгоритм Диница: различия между версиями
Anastasy (обсуждение | вклад) |
Anastasy (обсуждение | вклад) |
||
(не показаны 22 промежуточные версии этого же участника) | |||
Строка 5: | Строка 5: | ||
== Постановка задачи == | == Постановка задачи == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
− | Алгоритм Диница <ref>Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57</ref> — полиномиальный алгоритм, предназначенный для поиска [[Поиск максимального потока в транспортной сети| максимального потока в транспортной сети]]. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма <math>O( | + | Алгоритм Диница <ref name="Dinic">Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57</ref> — полиномиальный алгоритм, предназначенный для поиска [[Поиск максимального потока в транспортной сети| максимального потока в транспортной сети]]. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма <math>O(n^2m)</math>, где <math>m</math> — число ребер, а <math>n</math> — число вершин. |
Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток. | Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток. | ||
Строка 51: | Строка 51: | ||
* С помощью поиска в ширину слоистая сеть строится за время <math>O(m)</math>. | * С помощью поиска в ширину слоистая сеть строится за время <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>. | * Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Таким образом, один запуск обхода в глубину работает за <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>. | ||
− | * Можно показать, что после каждой итерации расстояние между стоком и истоком строго увеличивается<ref> | + | * Можно показать, что после каждой итерации расстояние между стоком и истоком строго увеличивается<ref name="Dinic"/> (то есть <math>{\rm level'}[t] > {\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>. |
+ | |||
+ | === Информационный граф === | ||
+ | <div><ul> | ||
+ | <li style="display: inline-block;"> [[File:dinic.png|thumb|none|500px|Рисунок 1. Информационный граф алгоритма Диница]] </li> | ||
+ | <li style="display: inline-block;"> [[File:bfs.png|thumb|none|650px|Рисунок 2. Информационный граф поиска в ширину]] </li> | ||
+ | </ul></div> | ||
+ | Для алгоритма Диница: | ||
+ | # Инициализация переменных | ||
+ | # Вызов функции поиска в ширину | ||
+ | # (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> | ||
+ | # Если было обновлено расстояние хотя бы до одной вершины, переход на следующую итерацию, иначе выход из цикла | ||
+ | |||
+ | === Ресурс параллелизма алгоритма === | ||
+ | В приведенном варианте алгоритма поиска в ширину граф обходится по слоям, то есть на каждой итерации обрабатывается множество вершин, расстояние до которых одинаково. Число слоев не превосходит <math>n - 1</math>, таким образом, высота ярусно-параллельной формы алгоритма поиска в ширину равна <math>O(n)</math>. | ||
+ | |||
+ | Так как поиск блокирующего потока производится последовательно, его высота ярусно-параллельной формы алгоритма совпадает с его последовательной сложностью <math>O(nm)</math>. | ||
+ | |||
+ | Так как число шагов алгоритма не превосходит <math>n</math>, высота ЯПФ алгоритма Диница равна <math>O(n^2m)</math>. | ||
+ | |||
+ | В описанном алгоритме поиска в ширину вершины разделяются между процессами поровну, поэтому ширина ЯПФ поиска в ширину и алгоритма Диница равна <math>n</math>. | ||
− | |||
− | |||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
+ | '''Входные данные''': Граф <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>. | ||
+ | |||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
+ | В зависимости от порядка обработки ребер графа, вычисленные блокирующие потоки на соответствующих итерациях могут быть различны, кроме того, может поменяться количество итераций алгоритма Диница. | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
Строка 63: | Строка 97: | ||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
+ | Набор и границы значений изменяемых параметров запуска реализации алгоритма: | ||
+ | |||
+ | * число процессоров <math>[2^k, k = 0, 1, ...7]</math>; | ||
+ | * число вершин графа [5 000:20 000] с шагом 5000. Количество ребер одинаково для всех графов и равно 2 500 000. | ||
+ | На графике, приведенном ниже, показана зависимость производительности (количество обработанных ребер в единицу времени) от количества процессов и количества вершин графа. Время алгоритма сильно зависит от структуры графа (она влияет на количество итераций алгоритма Диница), поэтому время выполнения алгоритма в общем случае не пропорционально размеру графа. | ||
+ | |||
+ | График зависимости ускорения от количества процессов и количества вершин графа (рис. 4) более нагляден, так как количество итераций в алгоритме не зависит от количества процессов и время выполнения пропорционально числу итераций. По этому графику видно, что ускорение падает с увеличением размера графа. | ||
+ | <div><ul> | ||
+ | <li style="display: inline-block;"> [[File:Dinic scalability.png|thumb|none|600px|Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа]] </li> | ||
+ | <li style="display: inline-block;"> [[File:speedup_dinic.png|thumb|none|600px|Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа]] </li> | ||
+ | </ul></div> | ||
+ | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
+ | * Python: [https://networkx.github.io NetworkX] (функция <code>[https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.dinitz.html dinitz]</code>): алгоритм Диница | ||
== Литература == | == Литература == | ||
<references /> | <references /> |
Текущая версия на 12:12, 30 ноября 2017
Алгоритм Диница
Автор: Киреева Анастасия, группа 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 году. Временная сложность алгоритма O(n^2m), где m — число ребер, а n — число вершин.
Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток. Алгоритм Диница схож с алгоритмом Эдмондса-Карпа[2], но основное отличие можно понимать так: на каждой итерации поток увеличивается не вдоль одного кратчайшего пути из истока в сток, а вдоль целого набора таких путей.
1.2 Математическое описание алгоритма
Математическая постановка задачи приведена в статье "Поиск максимального потока в транспортной сети", мы будем использовать введённые в ней обозначения.
Введём необходимые определения.
Остаточной сетью G^R по отношению к сети G=(V, E) и некоторому потоку f в ней называется сеть, в которой каждому ребру (u,v) \in E с пропускной способностью c_{uv} и потоком f_{uv} соответствуют два ребра:
- (u,v) с пропускной способностью c_{uv}^R = c_{uv} - f_{uv}
- (v,u) с пропускной способностью c_{vu}^R = f_{uv}
Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро (u,v), так и (v,u).
Блокирующим потоком в данной сети называется такой поток, что любой путь из истока s в сток t содержит насыщенное этим потоком ребро (то есть c_{uv} = f_{uv} для некоторых u,v \in V). Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
Блокирующий поток не обязательно максимален. Согласно теореме Форда-Фалкерсона поток будет максимальным тогда и только тогда, когда в остаточной сети G^R не найдётся s-t пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
Слоистая сеть для данной сети строится следующим образом. Сначала определяются длины кратчайших путей из истока s до всех остальных вершин; назовём уровнем {\rm level}[v] вершины её расстояние от истока. Тогда в слоистую сеть включают все те рёбра (u,v) исходной сети, для которых верно {\rm level}[u] + 1 = {\rm level}[v].
Слоистая сеть ациклична. Кроме того, любой s-t путь в слоистой сети является кратчайшим путём в исходной сети.
Алгоритм представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается. Алгоритм заканчивает свою работу, когда в построенной на некоторой итерации остаточной сети не найдётся s-t пути.
1.3 Вычислительное ядро алгоритма
Наибольший объем вычислений приходится на:
- поиск в ширину (для построения слоистой сети)
- обход в глубину (для построения блокирующего потока)
1.4 Макроструктура алгоритма
Одним из важных шагов алгоритма является поиск блокирующего потока. Опишем, каким образом это можно сделать.
Ищем s-t пути по одному обходом в глубину, пока такие пути находятся, при этом удаляем те ребра, вдоль которых невозможно дойти до стока. Для этого достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину.
1.5 Схема реализации последовательного алгоритма
Структуру алгоритма можно описать следующим образом:
- Для всех ребер (u, v) \in E сети G присвоим f_{uv}=0.
- Построим остаточную сеть G^R по отношению к сети G и потоку f. Затем строим слоистую сеть G^L по отношению к сети G^R. Если {\rm level}[t]=∞, алгоритм завершает работу и выводит поток f.
- Ищем блокирующий поток f' в сети G^R
- Прибавим f' к потоку f и переходим к шагу 2.
1.6 Последовательная сложность алгоритма
- С помощью поиска в ширину слоистая сеть строится за время O(m).
- Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Таким образом, один запуск обхода в глубину работает за O(n + k), где k — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет O(p), где p — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за O(pn + \sum\limits_i{k_i}). Учитывая, что все указатели в сумме прошли расстояние O(m), это дает асимптотику O(pn + pk). В худшем случае, когда блокирующий поток насыщает все рёбра, асимптотика получается O(mn).
- Можно показать, что после каждой итерации расстояние между стоком и истоком строго увеличивается[1] (то есть {\rm level'}[t] \gt {\rm level}[t], где {\rm level'}[t] — расстояние до стока, полученное на следующей итерации). Так как длина кратчайшего s-t пути не может превосходить n - 1, то и количество фаз алгоритма не превосходит n - 1. Таким образом, весь алгоритм Диница выполняется за O(n^2m).
1.7 Информационный граф
Для алгоритма Диница:
- Инициализация переменных
- Вызов функции поиска в ширину
- (3.1 - 3.k) выполнение функции поиска в глубину, итеративно увеличивается поток
- Вызов функции поиска в ширину. В случае существования пути до стока, переход на следующую итерацию (начиная с поиска в глубину), иначе вывод вычисленной величины потока.
Для поиска в ширину
- Инициализация расстояния до истока (d[s] = 0) и текущего уровня нулю (level = 0).
- Извлечение очередной вершины из множества вершин, соответствующего процессу (v \in V_{node}). Вершина обрабатывается, если расстояние до нее равно текущему уровню (d[v] == level )
- Обход соседей вершин. В случае если вершина u принадлежит V_{node}, значение пути до этой вершины инициализируется d[u] = level + 1. Иначе она помечается для дальнейшей обработки другим процессом.
- Слияние информации по помеченным вершинам (в общем массиве помечаются все вершины, которые были помечены хотя бы один раз)
- Для всех помеченных необработанных (d[v] == -1 ) вершин, принадлежащих V_{node}, расстояние принимается равным level + 1
- Если было обновлено расстояние хотя бы до одной вершины, переход на следующую итерацию, иначе выход из цикла
1.8 Ресурс параллелизма алгоритма
В приведенном варианте алгоритма поиска в ширину граф обходится по слоям, то есть на каждой итерации обрабатывается множество вершин, расстояние до которых одинаково. Число слоев не превосходит n - 1, таким образом, высота ярусно-параллельной формы алгоритма поиска в ширину равна O(n).
Так как поиск блокирующего потока производится последовательно, его высота ярусно-параллельной формы алгоритма совпадает с его последовательной сложностью O(nm).
Так как число шагов алгоритма не превосходит n, высота ЯПФ алгоритма Диница равна O(n^2m).
В описанном алгоритме поиска в ширину вершины разделяются между процессами поровну, поэтому ширина ЯПФ поиска в ширину и алгоритма Диница равна n.
1.9 Входные и выходные данные алгоритма
Входные данные: Граф G(V, E). n вершин v_i и m ребер e_j = (v_j^{(1)}, v_j^{(2)}) с заданной пропускной способностью c_j, а также исток s и сток t.
Объем входных данных: O(m + n).
Выходные данные: величина максимального потока.
Объем выходных данных: O(1).
1.10 Свойства алгоритма
В зависимости от порядка обработки ребер графа, вычисленные блокирующие потоки на соответствующих итерациях могут быть различны, кроме того, может поменяться количество итераций алгоритма Диница.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [2^k, k = 0, 1, ...7];
- число вершин графа [5 000:20 000] с шагом 5000. Количество ребер одинаково для всех графов и равно 2 500 000.
На графике, приведенном ниже, показана зависимость производительности (количество обработанных ребер в единицу времени) от количества процессов и количества вершин графа. Время алгоритма сильно зависит от структуры графа (она влияет на количество итераций алгоритма Диница), поэтому время выполнения алгоритма в общем случае не пропорционально размеру графа.
График зависимости ускорения от количества процессов и количества вершин графа (рис. 4) более нагляден, так как количество итераций в алгоритме не зависит от количества процессов и время выполнения пропорционально числу итераций. По этому графику видно, что ускорение падает с увеличением размера графа.
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