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

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

2022-07-07T06:31:44Z

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

	* C++: [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>.
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.flow.edmonds_karp.html edmonds_karp]</code>): алгоритм Эдмондса–Карпа, сложность <math>O(nm^2)</math>.
	* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/EdmondsKarpMaximumFlow.html EdmondsKarpMaximumFlow]</code>), алгоритм Эдмондса–Карпа, сложность <math>O(nm^2)</math>.

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

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

2018-03-14T14:02:14Z

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

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

			[[en:Ford–Fulkerson algorithm]]

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

2018-03-06T14:20:09Z

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

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

Teplov: /* Информационный граф */

2016-11-18T21:52:15Z

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

← Предыдущая версия		Версия от 21:52, 18 ноября 2016
Строка 48:		Строка 48:

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

			Далее представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма. Информационный граф алгоритма — ориентированный граф, состоящий из вершин, соответствующих операциям алгоритма, и направленных дуг, соответствующих передаче данных (результаты одних операций передаются в качестве аргументов другим операциям) между ними.

			[[file:Max flow.png\|thumb\|center\|1000px\|Рисунок 1 – Информационный граф алгоритма Форда-Фалкерсона]]

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Основной объём вычислений в алгоритме Форда-Фалкерсона приходится на поиск путей от источника к стоку. С этой целью может применяться [[Поиск в ширину (BFS)\|поиск в ширину]], который хорошо распараллеливается. Наилучших результатов можно достичь, если распределить вершины между узлами по слоям примерно одинаковой толщины, так что в каждом слое вершины были бы примерно на одинаковом удалении от источника (такое расслоение также можно найти поиском в ширину).		Основной объём вычислений в алгоритме Форда-Фалкерсона приходится на поиск путей от источника к стоку. С этой целью может применяться [[Поиск в ширину (BFS)\|поиск в ширину]], который хорошо распараллеливается. Наилучших результатов можно достичь, если распределить вершины между узлами по слоям примерно одинаковой толщины, так что в каждом слое вершины были бы примерно на одинаковом удалении от источника (такое расслоение также можно найти поиском в ширину).

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

2015-07-29T11:33:55Z

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

Строка 10:		Строка 10:
	* В алгоритме Диница для выбора кратчайшего пути поддерживается «расслоение» графа, так что поиск в ширину выполняется значительно реже.		* В алгоритме Диница для выбора кратчайшего пути поддерживается «расслоение» графа, так что поиск в ширину выполняется значительно реже.

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

	Математическая постановка задачи приведена в статье «[[Поиск максимального потока в транспортной сети\|Поиск максимального потока в транспортной сети]]», там же введены используемые обозначения.		Математическая постановка задачи приведена в статье «[[Поиск максимального потока в транспортной сети\|Поиск максимального потока в транспортной сети]]», там же введены используемые обозначения.
Строка 31:		Строка 31:

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Строка 48:		Строка 48:

	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Основной объём вычислений в алгоритме Форда-Фалкерсона приходится на поиск путей от источника к стоку. С этой целью может применяться [[Поиск в ширину (BFS)\|поиск в ширину]], который хорошо распараллеливается. Наилучших результатов можно достичь, если распределить вершины между узлами по слоям примерно одинаковой толщины, так что в каждом слое вершины были бы примерно на одинаковом удалении от источника (такое расслоение также можно найти поиском в ширину).		Основной объём вычислений в алгоритме Форда-Фалкерсона приходится на поиск путей от источника к стоку. С этой целью может применяться [[Поиск в ширину (BFS)\|поиск в ширину]], который хорошо распараллеливается. Наилучших результатов можно достичь, если распределить вершины между узлами по слоям примерно одинаковой толщины, так что в каждом слое вершины были бы примерно на одинаковом удалении от источника (такое расслоение также можно найти поиском в ширину).

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

	<references />		<references />

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

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

