Венгерский алгоритм решения задачи о назначениях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм за O(n^3))
м (rollbackEdits.php mass rollback)
 
(не показано 28 промежуточных версий 7 участников)
Строка 1: Строка 1:
Венгерский алгоритм — алгоритм, решающий задачу о назначениях за полиномиальное время. Оригинальная версия была придумана и разработана Х. Куном в 1955 году и имела асимптотику <tex> O(n^4) </tex>, но позже Эдмонс и Карп (а также, независимо от них, Томидзава) показали, что можно улучшить ее до <tex> O(n^3) </tex>.
+
'''''Венгерский алгоритм''''' (англ. ''Hungarian algorithm'') — алгоритм, решающий задачу о назначениях за полиномиальное время. Оригинальная версия была придумана и разработана Х. Куном в 1955 году и имела асимптотику <tex> O(n^4) </tex>, но позже Эдмонс и Карп (а также, независимо от них, Томидзава) показали, что можно улучшить ее до <tex> O(n^3) </tex>.
 
+
{{Задача
== Постановка задачи ==
+
|definition = Пусть дан [[Основные определения теории графов|взвешенный полный двудольный граф]] c целыми весами ребер <tex> K_{n, n} </tex>, нужно найти в нем [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|полное паросочетание минимального веса]]. Вес паросочетания определяется как сумма весов его ребер. Далее будем обозначать левую и правую доли графа за <tex> X </tex> и <tex> Y </tex> соответственно, вес ребра <tex> xy </tex> — как <tex> c(xy) </tex>.
 
+
}}
Пусть дан взвешенный полный двудольный граф <tex> K_{n, n} </tex>, нужно найти в нем полное паросочетание минимального веса. Вес паросочетания определяется как сумма весов его ребер. Далее будем обозначать левую и правую доли графа за <tex> X </tex> и <tex> Y </tex> соответственно, вес ребра <tex> xy </tex> — как <tex> c(xy) </tex>.
 
  
== Некоторые полезные утверждения ==
+
== Вспомогательные леммы ==
  
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Если веса всех ребер графа, инцидентных какой-либо вершине, изменить на одно и то же число, то в новом графе оптимальное паросочетание будет состоять из тех же ребер, что и в старом.
+
Если веса всех ребер графа, инцидентных какой-либо вершине, изменить (увеличить или уменьшить) на одно и то же число, то в новом графе оптимальное паросочетание будет состоять из тех же ребер, что и в старом.
 
|proof=
 
|proof=
 
Полное паросочетание для каждой вершины содержит ровно одно ребро, инцидентное этой вершине. Указанная операция изменит на одно и то же число вес любого паросочетания. Значит, ребро, которое принадлежало оптимальному паросочетанию в старом графе, в новом графе тоже будет ему принадлежать.
 
Полное паросочетание для каждой вершины содержит ровно одно ребро, инцидентное этой вершине. Указанная операция изменит на одно и то же число вес любого паросочетания. Значит, ребро, которое принадлежало оптимальному паросочетанию в старом графе, в новом графе тоже будет ему принадлежать.
Строка 18: Строка 17:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Выделим в множествах <tex>X</tex> и <tex>Y</tex> подмножества <tex>X', Y'</tex>. Пусть <tex>d = \min \{c(xy)|\ x \in X \setminus X', y \in Y'\}</tex>. Прибавим <tex> d </tex> ко всем весам ребер, инцидентных вершинам из <tex>X'</tex>. Затем отнимем <tex> d </tex> от всех весов ребер, инцидентных вершинам из <tex>Y'</tex> (далее для краткости эта операция обозначается как <tex> X' \uparrow\downarrow Y' </tex>). Тогда:
+
Выделим в множествах <tex>X</tex> и <tex>Y</tex> подмножества <tex>X', Y'</tex>. Пусть <tex>d = \min \{c(xy) \mid x \in X \setminus X', y \in Y'\}</tex>. Прибавим <tex> d </tex> ко всем весам ребер, инцидентных вершинам из <tex>X'</tex>. Затем отнимем <tex> d </tex> от всех весов ребер, инцидентных вершинам из <tex>Y'</tex> (далее для краткости эта операция обозначается как <tex> X' \uparrow\downarrow Y' </tex>). Тогда:
 
