39
правок
Изменения
м
→Алгоритм за O(n^3)
== Алгоритм за <tex>O(n^3)</tex> ==
<tex>a[1 \dots n][1 \dots m]</tex> {{---}} прямоугольная входная матрица, где <tex>n \leq m</tex>. Матрица хранится в 1-индексации.
<tex>u[0 \dots n], v[0 \dots n]</tex> {{---}} массивы потенциалов. Изначально нулевые, что верно для матрицы, состоящей из 0 строк.
<tex>p[0 \dots m]</tex> {{---}} массив паросочетания. Для каждого стобца <tex>i = 0 \dots m</tex> он хранит номер соответствующей выбранной строки <tex>p[i]</tex> (или 0, если ничего не выбрано). Полагаем, что <tex>p[0]</tex> равно номеру рассматриваемой строки.
<tex>minv[1 \dots m]</tex> {{---}} массив, хранящий для каждого столбца j вспомогательные минимумы, необходимые для быстрого пересчета потенциала.
<tex>minv[j] = \min_{i \in Z_1}\{a[i][j] - u[i] - v[j]\}</tex>
<tex>way[1 \dots m]</tex> {{---}} массив, содержащий информацию о том, где эти минимумы достигаются, чтобы мы могли впоследствии восстановить [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|увеличивающую цепочку]].
'''hungarianAlgorithmfunction'''hungarianAlgorithm(a): <font color=darkgreen>// добавляем в рассмотрение <tex> i </tex>-ую строку матрицы </font> '''for''' i = 1 '''to''' n:
p[0] = i
j0 = 0
'''for''' i = 0 '''to''' m + 1: minv[i] = <tex>\infty</tex>
used[i] = 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:
cur = a[i0][j] - u[i0] - v[j]
'''if''' cur < minv[j]:
minv[j] = cur
way[j] = j0
'''if''' minv[j] < <tex>\delta</tex>: <tex>\delta</tex> = minv[j]
j1 = j
<font color=darkgreen>// производим пересчет потенциалов u и v, соответствующее изменение массива minv</font> '''for''' j = 0 '''to''' m: '''if''' used[j]: u[p[j]] += <tex>\delta</tex> v[j] -= <tex>\delta</tex>; '''else''': minv[j] -= <tex>\delta</tex> j0 = j1; '''if''' p[j0] != 0:
'''break'''
<font color=darkgreen>// ищем увеличивающую цепочку, оканчивающуюся в столбце j0, "раскрутить" которую можно, пользуясь массивом предков way</font> '''while''' true:
j1 = way[j0]
p[j0] = p[j1]
j0 = j1
'''if''' j0 <tex>\neq</tex> 0:
'''break'''
