Алгоритм Форда-Фалкерсона: различия между версиями

[непроверенная версия]

Версия 00:21, 13 июня 2015

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритмов
3 Литература

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Форда-Фалкерсона^[1]^[2] (с последующими усовершенствованиями Эдмондса-Карпа^[3] и Е. А. Диница^[4]) предназначен для решения задачи о максимальном потоке в транспортной сети. Время работы алгоритма [math]O(n^2m)[/math] (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих [math]K[/math], сложность [math]O(Km)[/math] (для алгоритма Эдмондса–Карпа).

Алгоритм последовательно улучшает допустимый поток, находя так называемый дополняющий путь и увеличивая поток вдоль этого пути. Варианты алгоритма отличаются способом нахождения дополняющего пути.

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

1.2 Математическое описание

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Описание схемы реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

В статье Эдмондса–Карпа^[5] (теорема 1) доказано, что количество последовательно построенных кратчайших дополнительных путей не превосходит [math]m(n + 1)/2 = O(mn)[/math]. Основными операциями алгоритма являются поиск в ширину сложностью [math]O(m)[/math] и обновление потока вдоль дополняющего пути сложностью [math]O(n)[/math].

В алгоритме Эдмондса–Карпа выполняются следующие операции:

поиск в ширину и определение кратчайшего пути на каждой итерации, сложность [math]O(m + n)[/math], общая сложность [math]O(m^2n)[/math];
обновление потока вдоль дополняющего пути, сложность [math]O(n)[/math], общая сложность [math]O(n^2 m)[/math].

Таким образом, общая сложность составляет [math]O(m^2n)[/math].

В алгоритме Диница выполняются следующие операции:

поиск кратчайшего пути и обновление потока вдоль дополняющего пути на каждой итерации, сложность [math]O(n)[/math], общая сложность [math]O(mn^2)[/math];
обновление расслоения на каждой итерации, сложность [math]O(1)[/math], общая сложность [math]O(mn)[/math];
поиск в ширину для построения нового расслоения, сложность [math]O(m)[/math], число построений не более [math]n[/math], общая сложность [math]O(mn)[/math].

Таким образом, общая сложность составляет [math]O(mn^2)[/math].

1.7 Информационный граф

1.8 Описание ресурса параллелизма алгоритма

Основной объём вычислений в алгоритме Форда-Фалкерсона приходится на поиск путей от источника к стоку. С этой целью может применяться поиск в ширину, который хорошо распараллеливается. Наилучших результатов можно достичь, если распределить вершины между узлами по слоям примерно одинаковой толщины, так что в каждом слое вершины были бы примерно на одинаковом удалении от источника (такое расслоение также можно найти поиском в ширину).

1.9 Описание входных и выходных данных

1.10 Свойства алгоритма

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

C++: Boost Graph Library (функция edmonds_karp_max_flow): алгоритм Эдмондса–Карпа, сложность [math]O(nm^2)[/math] для действительных весов и [math]O(Kmn)[/math] для целых, не превосходящих [math]K[/math].
Python: NetworkX (функция edmonds_karp): алгоритм Эдмондса–Карпа, сложность [math]O(nm^2)[/math].
Java: JGraphT (класс EdmondsKarpMaximumFlow), алгоритм Эдмондса–Карпа, сложность [math]O(nm^2)[/math].

3 Литература

↑ Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.
↑ Ford, L R, Jr., and D R Fulkerson. “A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem.” Canadian Journal of Mathematics 9 (1957): 210–18.
↑ Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.
↑ Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.
↑ Ошибка цитирования Неверный тег <ref>; для сносок EdmondsKarp не указан текст

[1] Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.

[2] Ford, L R, Jr., and D R Fulkerson. “A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem.” Canadian Journal of Mathematics 9 (1957): 210–18.

[Edmonds-3] Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.

[4] Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.

[EdmondsKarp-5] Ошибка цитирования Неверный тег <ref>; для сносок EdmondsKarp не указан текст

[1]

[2]

[3]

[4]

[5]

@@ Строка 15: / Строка 15: @@
 === Описание схемы реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===
+В статье Эдмондса–Карпа<ref name=EdmondsKarp /> (теорема 1) доказано, что количество последовательно построенных кратчайших дополнительных путей не превосходит <math>m(n + 1)/2 = O(mn)</math>. Основными операциями алгоритма являются поиск в ширину сложностью <math>O(m)</math> и обновление потока вдоль дополняющего пути сложностью <math>O(n)</math>.
+В '''алгоритме Эдмондса–Карпа''' выполняются следующие операции:
+* поиск в ширину и определение кратчайшего пути на каждой итерации, сложность <math>O(m + n)</math>, общая сложность <math>O(m^2n)</math>;
+* обновление потока вдоль дополняющего пути, сложность <math>O(n)</math>, общая сложность <math>O(n^2 m)</math>.
+Таким образом, общая сложность составляет <math>O(m^2n)</math>.
+В '''алгоритме Диница''' выполняются следующие операции:
+* поиск кратчайшего пути и обновление потока вдоль дополняющего пути на каждой итерации, сложность <math>O(n)</math>, общая сложность <math>O(mn^2)</math>;
+* обновление расслоения на каждой итерации, сложность <math>O(1)</math>, общая сложность <math>O(mn)</math>;
+* поиск в ширину для построения нового расслоения, сложность <math>O(m)</math>, число построений не более <math>n</math>, общая сложность <math>O(mn)</math>.
+Таким образом, общая сложность составляет <math>O(mn^2)</math>.
 === Информационный граф ===
 === Описание ресурса параллелизма алгоритма ===