# Веса всех ребер графа останутся неотрицательными.
 
# Веса всех ребер графа останутся неотрицательными.
 
# Веса ребер вида <tex>xy</tex>, где <tex>x \in X', y \in Y'</tex> или <tex>x \in X \backslash X', y \in Y \backslash Y'</tex>, не изменятся.
 
# Веса ребер вида <tex>xy</tex>, где <tex>x \in X', y \in Y'</tex> или <tex>x \in X \backslash X', y \in Y \backslash Y'</tex>, не изменятся.
Строка 59: Строка 58:
 
Алгоритм, решающий задачу, работает с графом, как с матрицей весов.
 
Алгоритм, решающий задачу, работает с графом, как с матрицей весов.
  
# Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.
+
* Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.
# Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.
+
* Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.
# Ищем в текущем графе полное паросочетание из ребер нулевого веса:  
+
* Ищем в текущем графе полное паросочетание из ребер нулевого веса:  
#
+
** Если оно найдено, то желаемый результат достигнут, алгоритм закончен.
#* Если оно найдено, то желаемый результат достигнут, алгоритм закончен.
+
** В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|нахождение минимального вершинного покрытия в двудольном графе]]). Пусть <tex> X_c </tex> и <tex> Y_c </tex> — множества вершин минимального вершинного покрытия из левой и правой долей (то есть, строк и столбцов) соответственно, тогда применим преобразование <tex> X_c \uparrow\downarrow (Y \setminus Y_c) </tex>. Для этого преобразования <tex> d </tex> будет минимумом по всем ребрам между <tex> X \setminus X_c </tex> и <tex> Y \setminus Y_c </tex>, то есть, ребер нулевого веса здесь нет, поэтому, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.
#* В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|нахождение минимального вершинного покрытия в двудольном графе]]). Пусть <tex> X_c </tex> и <tex> Y_c </tex> — множества вершин минимального вершинного покрытия из левой и правой долей (то есть, строк и столбцов) соответственно, тогда применим преобразование <tex> X_c \uparrow\downarrow (Y \setminus Y_c) </tex>. Для этого преобразования <tex> d </tex> будет минимумом по всем ребрам между <tex> X \setminus X_c </tex> и <tex> Y \setminus Y_c </tex>, то есть, ребер нулевого веса здесь нет, поэтому, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.
 
  
 
== Анализ времени работы ==
 
== Анализ времени работы ==
  
Поиск максимального паросочетания или минимального вершинного покрытия в двудольном графе совершается за <tex> O(n^3) </tex> операций. При каждом повторении шагов 1-3 в матрице весов появляется новый нуль, который увеличивает размер максимального паросочетания хотя бы на 1, поэтому всего будет совершено <tex> O(n) </tex> итераций внешнего цикла. Поэтому, суммарная асимптотика работы алгоритма — <tex> O(n^4) </tex>.
+
[[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Поиск максимального паросочетания]] или [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|минимального вершинного покрытия]] в двудольном графе совершается за <tex> O(n^3) </tex> операций. При каждом повторении шагов 1-4 в матрице весов появляется новый нуль. Этот нуль соответствует некоторому новому ребру между вершинами из множеств <tex> X \setminus X_c </tex> и <tex> Y \setminus Y_c </tex>. Всего в графе <tex> n^2 </tex> ребер, значит, всего будет совершено не более <tex> O(n^2) </tex> итераций внешнего цикла. Поэтому, верхняя оценка времени работы данного метода — <tex> O(n^5) </tex>. Более точная оценка довольно сложна и зависит от порядка чисел в матрице весов графа.
  
== Алгоритм за <tex>O(n^3)</tex> ==
+
== Алгоритм за <tex> O(n^3) </tex> ==
  
Предложенный метод корректен, но не является оптимальным по времени работы, оно может быть улучшено до <tex> O(n^3) </tex>.
+
=== Общая идея ===
 +
Будем добавлять в рассмотрение строки матрицы одну за одной, а не рассматривать их все сразу.
  
