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

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

[досмотренная версия]

Текущая версия от 06:43, 7 июля 2022

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

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

Алгоритм проталкивания предпотока^[1] (англ. Push-Relabel Method, или Preflow-Push Method) предназначен для решения задачи о максимальном потоке в транспортной сети. Время работы алгоритма [math]\displaystyle{ O(mn \ln n) }[/math] (при использовании динамических деревьев Тарьяна-Слитора^[2]^[3]).

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

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

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

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

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

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

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

Алгоритм основан на локальных операциях и допускает распараллеливание, в том числе на распределённых системах^[4]. Распределение вершин графа по процессорам может производиться на основе результатов предварительного поиска в ширину от вершины-источника потока, так чтобы на каждом процессоре обрабатывалось примерно одинаковое количество вершин одного и того же расстояния от источника.

Входные и выходные данные алгоритма

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

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

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

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

Результаты прогонов

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

Литература

↑ Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.
↑ Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.
↑ Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.
↑ Jiang, Jincheng, and Lixin Wu. “A MPI Parallel Algorithm for the Maximum Flow Problem ,” Geocomputation 2013.

[1] Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.

[2] Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.

[3] Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.

[4] Jiang, Jincheng, and Lixin Wu. “A MPI Parallel Algorithm for the Maximum Flow Problem ,” Geocomputation 2013.

[1]

[2]

[3]

[4]

@@ Строка 1: / Строка 1: @@
-== Свойства и структура алгоритмов ==
+{{level-a}}
+== Свойства и структура алгоритма ==
 === Общее описание алгоритма ===
 '''Алгоритм проталкивания предпотока'''<ref>Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.</ref> (англ. Push-Relabel Method, или Preflow-Push Method) предназначен для решения задачи о [[Поиск максимального потока в транспортной сети|максимальном потоке в транспортной сети]]. Время работы алгоритма <math>O(mn \ln n)</math> (при использовании динамических деревьев Тарьяна-Слитора<ref>Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.</ref><ref>Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.</ref>).
-=== Математическое описание ===
+=== Математическое описание алгоритма ===
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===
-=== Описание схемы реализации последовательного алгоритма ===
+=== Схема реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===
 === Информационный граф ===
-=== Описание ресурса параллелизма алгоритма ===
+=== Ресурс параллелизма алгоритма ===
 Алгоритм основан на локальных операциях и допускает распараллеливание, в том числе на распределённых системах<ref>Jiang, Jincheng, and Lixin Wu. “A MPI Parallel Algorithm for the Maximum Flow Problem ,” Geocomputation 2013.</ref>. Распределение вершин графа по процессорам может производиться на основе результатов предварительного [[Поиск в ширину (BFS)|поиска в ширину]] от вершины-источника потока, так чтобы на каждом процессоре обрабатывалось примерно одинаковое количество вершин одного и того же расстояния от источника.
-=== Описание входных и выходных данных ===
+=== Входные и выходные данные алгоритма ===
-=== Свойства алгоритма===
+=== Свойства алгоритма ===
-== Программная реализация алгоритмов ==
+== Программная реализация алгоритма ==
 === Особенности реализации последовательного алгоритма ===
-=== Описание локальности данных и вычислений ===
+=== Возможные способы и особенности параллельной реализации алгоритма ===
-=== Возможные способы и особенности реализации параллельного алгоритма ===
+=== Результаты прогонов ===
-=== Масштабируемость алгоритма и его реализации ===
-=== Динамические характеристики и эффективность реализации алгоритма ===
 === Выводы для классов архитектур ===
-=== Существующие реализации алгоритма ===
-* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/push_relabel_max_flow.html push_relabel_max_flow]</code>), сложность <math>O(n^3)</math>.
 == Литература ==
 <references />
+[[Категория:Начатые статьи]]
+[[en:Preflow-Push algorithm]]