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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 3: Строка 3:
  
 
'''Алгоритм Форда-Фалкерсона'''<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>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>.
 +
 +
Алгоритм последовательно улучшает допустимый поток, находя так называемый ''дополняющий путь'' и увеличивая поток вдоль этого пути. Варианты алгоритма отличаются способом нахождения дополняющего пути.
 +
 +
* В исходном алгоритме Форда–Фалкерсона способ выбора дополняющего пути не уточнялся.
 +
* В алгоритме Эдмонса-Карпа выбирается кратчайший дополняющий путь, для чего используется [[Поиск в ширину (BFS)|поиск в ширину]] на каждой итерации;
 +
* В алгоритме Диница для выбора кратчайшего пути поддерживается «расслоение» графа, так что поиск в ширину выполняется значительно реже.
  
 
=== Математическое описание ===
 
=== Математическое описание ===

Версия 23:42, 12 июня 2015

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

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

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

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

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

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 Существующие реализации алгоритма

  • 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 Литература

  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. ↑ 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.
  3. ↑ Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.
Источник — https://algowiki-project.org/w/ru/index.php?title=Алгоритм_Форда-Фалкерсона&oldid=1939