Заметим, что искать максимальное паросочетание каждый раз заново необязательно, можно просто постепенно изменять его, получая новые нулевые ребра и строя [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|дополняющие цепи]] на них (примерно так же, как и в [[Алгоритм_Куна_для_поиска_максимального_паросочетания|алгоритме Куна]], но здесь мы фактически строим целое дерево возможных дополняющих цепей).
+
=== Описание алгоритма ===
 +
* Начало
 +
* '''Шаг 0.''' Введем ''следующее понятие'':
 +
: Назовём потенциалом два произвольных массива чисел <tex> u[1 \ldots n] </tex> и <tex> v[1 \ldots n] </tex> таких, что выполняется условие:
 +
<center> <tex> u[i] + v[j] \leqslant a[i][j] ~ (i = 1 \ldots n)</tex>, где <tex> a </tex> {{---}} заданная матрица. </center>
 +
* '''Шаг 1.''' Добавляем в рассмотрение очередную строку матрицы <tex> a. </tex>
 +
* '''Шаг 2.''' Пока нет увеличивающей цепи, начинающейся в этой строке, пересчитываем потенциал.
 +
* '''Шаг 3.''' Как только появляется увеличивающая цепь, чередуем паросочетание вдоль неё (включая тем самым последнюю строку в паросочетание), и переходим к началу (к рассмотрению следующей строки).
 +
* Конец
  
При их построении нам потребуется сохранять некоторую дополнительную информацию. Для каждого столбца, если в нем есть элемент из текущего паросочетания, будем хранить номер строки этого элемента. Также, при построении дополняющей цепи, будем для каждого элемента паросочетания хранить, на какой добавленный нуль из того же столбца его нужно заменить, если цепь будет проходить через него, а для каждого добавленного нуля {{---}} элемент из паросочетания, находящийся в той же строке (если он существует). Эти данные помогут нам восстановить дополняющую цепь.
+
=== Ключевые идеи ===
 +
* Для проверки наличия увеличивающей цепочки нет необходимости запускать обход Куна заново после каждого пересчёта потенциала. Вместо этого можно оформить [[Алгоритм Куна для поиска максимального паросочетания|обход Куна]] в итеративном виде: после каждого пересчёта потенциала мы просматриваем добавившиеся жёсткие рёбра и, если их левые концы были достижимыми, помечаем их правые концы также как достижимые и продолжаем обход из них.
 +
* Развивая эту идею дальше, можно прийти к такому представлению алгоритма: это цикл, на каждом шаге которого сначала пересчитывается потенциал, затем находится столбец, ставший достижимым (а таковой всегда найдётся, поскольку после пересчёта потенциала всегда появляются новые достижимые вершины), и если этот столбец был ненасыщен, то найдена увеличивающая цепь, а если столбец был насыщен — то соответствующая ему в паросочетании строка также становится достижимой.
 +
* Теперь алгоритм принимает вид: цикл добавления столбцов, на каждом из которых сначала пересчитывается потенциал, а затем какой-то новый столбец помечается как достижимый.
 +
* Чтобы быстро пересчитывать потенциал (быстрее, чем наивный вариант за <tex> O(n^2) </tex>), надо поддерживать вспомогательные минимумы по каждому из столбцов <tex> j </tex>.
  
Будем рассматривать строки матрицы последовательно. Пусть в данный момент мы рассматриваем <tex> i </tex>-ую строку, а в первых <tex> i - 1 </tex> строках максимальное паросочетание уже найдено.
+
=== Реализация ===
  
Множество строк <tex> C </tex>, из которых мы будем вычитать минимумы, вначале состоит только из строки <tex> i </tex>, множество <tex> R </tex> пусто. Применим к матрице операцию <tex> R\uparrow\downarrow C </tex>. Если новый нуль с координатами <tex> xy </tex> появился в столбце, не занятом паросочетанием, то дополняющая цепь найдена, <tex> xy </tex> — ее последнее ребро. Если нет, то существует элемент <tex> x'y </tex> из паросочетания. Тогда добавим строку <tex> x' </tex> и столбец <tex> y </tex> в множества <tex> C </tex> и <tex> R </tex> соответственно, отметим <tex> xy </tex> как замену для <tex> x'y </tex> и повторим операцию.
+
<tex> \mathtt{a[1 \dots n][1 \dots m]} </tex> {{---}} прямоугольная входная матрица, где <tex> \mathtt{n \leqslant m} </tex>. Матрица хранится в 1-индексации.
  
