39
правок
Изменения
м
<font color=darkgreen>// добавляем в рассмотрение <tex> i </tex>-ую строку матрицы </font>
<font color=darkgreen>// производим пересчет потенциалов u и v, соответствующее изменение массива minv</font>
<font color=darkgreen>// ищем увеличивающую цепочку, оканчивающуюся в столбце j0, "раскрутить" которую можно, пользуясь массивом предков way</font>
→Алгоритм за O(n^3)
[[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Поиск максимального паросочетания]] или [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|минимального вершинного покрытия]] в двудольном графе совершается за <tex> O(n^3) </tex> операций. При каждом повторении шагов 1-4 в матрице весов появляется новый нуль. Этот нуль соответствует некоторому новому ребру между вершинами из множеств <tex> X \setminus X_c </tex> и <tex> Y \setminus Y_c </tex>. Всего в графе n^2 ребер, значит, всего будет совершено не более <tex> O(n^2) </tex> итераций внешнего цикла. Поэтому, верхняя оценка времени работы данного метода — <tex> O(n^5) </tex>. Более точная оценка довольно сложна и зависит от порядка чисел в матрице весов графа.
== Алгоритм за <tex>O(n^3)</tex> == === Общая идея ===Будем добавлять в рассмотрение строки матрицы одну за одной, а не рассматривать их все сразу. === Описание алгоритма ===* Добавляем в рассмотрение очередную строку матрицы <tex> \mathtt{a} </tex>.* Пока нет увеличивающей цепи, начинающейся в этой строке, пересчитываем потенциал.* Как только появляется увеличивающая цепь, чередуем паросочетание вдоль неё (включая тем самым последнюю строку в паросочетание), и переходим к началу (к рассмотрению следующей строки). === Реализация ===
<tex> \mathtt{a[1 \dots n][1 \dots m]} </tex> {{---}} прямоугольная входная матрица, где <tex> \mathtt{n \leqslant m} </tex>. Матрица хранится в 1-индексации.
'''function''' hungarianAlgorithm(a):
'''for''' i = 1 '''to''' n
p[0] = i
j0 = 0
заполняем массивы '''minv ''' {{---}} <tex> \infty </tex>, '''used ''' {{---}} false <font color=darkgreen>// ищем свободный столбец j0 </font>
'''while''' true
used[j0] = true
i0 = p[j0]
<tex> \delta </tex> = <tex> \infty </tex> <font color=darkgreen> // минимум в массиве minv </font> <font color=darkgreen>// пересчитываем массив minv </font>
'''for''' j = 1 '''to''' m
'''if''' used[j] == 0
<tex> \delta </tex> = minv[j]
j1 = j
'''for''' j = 0 '''to''' m
'''if''' used[j]
'''if''' p[j0] != 0
'''break'''
'''while''' true
j1 = way[j0]
'''if''' j0 <tex> \neq </tex> 0
'''break'''
=== Время работы ===
Оценим время работы алгоритма. Во внешнем цикле мы добавляем в рассмотрение строки матрицы одну за другой. Каждая строка обрабатывается за время <tex> O(n^2) </tex>, поскольку при этом могло происходить лишь <tex> O(n) </tex> пересчётов потенциала (каждый — за время <tex> O(n) </tex>), для чего за время <tex> O(n^2) </tex> поддерживается массив <tex> \mathtt{minv[]} </tex>; алгоритм Куна суммарно отработает за время <tex> O(n^2) </tex> (поскольку он представлен в форме <tex> O(n) </tex> итераций, на каждой из которых посещается новый столбец).
Итоговая асимптотика составляет <tex> O(n^3) </tex>.
== См. также ==
