Изменения

'''''Венгерский алгоритм ''''' (англ. ''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>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> 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> 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> ==

<tex>a[1 \dots n][1 \dots m]</tex> {{---}} прямоугольная входная матрица=== Общая идея ===Будем добавлять в рассмотрение строки матрицы одну за одной, где <tex>n \leq m</tex>. Матрица хранится в 1-индексацииа не рассматривать их все сразу.

=== Описание алгоритма ===* Начало* '''Шаг 0.''' Введем ''следующее понятие'':: Назовём потенциалом два произвольных массива чисел <tex>u[0 1 \ldots n] </tex> и <tex> v[1 \dots ldots n]</tex> таких, что выполняется условие:<center> <tex> u[i] + v[0 j] \leqslant a[i][j] ~ (i = 1 \dots ldots n])</tex>, где <tex> a </tex> {{---}} массивы потенциаловзаданная матрица. </center>* '''Шаг 1.''' Добавляем в рассмотрение очередную строку матрицы <tex> a. </tex>* '''Шаг 2.''' Пока нет увеличивающей цепи, начинающейся в этой строке, пересчитываем потенциал.* '''Шаг 3. Изначально нулевые''' Как только появляется увеличивающая цепь, что верно для матрицычередуем паросочетание вдоль неё (включая тем самым последнюю строку в паросочетание), состоящей из 0 строки переходим к началу (к рассмотрению следующей строки).* Конец

<tex>p=== Ключевые идеи ===* Для проверки наличия увеличивающей цепочки нет необходимости запускать обход Куна заново после каждого пересчёта потенциала. Вместо этого можно оформить [[0 \dots mАлгоритм Куна для поиска максимального паросочетания|обход Куна]]</tex> {{--в итеративном виде: после каждого пересчёта потенциала мы просматриваем добавившиеся жёсткие рёбра и, если их левые концы были достижимыми, помечаем их правые концы также как достижимые и продолжаем обход из них.* Развивая эту идею дальше, можно прийти к такому представлению алгоритма: это цикл, на каждом шаге которого сначала пересчитывается потенциал, затем находится столбец, ставший достижимым (а таковой всегда найдётся, поскольку после пересчёта потенциала всегда появляются новые достижимые вершины), и если этот столбец был ненасыщен, то найдена увеличивающая цепь, а если столбец был насыщен — то соответствующая ему в паросочетании строка также становится достижимой.* Теперь алгоритм принимает вид: цикл добавления столбцов, на каждом из которых сначала пересчитывается потенциал, а затем какой-}} массив паросочетаниято новый столбец помечается как достижимый. Для каждого стобца * Чтобы быстро пересчитывать потенциал (быстрее, чем наивный вариант за <tex>i = 0 \dots m</tex> он хранит номер соответствующей выбранной строки <tex>p[i]O(n^2) </tex> (или 0, если ничего не выбрано). Полагаем, что надо поддерживать вспомогательные минимумы по каждому из столбцов <tex>p[0]j </tex> равно номеру рассматриваемой строки.

<tex>minv[j] = \min_{i \in Z_1}\mathtt{a[i1 \dots n][j1 \dots m] } </tex> {{-- u[i] - v[j]}} прямоугольная входная матрица, где <tex> \mathtt{n \leqslant m}</tex>. Матрица хранится в 1-индексации.

<tex>way\mathtt{u[1 0 \dots mn], ~ v[0 \dots n]} </tex> {{---}} массив, содержащий информацию о том, где эти минимумы достигаются, чтобы мы могли впоследствии восстановить увеличивающую цепочкупотенциал.

'''hungarianAlgorithm'''(a): '''for''' i = 1 '''to''' n: p[0] = i j0 = 0 '''for''' i = 0 '''to''' m + 1: minv[i] = <tex>\infty</tex> used[i] = false '''while''' true: used[j0] = true i0 = mathtt{p[j00 \dots m] <tex>\delta} </tex> = {{---}} массив паросочетания. Для каждого стобца <tex>\infty</tex> '''for''' j = 1 '''to''' m: '''if''' used[j] =mathtt{i = 0: cur = a[i0][j] - u[i0] - v[j] '''if''' cur < minv[j]: minv[j] = cur way[j] = j0 '''if''' minv[j] < <tex>\deltadots m} </tex>: он хранит номер соответствующей выбранной строки <tex>\delta</tex> = minv[j] j1 = j '''for''' j = 0 '''to''' m: '''if''' used[j]: u[mathtt{p[j]i] += <tex>\delta} </tex> v[j] -= (или <tex>\deltamathtt{0} </tex>; '''else''': minv[j] -= , если ничего не выбрано). Полагаем, что <tex>\delta</tex> j0 = j1; '''if''' mathtt{p[j0] != 0: '''break''' '''while''' true: j1 = way[j0] p[j0] = p[j1] j0 = j1 '''if''' j0 <tex>\neq} </tex> 0: '''break'''равно номеру рассматриваемой строки.

<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 стр.