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

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

Версия от 20:45, 12 июня 2015

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

↑ 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.

[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.

[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.

[1]

[2]

[3]

[4]

@@ Строка 2: / Строка 2: @@
 === Общее описание алгоритма ===
-'''Алгоритм Форда-Фалкерсона'''<ref>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.</ref> (с последующими усовершенствованиями '''Эдмондса-Карпа'''<ref>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.</ref> и '''Е.&nbsp;А.&nbsp;Диница'''<ref>Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.</ref>) предназначен для решения задачи о [[Поиск максимального потока в транспортной сети|максимальном потоке в транспортной сети]]. Время работы алгоритма <math>O(n^2m)</math> (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих <math>K</math>, сложность <math>O(Km)</math>.
+'''Алгоритм Форда-Фалкерсона'''<ref>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.</ref><ref>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.</ref> (с последующими усовершенствованиями '''Эдмондса-Карпа'''<ref>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.</ref> и '''Е.&nbsp;А.&nbsp;Диница'''<ref>Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.</ref>) предназначен для решения задачи о [[Поиск максимального потока в транспортной сети|максимальном потоке в транспортной сети]]. Время работы алгоритма <math>O(n^2m)</math> (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих <math>K</math>, сложность <math>O(Km)</math> (для алгоритма Эдмонса–Карпа).
 Алгоритм последовательно улучшает допустимый поток, находя так называемый ''дополняющий путь'' и увеличивая поток вдоль этого пути. Варианты алгоритма отличаются способом нахождения дополняющего пути.