Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показаны 3 промежуточные версии этого же участника)
Строка 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>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: Строка 34:
 
# Составить новое паросочетание <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: Строка 57:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма===
+
=== Свойства алгоритма ===
== Программная реализация алгоритмов ==
+
 
 +
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Результаты прогонов ===
=== Масштабируемость алгоритма и его реализации ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
 
 
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/HopcroftKarpBipartiteMatching.html HopcroftKarpBipartiteMatching]</code>).
 
  
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />
 +
 +
[[Категория:Начатые статьи]]
 +
 +
[[en:Hopcroft–Karp algorithm]]

Текущая версия на 09:56, 7 июля 2022


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 Макроструктура алгоритма

  1. Выбрать начальное паросочетание [math]M_0[/math] (например, [math]M_0 = \emptyset[/math] или паросочетание, полученное жадным алгоритмом).
  2. Вычислить максимальное по включение множество кратчайших увеличивающих цепей [math]\{ P_1, \ldots, P_q \}[/math], не пересекающихся по вершинам. Если улучшающих цепей не существует, остановиться: текущее паросочетание [math]M_i[/math] является максимальным.
  3. Составить новое паросочетание [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] соответствующие множества свободных вершин.

  1. Если одно из множеств [math]X_f[/math] или [math]Y_f[/math] пусто, то увеличивающих цепей не существует.
  2. Ориентируем рёбра [math]G[/math] следующим образом:
    • рёбра из [math]M[/math] идут из [math]X[/math] в [math]Y[/math];
    • все остальные рёбра идут из [math]Y[/math] в [math]X[/math].
  3. Выполним один поиск в ширину на полученном ориентированном графе, двигаясь от множества вершин [math]X_f[/math] в обратном направлении.
    • Поиск останавливается на том шаге, на котором будет посещена хотя бы одна из вершин в [math]Y_f[/math].
    • Если поиск будет завершён без посещения одной из вершин [math]Y_f[/math], то увеличивающих цепей не существует.
    • Пометим вершины и рёбра, посещённые в ходе поиска в ширину.
  4. Для каждой из свободных вершин [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 Литература

  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.