После того, как мы нашли дополняющую цепь, производим серию замен вдоль нее. Цепь состоит из элементов паросочетания и добавленных на текущей итерации нулей, причем для каждого элемента цепи (кроме, разумеется, последнего) известен следующий за ним. После того, как мы удалим из паросочетания все ребра цепи, принадлежащие ему и добавим не принадлежащие, суммарный размер паросочетания увеличится.
+
<tex> \mathtt{u[0 \dots n], ~ v[0 \dots n]} </tex> {{---}} потенциал.
  
При добавлении строки с номером <tex> i </tex> на поиск дополняющей цепи требуется <tex> O(i) </tex> итераций, если каждая итерация требует <tex> O(m) </tex> действий, то общее время работы алгоритма составляет <tex> O(mn^2) </tex>. При наивной реализации <tex> m = O(n^2) </tex>. Но если запоминать минимальные значения для каждой строки и столбца, а также обновлять их, не пересчитывая элементы самой матрицы, то можно выполнять все требуемые действия за <tex> O(n) </tex> операций, тогда на выполнение всего алгоритма потребуется <tex> O(n^3) </tex> действий.
+
<tex> \mathtt{p[0 \dots m]} </tex> {{---}} массив паросочетания. Для каждого стобца <tex> \mathtt{i = 0 \dots m} </tex> он хранит номер соответствующей выбранной строки <tex> \mathtt{p[i]} </tex> (или <tex> \mathtt{0} </tex>, если ничего не выбрано). Полагаем, что <tex> \mathtt{p[0]} </tex> равно номеру рассматриваемой строки.
  
== Ссылки ==
+
<tex> \mathtt{minv[1 \dots m]} </tex> {{---}} массив, хранящий для каждого столбца <tex> \mathtt{j} </tex> вспомогательные минимумы, необходимые для быстрого пересчета потенциала.
 +
 
 +
<tex> \mathtt{minv[j] = \min\limits_{i \in Z_1}(a[i][j] - u[i] - v[j])} </tex>, где <tex> \mathtt{Z_1} </tex> {{---}} множество вершин первой доли, которые были посещены обходом [[Алгоритм Куна для поиска максимального паросочетания|алгоритма Куна]] при попытке поиска увеличивающей цепи.
 +
 
 +
<tex> \mathtt{way[1 \dots m]} </tex> {{---}} массив, содержащий информацию о том, где эти минимумы достигаются, чтобы мы могли впоследствии восстановить [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|увеличивающую цепочку]].
 +
 
 +
'''function''' hungarianAlgorithm(a):
 +
  '''for''' i = 1 '''to''' n <font color=darkgreen>// рассматриваем строки матрицы ''a'' </font>
 +
    p[0] = i <font color=darkgreen>// для удобства реализации </font>
 +
    j0 = 0 <font color=darkgreen>// свободный столбец </font>
 +
    заполняем массивы ''minv'' {{---}} <tex> \infty </tex>, ''used'' {{---}} ''false''
 +
    '''while''' ''true'' <font color=darkgreen>// ищем свободный столбец </font>
 +
      used[j0] = ''true'', i0 = p[j0] <font color=darkgreen>// помечаем посещенными столбец ''j0'' и строку ''i0'' </font>
 +
      пересчитываем массив ''minv'', находим в нем минимум ''<tex> \delta </tex>'' (изначально ''<tex> \infty </tex>'') и столбец ''j1'', в котором он достигнут
 +
      '''for''' j = 0 '''to''' m <font color=darkgreen>// производим пересчет потенциала ''u'' и ''v'', соответствующее изменение ''minv'' </font>
 +
        '''if''' used[j]
 +
          u[p[j]] += <tex> \delta </tex>
 +
          v[j] -= <tex> \delta </tex>
 +
        '''else'''
 +
          minv[j] -= <tex> \delta </tex>
 +
      если нашли свободный столбец {{---}} выходим из цикла
 +
    ищем увеличивающуюся цепочку, пользуясь массивом предков ''way''
 +
 
 +
=== Время работы ===
 +