2015-06-12T21:50:23Z

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

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

	'''Алгоритм Форда-Фалкерсона'''<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>Ford, L R, Jr., and D R Fulkerson. “A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem.” Canadian Journal of Mathematics 9 (1957): 210–18.</ref> (с последующими усовершенствованиями '''Эдмондса-Карпа'''<ref name=~~Edmonds~~>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> и '''Е. А. Диница'''<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>Ford, L R, Jr., and D R Fulkerson. “A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem.” Canadian Journal of Mathematics 9 (1957): 210–18.</ref> (с последующими усовершенствованиями '''Эдмондса-Карпа'''<ref name=EdmondsKarp>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> и '''Е. А. Диница'''<ref>Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.</ref>) предназначен для решения задачи о [[Поиск максимального потока в транспортной сети\|максимальном потоке в транспортной сети]]. Время работы алгоритма <math>O(n^2m)</math> (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих <math>K</math>, сложность <math>O(Km)</math> (для алгоритма Эдмондса–Карпа).

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

Daryin: /* Математическое описание */

2015-06-12T21:43:23Z

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

← Предыдущая версия		Версия от 21:43, 12 июня 2015
Строка 11:		Строка 11:

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

			Математическая постановка задачи приведена в статье «[[Поиск максимального потока в транспортной сети\|Поиск максимального потока в транспортной сети]]», там же введены используемые обозначения.

			Пусть задан некоторый допустимый поток <math>f</math>. ''Дополняющим путём'' называется последовательность рёбер <math>e_0 = (s, v_1), e_1 = (v_1, v_2), \ldots, e_k = (v_k, t)</math>, каждое из которых обладает положительной ''остаточной пропускной способностью'' <math>c_f(e_i) = c(e_i) - f(e_i) > 0</math>.

			Поток останется допустимым, если увеличить его вдоль дополняющего пути на число <math>\delta = \min \{ c(e_i) - f(e_i) \} > 0</math>, при этом величина потока возрастёт на то же число <math>\delta</math>. Для сохранения антисимметричности увеличение потока производится присваиваниями

			:<math>
			f(e_i) \leftarrow f(e_i) + \delta, \quad f(e_i^R) \leftarrow f(e_i^R) - \delta, \quad i = \overline{0, k}.
			</math>

			Если дополняющего пути не существует, то поток <math>f</math> является максимальным.

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

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

2015-06-12T21:25:51Z

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

← Предыдущая версия		Версия от 21:25, 12 июня 2015
Строка 12:		Строка 12:
	=== Математическое описание ===		=== Математическое описание ===
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

			Вычислительными ядрами, на которые приходится наибольший объём вычислений, являются:
			* [[Поиск в ширину (BFS)\|поиск в ширину]];
			* увеличение потока вдоль дополняющего пути.

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== Описание схемы реализации последовательного алгоритма ===		=== Описание схемы реализации последовательного алгоритма ===

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

2015-06-12T21:21:52Z

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

@@ Строка 15: / Строка 15: @@
 === Описание схемы реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===
 === Информационный граф ===
 === Описание ресурса параллелизма алгоритма ===

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

2015-06-12T21:02:33Z

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

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

	'''Алгоритм Форда-Фалкерсона'''<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>Ford, L R, Jr., and D R Fulkerson. “A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem.” Canadian Journal of Mathematics 9 (1957): 210–18.</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> и '''Е. А. Диница'''<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>Ford, L R, Jr., and D R Fulkerson. “A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem.” Canadian Journal of Mathematics 9 (1957): 210–18.</ref> (с последующими усовершенствованиями '''Эдмондса-Карпа'''<ref name=Edmonds>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> и '''Е. А. Диница'''<ref>Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.</ref>) предназначен для решения задачи о [[Поиск максимального потока в транспортной сети\|максимальном потоке в транспортной сети]]. Время работы алгоритма <math>O(n^2m)</math> (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих <math>K</math>, сложность <math>O(Km)</math> (для алгоритма Эдмондса–Карпа).

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

	* В исходном алгоритме Форда–Фалкерсона способ выбора дополняющего пути не уточнялся.		* В исходном алгоритме Форда–Фалкерсона способ выбора дополняющего пути не уточнялся.
	* В алгоритме ~~Эдмонса~~-Карпа выбирается кратчайший дополняющий путь, для чего используется [[Поиск в ширину (BFS)\|поиск в ширину]] на каждой итерации;		* В алгоритме Эдмондса-Карпа выбирается кратчайший дополняющий путь, для чего используется [[Поиск в ширину (BFS)\|поиск в ширину]] на каждой итерации;
	* В алгоритме Диница для выбора кратчайшего пути поддерживается «расслоение» графа, так что поиск в ширину выполняется значительно реже.		* В алгоритме Диница для выбора кратчайшего пути поддерживается «расслоение» графа, так что поиск в ширину выполняется значительно реже.