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

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

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

Текущая версия на 09:43, 7 июля 2022

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

↑ 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)|поиска в ширину]] от вершины-источника потока, так чтобы на каждом процессоре обрабатывалось примерно одинаковое количество вершин одного и того же расстояния от источника.
-=== Описание входных и выходных данных ===
+=== Входные и выходные данные алгоритма ===
-=== Свойства алгоритма===
+=== Свойства алгоритма ===
-== Программная реализация алгоритмов ==
+== Программная реализация алгоритма ==
 === Особенности реализации последовательного алгоритма ===
-=== Описание локальности данных и вычислений ===
+=== Возможные способы и особенности параллельной реализации алгоритма ===
-=== Возможные способы и особенности реализации параллельного алгоритма ===
+=== Результаты прогонов ===
-=== Масштабируемость алгоритма и его реализации ===
-=== Динамические характеристики и эффективность реализации алгоритма ===
 === Выводы для классов архитектур ===
-=== Существующие реализации алгоритма ===
 == Литература ==
 <references />
+[[Категория:Начатые статьи]]
+[[en:Preflow-Push algorithm]]