Оценим время работы алгоритма. Во внешнем цикле мы добавляем в рассмотрение строки матрицы одну за другой. Каждая строка обрабатывается за время <tex> O(n^2) </tex>, поскольку при этом могло происходить лишь <tex> O(n) </tex> пересчётов потенциала (каждый — за время <tex> O(n) </tex>), для чего за время <tex> O(n^2) </tex> поддерживается массив <tex> minv </tex>; [[Алгоритм Куна для поиска максимального паросочетания|алгоритм Куна]] суммарно отработает за время <tex> O(n^2) </tex> (поскольку он представлен в форме <tex> O(n) </tex> итераций, на каждой из которых посещается новый столбец).
 +
 
 +
Итоговая асимптотика составляет <tex> O(n^3) </tex>.
 +
 
 +
== См. также ==
 +
* [[Алгоритм Куна для поиска максимального паросочетания]]
 +
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 +
 
 +
== Источники информации ==
 +
* Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — 2010, 368 стр.
 
* [http://ru.wikipedia.org/wiki/Венгерский_алгоритм Венгерский алготитм в Википедии]
 
* [http://ru.wikipedia.org/wiki/Венгерский_алгоритм Венгерский алготитм в Википедии]
 
* [http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-2002 Визуализатор алгоритма]
 
* [http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-2002 Визуализатор алгоритма]
 
* [http://acm.mipt.ru/twiki/bin/view/Algorithms/HungarianAlgorithmCPP?sortcol=5&table=2&up=0 Реализация венгерского алгоритма на C++]
 
* [http://acm.mipt.ru/twiki/bin/view/Algorithms/HungarianAlgorithmCPP?sortcol=5&table=2&up=0 Реализация венгерского алгоритма на C++]
 
+
* [http://e-maxx.ru/algo/assignment_hungary Венгерский алгоритм решения задачи о назначениях]
== Литература ==
 
* Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — 2010, 368 стр.
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория: Задача о потоке минимальной стоимости]]
 
[[Категория: Задача о потоке минимальной стоимости]]

Текущая версия на 19:21, 4 сентября 2022

Венгерский алгоритм (англ. Hungarian algorithm) — алгоритм, решающий задачу о назначениях за полиномиальное время. Оригинальная версия была придумана и разработана Х. Куном в 1955 году и имела асимптотику [math] O(n^4) [/math], но позже Эдмонс и Карп (а также, независимо от них, Томидзава) показали, что можно улучшить ее до [math] O(n^3) [/math].

Задача:
Пусть дан взвешенный полный двудольный граф c целыми весами ребер [math] K_{n, n} [/math], нужно найти в нем полное паросочетание минимального веса. Вес паросочетания определяется как сумма весов его ребер. Далее будем обозначать левую и правую доли графа за [math] X [/math] и [math] Y [/math] соответственно, вес ребра [math] xy [/math] — как [math] c(xy) [/math].


Вспомогательные леммы

Лемма:
Если веса всех ребер графа, инцидентных какой-либо вершине, изменить (увеличить или уменьшить) на одно и то же число, то в новом графе оптимальное паросочетание будет состоять из тех же ребер, что и в старом.
Доказательство:
[math]\triangleright[/math]
Полное паросочетание для каждой вершины содержит ровно одно ребро, инцидентное этой вершине. Указанная операция изменит на одно и то же число вес любого паросочетания. Значит, ребро, которое принадлежало оптимальному паросочетанию в старом графе, в новом графе тоже будет ему принадлежать.
[math]\triangleleft[/math]

Далее будем рассматривать только графы с неотрицательной весовой функцией, так как, согласно этой лемме, задачу о назначениях на остальных графах можно свести к задаче о назначениях на них.

Лемма:
Выделим в множествах [math]X[/math] и [math]Y[/math] подмножества [math]X', Y'[/math]. Пусть [math]d = \min \{c(xy) \mid x \in X \setminus X', y \in Y'\}[/math]. Прибавим [math] d [/math] ко всем весам ребер, инцидентных вершинам из [math]X'[/math]. Затем отнимем [math] d [/math] от всех весов ребер, инцидентных вершинам из [math]Y'[/math] (далее для краткости эта операция обозначается как [math] X' \uparrow\downarrow Y' [/math]). Тогда:
  1. Веса всех ребер графа останутся неотрицательными.
  2. Веса ребер вида [math]xy[/math], где [math]x \in X', y \in Y'[/math] или [math]x \in X \backslash X', y \in Y \backslash Y'[/math], не изменятся.
Доказательство:
[math]\triangleright[/math]

Рассмотрим матрицу весов графа. Не умаляя общности, можно сказать, что множества [math] X' [/math] и [math] Y' [/math] состоят из первых элементов множеств [math] X [/math] и [math] Y [/math] соответственно (мы упорядочиваем множества по номерам вершин). Тогда вся матрица делится на 4 блока:

[math] Y' [/math] [math] Y \backslash Y' [/math]
[math] X' [/math] [math] A + d - d [/math] [math] C + d [/math]
[math] X \backslash X' [/math] [math] B - d [/math] [math] D [/math]
Веса группы [math] A [/math] будут сначала увеличены, а потом уменьшены на [math] d [/math], поэтому они не изменятся, веса группы [math] D [/math] вообще изменяться не будут. Все веса группы [math] B [/math] будут уменьшены на [math] d [/math], но [math] d [/math] — минимум среди этих весов, поэтому они останутся неотрицательными.
[math]\triangleleft[/math]
Лемма:
Если веса всех ребер графа неотрицательны и некоторое полное паросочетание состоит из ребер нулевого веса, то оно является оптимальным.
Доказательство:
[math]\triangleright[/math]
Действительно, паросочетание с какими-то другими весами ребер имеет больший вес и оптимальным не является.
[math]\triangleleft[/math]

Общий метод

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

Алгоритм, решающий задачу, работает с графом, как с матрицей весов.

  • Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.
  • Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.
  • Ищем в текущем графе полное паросочетание из ребер нулевого веса:
    • Если оно найдено, то желаемый результат достигнут, алгоритм закончен.
    • В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как нахождение минимального вершинного покрытия в двудольном графе). Пусть [math] X_c [/math] и [math] Y_c [/math] — множества вершин минимального вершинного покрытия из левой и правой долей (то есть, строк и столбцов) соответственно, тогда применим преобразование [math] X_c \uparrow\downarrow (Y \setminus Y_c) [/math]. Для этого преобразования [math] d [/math] будет минимумом по всем ребрам между [math] X \setminus X_c [/math] и [math] Y \setminus Y_c [/math], то есть, ребер нулевого веса здесь нет, поэтому, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.

Анализ времени работы

Поиск максимального паросочетания или минимального вершинного покрытия в двудольном графе совершается за [math] O(n^3) [/math] операций. При каждом повторении шагов 1-4 в матрице весов появляется новый нуль. Этот нуль соответствует некоторому новому ребру между вершинами из множеств [math] X \setminus X_c [/math] и [math] Y \setminus Y_c [/math]. Всего в графе [math] n^2 [/math] ребер, значит, всего будет совершено не более [math] O(n^2) [/math] итераций внешнего цикла. Поэтому, верхняя оценка времени работы данного метода — [math] O(n^5) [/math]. Более точная оценка довольно сложна и зависит от порядка чисел в матрице весов графа.

Алгоритм за [math] O(n^3) [/math]

Общая идея

Будем добавлять в рассмотрение строки матрицы одну за одной, а не рассматривать их все сразу.

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

  • Начало
  • Шаг 0. Введем следующее понятие:
Назовём потенциалом два произвольных массива чисел [math] u[1 \ldots n] [/math] и [math] v[1 \ldots n] [/math] таких, что выполняется условие:
[math] u[i] + v[j] \leqslant a[i][j] ~ (i = 1 \ldots n)[/math], где [math] a [/math] — заданная матрица.
  • Шаг 1. Добавляем в рассмотрение очередную строку матрицы [math] a. [/math]
  • Шаг 2. Пока нет увеличивающей цепи, начинающейся в этой строке, пересчитываем потенциал.
  • Шаг 3. Как только появляется увеличивающая цепь, чередуем паросочетание вдоль неё (включая тем самым последнюю строку в паросочетание), и переходим к началу (к рассмотрению следующей строки).
  • Конец

Ключевые идеи

  • Для проверки наличия увеличивающей цепочки нет необходимости запускать обход Куна заново после каждого пересчёта потенциала. Вместо этого можно оформить обход Куна в итеративном виде: после каждого пересчёта потенциала мы просматриваем добавившиеся жёсткие рёбра и, если их левые концы были достижимыми, помечаем их правые концы также как достижимые и продолжаем обход из них.
  • Развивая эту идею дальше, можно прийти к такому представлению алгоритма: это цикл, на каждом шаге которого сначала пересчитывается потенциал, затем находится столбец, ставший достижимым (а таковой всегда найдётся, поскольку после пересчёта потенциала всегда появляются новые достижимые вершины), и если этот столбец был ненасыщен, то найдена увеличивающая цепь, а если столбец был насыщен — то соответствующая ему в паросочетании строка также становится достижимой.
  • Теперь алгоритм принимает вид: цикл добавления столбцов, на каждом из которых сначала пересчитывается потенциал, а затем какой-то новый столбец помечается как достижимый.
  • Чтобы быстро пересчитывать потенциал (быстрее, чем наивный вариант за [math] O(n^2) [/math]), надо поддерживать вспомогательные минимумы по каждому из столбцов [math] j [/math].

Реализация

[math] \mathtt{a[1 \dots n][1 \dots m]} [/math] — прямоугольная входная матрица, где [math] \mathtt{n \leqslant m} [/math]. Матрица хранится в 1-индексации.

[math] \mathtt{u[0 \dots n], ~ v[0 \dots n]} [/math] — потенциал.

[math] \mathtt{p[0 \dots m]} [/math] — массив паросочетания. Для каждого стобца [math] \mathtt{i = 0 \dots m} [/math] он хранит номер соответствующей выбранной строки [math] \mathtt{p[i]} [/math] (или [math] \mathtt{0} [/math], если ничего не выбрано). Полагаем, что [math] \mathtt{p[0]} [/math] равно номеру рассматриваемой строки.

[math] \mathtt{minv[1 \dots m]} [/math] — массив, хранящий для каждого столбца [math] \mathtt{j} [/math] вспомогательные минимумы, необходимые для быстрого пересчета потенциала.

[math] \mathtt{minv[j] = \min\limits_{i \in Z_1}(a[i][j] - u[i] - v[j])} [/math], где [math] \mathtt{Z_1} [/math] — множество вершин первой доли, которые были посещены обходом алгоритма Куна при попытке поиска увеличивающей цепи.

[math] \mathtt{way[1 \dots m]} [/math] — массив, содержащий информацию о том, где эти минимумы достигаются, чтобы мы могли впоследствии восстановить увеличивающую цепочку.

function hungarianAlgorithm(a):
  for i = 1 to n // рассматриваем строки матрицы a 
    p[0] = i // для удобства реализации 
    j0 = 0 // свободный столбец 
    заполняем массивы minv[math] \infty [/math], usedfalse
    while true // ищем свободный столбец 
      used[j0] = true, i0 = p[j0] // помечаем посещенными столбец j0 и строку i0 
      пересчитываем массив minv, находим в нем минимум [math] \delta [/math] (изначально [math] \infty [/math]) и столбец j1, в котором он достигнут
      for j = 0 to m // производим пересчет потенциала u и v, соответствующее изменение minv 
        if used[j]
          u[p[j]] += [math] \delta [/math]
          v[j] -= [math] \delta [/math]
        else
          minv[j] -= [math] \delta [/math]
      если нашли свободный столбец — выходим из цикла
    ищем увеличивающуюся цепочку, пользуясь массивом предков way

Время работы

Оценим время работы алгоритма. Во внешнем цикле мы добавляем в рассмотрение строки матрицы одну за другой. Каждая строка обрабатывается за время [math] O(n^2) [/math], поскольку при этом могло происходить лишь [math] O(n) [/math] пересчётов потенциала (каждый — за время [math] O(n) [/math]), для чего за время [math] O(n^2) [/math] поддерживается массив [math] minv [/math]; алгоритм Куна суммарно отработает за время [math] O(n^2) [/math] (поскольку он представлен в форме [math] O(n) [/math] итераций, на каждой из которых посещается новый столбец).

Итоговая асимптотика составляет [math] O(n^3) [/math].

См. также

Источники информации