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

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

Версия от 12:19, 25 июня 2015

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

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

Алгоритм Гопкрофта-Карпа^[1] предназначен для решения задачи о назначениях в случае единичных цен. По заданному двудольному графу алгоритм находит максимальное паросочетание за время [math]\displaystyle{ O(m \sqrt{n}) }[/math].

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

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

Вершина [math]\displaystyle{ v \in V }[/math] называется свободной, если она не принадлежит ни одному ребру из [math]\displaystyle{ M }[/math]. Простой путь

[math]\displaystyle{ P: e_1 = (v_1, v_2), e_2 = (v_2, v_3), \ldots, e_{2k-1} = (v_{2k-1}, v_{2k}) }[/math]

называется увеличивающей цепью, если его концы [math]\displaystyle{ v_1 }[/math] и [math]\displaystyle{ v_{2k} }[/math] – свободные вершины, а каждое второе ребро принадлежит текущему паросочетанию:

[math]\displaystyle{ e_2, e_4, \ldots, e_{2k-2} \in M. }[/math]

Паросочетание [math]\displaystyle{ M }[/math] является максимальным, если для него не существует увеличивающей цепи.

Множество [math]\displaystyle{ M' }[/math], полученное заменой в [math]\displaystyle{ M }[/math] рёбер [math]\displaystyle{ e_2, e_4, \ldots, e_{2k-2} }[/math] на рёбра [math]\displaystyle{ e_1, e_3, \ldots, e_{2k-1} }[/math], является паросочетанием и содержит на одно ребро больше, чем [math]\displaystyle{ M }[/math]. Множество [math]\displaystyle{ M' = M \mathop{\Delta} P }[/math], где [math]\displaystyle{ \mathop{\Delta} }[/math] обозначает операцию симметрической разности множеств.

На каждом шаге алгоритма Гопкрофта-Карпа строится максимальное по включению множество кратчайших увеличивающих цепей [math]\displaystyle{ \{ P_1, \ldots, P_q \} }[/math], не пересекающихся по вершинам, и текущее паросочетание [math]\displaystyle{ M }[/math] заменяется на [math]\displaystyle{ M = M \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q }[/math]. Гарантируется, что число шагов не превышает [math]\displaystyle{ 2 (\sqrt{\mu} + 1) = O(\sqrt{n}) }[/math], где [math]\displaystyle{ \mu }[/math] – число рёбер максимального паросочетания.

Для поиска максимального множества кратчайших увеличивающих цепей применяется поиск в ширину с последующим поиском в глубину.

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

Основная вычислительная сложность алгоритма приходится на операции поиска в ширину и поиска в глубину.

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

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

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

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

Пусть [math]\displaystyle{ G = (V, E) }[/math] – двудольный граф с разбиением вершин [math]\displaystyle{ V = X \sqcup Y }[/math], а [math]\displaystyle{ M }[/math] – текущее паросочетание в нём. Обозначим через [math]\displaystyle{ X_f \subseteq X }[/math] и [math]\displaystyle{ Y_f \subseteq Y }[/math] соответствующие множества свободных вершин.

Если одно из множеств [math]\displaystyle{ X_f }[/math] или [math]\displaystyle{ Y_f }[/math] пусто, то увеличивающих цепей не существует.
Ориентируем рёбра [math]\displaystyle{ G }[/math] следующим образом:
- рёбра из [math]\displaystyle{ M }[/math] идут из [math]\displaystyle{ X }[/math] в [math]\displaystyle{ Y }[/math];
- все остальные рёбра идут из [math]\displaystyle{ Y }[/math] в [math]\displaystyle{ X }[/math].
Выполним один поиск в ширину на полученном ориентированном графе, двигаясь от множества вершин [math]\displaystyle{ X_f }[/math] в обратном направлении.
- Поиск останавливается на том шаге, на котором будет посещена хотя бы одна из вершин в [math]\displaystyle{ Y_f }[/math].
- Если поиск будет завершён без посещения одной из вершин [math]\displaystyle{ Y_f }[/math], то увеличивающих цепей не существует.
- Пометим вершины и рёбра, посещённые в ходе поиска в ширину.
Для каждой из свободных вершин [math]\displaystyle{ y \in Y_f }[/math] выполним поиск в глубину в прямом направлении, двигаясь только по помеченным рёбрам и вершинам.
- Снимем пометку с посещённых рёбер и вершин.
- Если на очередном шаге посещена вершина [math]\displaystyle{ x \in X_f }[/math], то поиск останавливается, а текущее содержимое стека определяет кратчайшую увеличивающую цепь от [math]\displaystyle{ y }[/math] к [math]\displaystyle{ x }[/math].
- Если поиск в глубину завершается без посещения множества [math]\displaystyle{ X_f }[/math], то для данной вершины [math]\displaystyle{ y }[/math] увеличивающей цепи не существует, и необходимо перейти к следующей свободной вершине.

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

Алгоритм выполняет не более [math]\displaystyle{ O(\sqrt{n}) }[/math] шагов, на каждом из которых производятся поиск в ширину и поиск в глубину сложностью [math]\displaystyle{ O(m) }[/math]. Таким образом, общая сложность составляет [math]\displaystyle{ O(m \sqrt{n}) }[/math].

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

Описание ресурса параллелизма алгоритма

Описание входных и выходных данных

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

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

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

Описание локальности данных и вычислений

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

Масштабируемость алгоритма и его реализации

Динамические характеристики и эффективность реализации алгоритма

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

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

Java: JGraphT (класс HopcroftKarpBipartiteMatching).

Литература

↑ 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.

[1] 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.

[1]

@@ Строка 33: / Строка 33: @@
 === Описание схемы реализации последовательного алгоритма ===
+Опишем, каким образом ищется максимальное множество кратчайших увеличивающих цепей на втором шаге алгоритма.
+Пусть <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>.