Алгоритм проталкивания предпотока - История изменений

ASA в 06:43, 7 июля 2022

2022-07-07T06:43:17Z

← Предыдущая версия		Версия от 06:43, 7 июля 2022
Строка 21:		Строка 21:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	* C++: [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>.
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.flow.preflow_push.html preflow_push]</code>): алгоритм highest-label preflow-push, сложность <math>O(n^2\sqrt{m})</math>.

	== Литература ==		== Литература ==

ASA в 14:05, 14 марта 2018

2018-03-14T14:05:23Z

← Предыдущая версия		Версия от 14:05, 14 марта 2018
Строка 41:		Строка 41:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Preflow-Push algorithm]]

ASA в 14:20, 6 марта 2018

2018-03-06T14:20:29Z

← Предыдущая версия		Версия от 14:20, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

ASA в 11:38, 29 июля 2015

2015-07-29T11:38:14Z

← Предыдущая версия		Версия от 11:38, 29 июля 2015
Строка 1:		Строка 1:
	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Алгоритм проталкивания предпотока'''<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>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)\|поиска в ширину]] от вершины-источника потока, так чтобы на каждом процессоре обрабатывалось примерно одинаковое количество вершин одного и того же расстояния от источника.		Алгоритм основан на локальных операциях и допускает распараллеливание, в том числе на распределённых системах<ref>Jiang, Jincheng, and Lixin Wu. “A MPI Parallel Algorithm for the Maximum Flow Problem ,” Geocomputation 2013.</ref>. Распределение вершин графа по процессорам может производиться на основе результатов предварительного [[Поиск в ширину (BFS)\|поиска в ширину]] от вершины-источника потока, так чтобы на каждом процессоре обрабатывалось примерно одинаковое количество вершин одного и того же расстояния от источника.

	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма===		=== Свойства алгоритма ===
	== Программная реализация ~~алгоритмов~~ ==
			== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		==== Локальность реализации алгоритма ====
			===== Структура обращений в память и качественная оценка локальности =====
			===== Количественная оценка локальности =====
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
Строка 31:		Строка 37:

	<references />		<references />

			[[Категория:Начатые статьи]]

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

2015-06-11T18:31:22Z

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

← Предыдущая версия		Версия от 18:31, 11 июня 2015
Строка 25:		Строка 25:
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

	* [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>.		* C++: [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>.
			* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.flow.preflow_push.html preflow_push]</code>): алгоритм highest-label preflow-push, сложность <math>O(n^2\sqrt{m})</math>.

	== Литература ==		== Литература ==

	<references />		<references />

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

2015-06-10T23:21:07Z

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

← Предыдущая версия		Версия от 23:21, 10 июня 2015
Строка 24:		Строка 24:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			* [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 />		<references />

Daryin: /* Общее описание алгоритма */

2015-06-09T20:56:40Z

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

← Предыдущая версия		Версия от 20:56, 9 июня 2015
Строка 2:		Строка 2:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Алгоритм проталкивания предпотока'''<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>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>).

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

Daryin: Отмена правки 1788, сделанной участником Daryin (обс.)

2015-06-09T20:56:19Z

Отмена правки 1788, сделанной участником Daryin (обс.)

← Предыдущая версия		Версия от 20:56, 9 июня 2015
Строка 2:		Строка 2:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	[[Поиск максимального потока в ~~транспортной сети~~\|максимальном потоке в ~~транспортной сети~~]]		'''Алгоритм проталкивания предпотока'''<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>).

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

Daryin: /* Общее описание алгоритма */

2015-06-09T20:55:35Z

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

← Предыдущая версия		Версия от 20:55, 9 июня 2015
Строка 2:		Строка 2:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Алгоритм проталкивания предпотока'''<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>).		[[Поиск максимального потока в транспортной сети\|максимальном потоке в транспортной сети]]

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

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

2015-06-08T23:14:58Z

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

Новая страница

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Алгоритм проталкивания предпотока'''<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 />