Алгоритм Гопкрофта-Карпа - История изменений

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

2022-07-07T06:56:04Z

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

	* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/HopcroftKarpBipartiteMatching.html HopcroftKarpBipartiteMatching]</code>).

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

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

2018-03-14T14:11:09Z

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

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

			[[en:Hopcroft–Karp algorithm]]

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

2018-03-06T14:21:49Z

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

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

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

2015-07-29T11:41:48Z

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

	'''Алгоритм Гопкрофта-Карпа'''<ref>Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.</ref> предназначен для решения [[Задача о назначениях\|задачи о назначениях]] в случае единичных цен. По заданному двудольному графу алгоритм находит максимальное паросочетание за время <math>O(m \sqrt{n})</math>.		'''Алгоритм Гопкрофта-Карпа'''<ref>Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.</ref> предназначен для решения [[Задача о назначениях\|задачи о назначениях]] в случае единичных цен. По заданному двудольному графу алгоритм находит максимальное паросочетание за время <math>O(m \sqrt{n})</math>.

	=== Математическое описание ===		=== Математическое описание алгоритма ===
	Граф <math>G = (V, E)</math> называется ''двудольным'', если его вершины можно разделить на две части <math>V = X \sqcup Y</math>, так что каждое ребро <math>e \in E</math> соединяет вершины из <math>X</math> и <math>Y</math>. Набор рёбер <math>M \subseteq E</math> называется ''паросочетанием'', если каждая вершина <math>v \in V</math> принадлежит не более чем одному ребру из <math>M</math>. Требуется найти '''максимальное паросочетание''' – паросочетание с максимально возможным числом рёбер.		Граф <math>G = (V, E)</math> называется ''двудольным'', если его вершины можно разделить на две части <math>V = X \sqcup Y</math>, так что каждое ребро <math>e \in E</math> соединяет вершины из <math>X</math> и <math>Y</math>. Набор рёбер <math>M \subseteq E</math> называется ''паросочетанием'', если каждая вершина <math>v \in V</math> принадлежит не более чем одному ребру из <math>M</math>. Требуется найти '''максимальное паросочетание''' – паросочетание с максимально возможным числом рёбер.

Строка 32:		Строка 32:
	# Составить новое паросочетание <math>M_{i + 1} = M_i \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q</math> и перейти к шагу 2.		# Составить новое паросочетание <math>M_{i + 1} = M_i \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q</math> и перейти к шагу 2.

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

	Опишем, каким образом ищется максимальное множество кратчайших увеличивающих цепей на втором шаге алгоритма.		Опишем, каким образом ищется максимальное множество кратчайших увеличивающих цепей на втором шаге алгоритма.
Строка 55:		Строка 55:

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

	<references />		<references />

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

Daryin: /* Описание схемы реализации последовательного алгоритма */

2015-06-25T12:19:19Z

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

@@ Строка 33: / Строка 33: @@
 === Описание схемы реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===
 Алгоритм выполняет не более <math>O(\sqrt{n})</math> шагов, на каждом из которых производятся поиск в ширину и поиск в глубину сложностью <math>O(m)</math>. Таким образом, общая сложность составляет <math>O(m \sqrt{n})</math>.

Daryin: /* Макроструктура алгоритма */

2015-06-25T11:26:09Z

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

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

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

			# Выбрать начальное паросочетание <math>M_0</math> (например, <math>M_0 = \emptyset</math> или паросочетание, полученное жадным алгоритмом).
			# Вычислить максимальное по включение множество кратчайших увеличивающих цепей <math>\{ P_1, \ldots, P_q \}</math>, не пересекающихся по вершинам. Если улучшающих цепей не существует, остановиться: текущее паросочетание <math>M_i</math> является максимальным.
			# Составить новое паросочетание <math>M_{i + 1} = M_i \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q</math> и перейти к шагу 2.

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

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

2015-06-24T21:11:51Z

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

← Предыдущая версия		Версия от 21:11, 24 июня 2015
Строка 29:		Строка 29:
	=== Описание схемы реализации последовательного алгоритма ===		=== Описание схемы реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
			Алгоритм выполняет не более <math>O(\sqrt{n})</math> шагов, на каждом из которых производятся поиск в ширину и поиск в глубину сложностью <math>O(m)</math>. Таким образом, общая сложность составляет <math>O(m \sqrt{n})</math>.

	=== Информационный граф ===		=== Информационный граф ===
	=== Описание ресурса параллелизма алгоритма ===		=== Описание ресурса параллелизма алгоритма ===

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

2015-06-24T21:09:54Z

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

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

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
			Основная вычислительная сложность алгоритма приходится на операции [[Поиск в ширину (BFS)\|поиска в ширину]] и [[Поиск в глубину (DFS)\|поиска в глубину]].

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

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

2015-06-24T21:09:00Z

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

@@ Строка 5: / Строка 5: @@
 === Математическое описание ===
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===

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

2015-06-11T19:45:44Z

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

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

			* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/HopcroftKarpBipartiteMatching.html HopcroftKarpBipartiteMatching]</code>).

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

	<references />		<references />