39
правок
Изменения
м
→Реализация
<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''
