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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показана 41 промежуточная версия 10 участников)
Строка 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</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>, не изменятся.
Строка 27: Строка 26:
 
   <tr>
 
   <tr>
 
     <td>  </td>
 
     <td>  </td>
     <td> <tex> X' </tex> </td>
+
     <td> <tex> Y' </tex> </td>
     <td> <tex> X \backslash X' </tex> </td>
+
     <td> <tex> Y \backslash Y' </tex> </td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
     <td> <tex> Y' </tex> </td>
+
     <td> <tex> X' </tex> </td>
 
     <td> <tex> A + d - d </tex> </td>
 
     <td> <tex> A + d - d </tex> </td>
     <td> <tex> B - d </tex> </td>
+
     <td> <tex> C + d </tex> </td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
     <td> <tex> Y \backslash Y' </tex> </td>
+
     <td> <tex> X \backslash X' </tex> </td>
     <td> <tex> C + d </tex> </td>
+
     <td> <tex> B - d </tex> </td>
 
     <td> <tex> D </tex> </td>
 
     <td> <tex> D </tex> </td>
 
   </tr>
 
   </tr>
Строка 53: Строка 52:
 
}}
 
}}
  
== Алгоритм ==
+
== Общий метод ==
  
 
Доказанные ранее утверждения позволяют придумать схему алгоритма, решающего задачу о назначениях: нужно найти полное паросочетание из ребер нулевого веса в графе, полученном из исходного преобразованиями, описанными в первых двух леммах.  
 
Доказанные ранее утверждения позволяют придумать схему алгоритма, решающего задачу о назначениях: нужно найти полное паросочетание из ребер нулевого веса в графе, полученном из исходного преобразованиями, описанными в первых двух леммах.  
Строка 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.
#* В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|нахождение минимального вершинного покрытия в двудольном графе]]). Теперь применим преобразование из леммы 2. Пусть множества вершин минимального вершинного покрытия из левой и правой долей — <tex> X_c </tex> и <tex> Y_c </tex> соответственно, тогда берем <tex> X' = X_c, Y' = 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>. В книге Асанова, а также в реализации на C++ по ссылке ниже предложена оптимизация, которая позволяет улучшить время работы до <tex> O(n^3) </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> ==
  
== Ссылки ==
+
=== Общая идея ===
 +
Будем добавлять в рассмотрение строки матрицы одну за одной, а не рассматривать их все сразу.
 +
 
 +
=== Описание алгоритма ===
 +
* Начало
 +
* '''Шаг 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> \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> \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].

См. также

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