1632
правки
Изменения
м
# * Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.# * Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.# * Ищем в текущем графе полное паросочетание из ребер нулевого веса: ##** Если оно найдено, то желаемый результат достигнут, алгоритм закончен.#** В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|нахождение минимального вершинного покрытия в двудольном графе]]). Пусть <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> 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>
rollbackEdits.php mass rollback
Алгоритм, решающий задачу, работает с графом, как с матрицей весов.
== Анализ времени работы ==
* Начало
* '''Шаг 0.''' Введем ''следующее понятие'':
* '''Шаг 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> \mathtt{minv} </tex>; [[Алгоритм Куна для поиска максимального паросочетания|алгоритм Куна]] суммарно отработает за время <tex> O(n^2) </tex> (поскольку он представлен в форме <tex> O(n) </tex> итераций, на каждой из которых посещается новый столбец).
Итоговая асимптотика составляет <tex> O(n^3) </tex>.
