Алгоритм Гопкрофта-Карпа: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| (не показано 8 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | == Свойства и структура | + | {{level-a}} |
| + | |||
| + | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Гопкрофта-Карпа'''<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>v \in V</math> называется свободной, если она не принадлежит ни одному ребру из <math>M</math>. Простой путь | ||
| + | :<math> | ||
| + | P: e_1 = (v_1, v_2), e_2 = (v_2, v_3), \ldots, e_{2k-1} = (v_{2k-1}, v_{2k}) | ||
| + | </math> | ||
| + | называется ''увеличивающей цепью'', если его концы <math>v_1</math> и <math>v_{2k}</math> – свободные вершины, а каждое второе ребро принадлежит текущему паросочетанию: | ||
| + | :<math> | ||
| + | e_2, e_4, \ldots, e_{2k-2} \in M. | ||
| + | </math> | ||
| + | Паросочетание <math>M</math> является максимальным, если для него не существует увеличивающей цепи. | ||
| + | |||
| + | Множество <math>M'</math>, полученное заменой в <math>M</math> рёбер <math>e_2, e_4, \ldots, e_{2k-2}</math> на рёбра <math>e_1, e_3, \ldots, e_{2k-1}</math>, является паросочетанием и содержит на одно ребро больше, чем <math>M</math>. Множество <math>M' = M \mathop{\Delta} P</math>, где <math>\mathop{\Delta}</math> обозначает операцию симметрической разности множеств. | ||
| + | |||
| + | На каждом шаге алгоритма Гопкрофта-Карпа строится максимальное по включению множество кратчайших увеличивающих цепей <math>\{ P_1, \ldots, P_q \}</math>, не пересекающихся по вершинам, и текущее паросочетание <math>M</math> заменяется на <math>M = M \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q</math>. Гарантируется, что число шагов не превышает <math>2 (\sqrt{\mu} + 1) = O(\sqrt{n})</math>, где <math>\mu</math> – число рёбер максимального паросочетания. | ||
| + | |||
| + | Для поиска максимального множества кратчайших увеличивающих цепей применяется [[Поиск в ширину (BFS)|поиск в ширину]] с последующим [[Поиск в глубину (DFS)|поиском в глубину]]. | ||
| + | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| + | Основная вычислительная сложность алгоритма приходится на операции [[Поиск в ширину (BFS)|поиска в ширину]] и [[Поиск в глубину (DFS)|поиска в глубину]]. | ||
| + | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | |
| + | # Выбрать начальное паросочетание <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. | ||
| + | |||
| + | === Схема реализации последовательного алгоритма === | ||
| + | |||
| + | Опишем, каким образом ищется максимальное множество кратчайших увеличивающих цепей на втором шаге алгоритма. | ||
| + | |||
| + | Пусть <math>G = (V, E)</math> – двудольный граф с разбиением вершин <math>V = X \sqcup Y</math>, а <math>M</math> – текущее паросочетание в нём. Обозначим через <math>X_f \subseteq X</math> и <math>Y_f \subseteq Y</math> соответствующие множества свободных вершин. | ||
| + | |||
| + | # Если одно из множеств <math>X_f</math> или <math>Y_f</math> пусто, то увеличивающих цепей не существует. | ||
| + | # Ориентируем рёбра <math>G</math> следующим образом: | ||
| + | #* рёбра из <math>M</math> идут из <math>X</math> в <math>Y</math>; | ||
| + | #* все остальные рёбра идут из <math>Y</math> в <math>X</math>. | ||
| + | # Выполним один [[Поиск в ширину (BFS)|поиск в ширину]] на полученном ориентированном графе, двигаясь от множества вершин <math>X_f</math> в обратном направлении. | ||
| + | #* Поиск останавливается на том шаге, на котором будет посещена хотя бы одна из вершин в <math>Y_f</math>. | ||
| + | #* Если поиск будет завершён без посещения одной из вершин <math>Y_f</math>, то увеличивающих цепей не существует. | ||
| + | #* Пометим вершины и рёбра, посещённые в ходе поиска в ширину. | ||
| + | # Для каждой из свободных вершин <math>y \in Y_f</math> выполним [[Поиск в глубину (DFS)|поиск в глубину]] в прямом направлении, двигаясь только по помеченным рёбрам и вершинам. | ||
| + | #* Снимем пометку с посещённых рёбер и вершин. | ||
| + | #* Если на очередном шаге посещена вершина <math>x \in X_f</math>, то поиск останавливается, а текущее содержимое стека определяет кратчайшую увеличивающую цепь от <math>y</math> к <math>x</math>. | ||
| + | #* Если поиск в глубину завершается без посещения множества <math>X_f</math>, то для данной вершины <math>y</math> увеличивающей цепи не существует, и необходимо перейти к следующей свободной вершине. | ||
| + | |||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | Алгоритм выполняет не более <math>O(\sqrt{n})</math> шагов, на каждом из которых производятся поиск в ширину и поиск в глубину сложностью <math>O(m)</math>. Таким образом, общая сложность составляет <math>O(m \sqrt{n})</math>. | ||
| + | |||
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
| − | === | + | === Входные и выходные данные алгоритма === |
| − | === Свойства алгоритма=== | + | === Свойства алгоритма === |
| − | == Программная реализация | + | |
| + | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | + | === Возможные способы и особенности параллельной реализации алгоритма === | |
| − | === Возможные способы и особенности реализации | + | === Результаты прогонов === |
| − | === | ||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
| − | |||
| − | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
| + | |||
| + | [[Категория:Начатые статьи]] | ||
| + | |||
| + | [[en:Hopcroft–Karp algorithm]] | ||
Текущая версия на 09:56, 7 июля 2022
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм Гопкрофта-Карпа[1] предназначен для решения задачи о назначениях в случае единичных цен. По заданному двудольному графу алгоритм находит максимальное паросочетание за время [math]O(m \sqrt{n})[/math].
1.2 Математическое описание алгоритма
Граф [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]v \in V[/math] называется свободной, если она не принадлежит ни одному ребру из [math]M[/math]. Простой путь
- [math] P: e_1 = (v_1, v_2), e_2 = (v_2, v_3), \ldots, e_{2k-1} = (v_{2k-1}, v_{2k}) [/math]
называется увеличивающей цепью, если его концы [math]v_1[/math] и [math]v_{2k}[/math] – свободные вершины, а каждое второе ребро принадлежит текущему паросочетанию:
- [math] e_2, e_4, \ldots, e_{2k-2} \in M. [/math]
Паросочетание [math]M[/math] является максимальным, если для него не существует увеличивающей цепи.
Множество [math]M'[/math], полученное заменой в [math]M[/math] рёбер [math]e_2, e_4, \ldots, e_{2k-2}[/math] на рёбра [math]e_1, e_3, \ldots, e_{2k-1}[/math], является паросочетанием и содержит на одно ребро больше, чем [math]M[/math]. Множество [math]M' = M \mathop{\Delta} P[/math], где [math]\mathop{\Delta}[/math] обозначает операцию симметрической разности множеств.
На каждом шаге алгоритма Гопкрофта-Карпа строится максимальное по включению множество кратчайших увеличивающих цепей [math]\{ P_1, \ldots, P_q \}[/math], не пересекающихся по вершинам, и текущее паросочетание [math]M[/math] заменяется на [math]M = M \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q[/math]. Гарантируется, что число шагов не превышает [math]2 (\sqrt{\mu} + 1) = O(\sqrt{n})[/math], где [math]\mu[/math] – число рёбер максимального паросочетания.
Для поиска максимального множества кратчайших увеличивающих цепей применяется поиск в ширину с последующим поиском в глубину.
1.3 Вычислительное ядро алгоритма
Основная вычислительная сложность алгоритма приходится на операции поиска в ширину и поиска в глубину.
1.4 Макроструктура алгоритма
- Выбрать начальное паросочетание [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.
1.5 Схема реализации последовательного алгоритма
Опишем, каким образом ищется максимальное множество кратчайших увеличивающих цепей на втором шаге алгоритма.
Пусть [math]G = (V, E)[/math] – двудольный граф с разбиением вершин [math]V = X \sqcup Y[/math], а [math]M[/math] – текущее паросочетание в нём. Обозначим через [math]X_f \subseteq X[/math] и [math]Y_f \subseteq Y[/math] соответствующие множества свободных вершин.
- Если одно из множеств [math]X_f[/math] или [math]Y_f[/math] пусто, то увеличивающих цепей не существует.
- Ориентируем рёбра [math]G[/math] следующим образом:
- рёбра из [math]M[/math] идут из [math]X[/math] в [math]Y[/math];
- все остальные рёбра идут из [math]Y[/math] в [math]X[/math].
- Выполним один поиск в ширину на полученном ориентированном графе, двигаясь от множества вершин [math]X_f[/math] в обратном направлении.
- Поиск останавливается на том шаге, на котором будет посещена хотя бы одна из вершин в [math]Y_f[/math].
- Если поиск будет завершён без посещения одной из вершин [math]Y_f[/math], то увеличивающих цепей не существует.
- Пометим вершины и рёбра, посещённые в ходе поиска в ширину.
- Для каждой из свободных вершин [math]y \in Y_f[/math] выполним поиск в глубину в прямом направлении, двигаясь только по помеченным рёбрам и вершинам.
- Снимем пометку с посещённых рёбер и вершин.
- Если на очередном шаге посещена вершина [math]x \in X_f[/math], то поиск останавливается, а текущее содержимое стека определяет кратчайшую увеличивающую цепь от [math]y[/math] к [math]x[/math].
- Если поиск в глубину завершается без посещения множества [math]X_f[/math], то для данной вершины [math]y[/math] увеличивающей цепи не существует, и необходимо перейти к следующей свободной вершине.
1.6 Последовательная сложность алгоритма
Алгоритм выполняет не более [math]O(\sqrt{n})[/math] шагов, на каждом из которых производятся поиск в ширину и поиск в глубину сложностью [math]O(m)[/math]. Таким образом, общая сложность составляет [math]O(m \sqrt{n})[/math].
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ 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.
