Алгоритм Форда-Фалкерсона: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/edmonds_karp_max_flow.html edmonds_karp_max_flow]</code>): алгоритм Эдмонса–Карпа, сложность <math>O(nm^2)</math> для действительных весов и <math>O(Kmn)</math>. | * [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/edmonds_karp_max_flow.html edmonds_karp_max_flow]</code>): алгоритм Эдмонса–Карпа, сложность <math>O(nm^2)</math> для действительных весов и <math>O(Kmn)</math> для целых, не превосходящих <math>K</math>. | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия от 23:18, 10 июня 2015
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Форда-Фалкерсона[1] (с последующими усовершенствованиями Эдмондса-Карпа[2] и Е. А. Диница[3]) предназначен для решения задачи о максимальном потоке в транспортной сети. Время работы алгоритма [math]\displaystyle{ O(n^2m) }[/math] (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих [math]\displaystyle{ K }[/math], сложность [math]\displaystyle{ O(Km) }[/math].
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Описание ресурса параллелизма алгоритма
Основной объём вычислений в алгоритме Форда-Фалкерсона приходится на поиск путей от источника к стоку. С этой целью может применяться поиск в ширину, который хорошо распараллеливается. Наилучших результатов можно достичь, если распределить вершины между узлами по слоям примерно одинаковой толщина, так что в каждом слое вершины были бы примерно на одинаковом удалении от источника (такое расслоение также можно найти поиском в ширину).
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Boost Graph Library (функция
edmonds_karp_max_flow): алгоритм Эдмонса–Карпа, сложность [math]\displaystyle{ O(nm^2) }[/math] для действительных весов и [math]\displaystyle{ O(Kmn) }[/math] для целых, не превосходящих [math]\displaystyle{ K }[/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.
- ↑ 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.