Изменения

'''''Венгерский алгоритм ''''' (англ. ''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 \uparrow\downarrow Y \setminus Y_c </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-3 4 в матрице весов появляется новый нуль. Этот нуль соответствует некоторому новому ребру между вершинами из множеств <tex> X \setminus X_c </tex> и <tex> Y \setminus Y_c </tex>. Всего в графе <tex> n^2 </tex> ребер, который увеличивает размер максимального паросочетания хотя бы на 1значит, поэтому всего будет совершено не более <tex> O(n^2) </tex> итераций внешнего цикла. Поэтому, суммарная асимптотика верхняя оценка времени работы алгоритма данного метода — <tex> O(n^45) </tex>. Более точная оценка довольно сложна и зависит от порядка чисел в матрице весов графа.

== Алгоритм за <tex> O(n^3) </tex> ==

Предложенный метод корректен=== Общая идея ===Будем добавлять в рассмотрение строки матрицы одну за одной, но а не является оптимальным по времени работы, оно может быть улучшено до <tex> O(n^3) </tex>рассматривать их все сразу.

Заметим=== Описание алгоритма ===* Начало* '''Шаг 0.''' Введем ''следующее понятие'':: Назовём потенциалом два произвольных массива чисел <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>* '''Шаг 2.''' Пока нет увеличивающей цепи, начинающейся в этой строке, пересчитываем потенциал.* '''Шаг 3.''' Как только появляется увеличивающая цепь, чередуем паросочетание вдоль неё (включая тем самым последнюю строку в [[Алгоритм_Куна_для_поиска_максимального_паросочетания|алгоритме Куна]]паросочетание), но здесь мы фактически строим целое дерево возможных дополняющих цепейи переходим к началу (к рассмотрению следующей строки).* Конец

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

Множество строк <tex> C </tex>, из которых мы будем вычитать минимумы, вначале состоит только из строки <tex> i \mathtt{a[1 \dots n][1 \dots m]} </tex>{{---}} прямоугольная входная матрица, множество где <tex> R </tex> пусто. Применим к матрице операцию <tex> C\uparrowmathtt{n \downarrow R </tex>. Если новый ноль с координатами <tex> xy </tex> появился в столбце, не занятом паросочетанием, то удлинняющая цепь найдена, <tex> xy </tex> — ее последнее ребро. Если нет, то существует элемент <tex> x'y leqslant m} </tex> из паросочетания. Тогда добавим строку <tex> x' </tex> и столбец <tex> y </tex> Матрица хранится в множества <tex> C </tex> и <tex> R </tex> соответственно и отметим <tex> xy </tex> как замену для <tex> x'y </tex>1-индексации.

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

При добавлении строки с номером <tex> i \mathtt{p[0 \dots m]} </tex> на поиск дополняющей цепи требуется {{---}} массив паросочетания. Для каждого стобца <tex> O(\mathtt{i) = 0 \dots m} </tex> итераций, если каждая итерация требует он хранит номер соответствующей выбранной строки <tex> O(m) \mathtt{p[i]} </tex> действий, то общее время работы алгоритма составляет <tex> O(mn^2) или </tex>. При наивной реализации <tex> m = O(n^2) \mathtt{0} </tex>. Но , если запоминать минимальные значения для каждой строки и столбца, а также обновлять их, ничего не пересчитывая элементы самой матрицы, то можно выполнять все требуемые действия за <tex> O(nвыбрано) </tex> операций. Полагаем, тогда на выполнение всего алгоритма потребуется что <tex> O(n^3) \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> minv </tex>; [[Алгоритм Куна для поиска максимального паросочетания|алгоритм Куна]] суммарно отработает за время <tex> O(n^2) </tex> (поскольку он представлен в форме <tex> O(n) </tex> итераций, на каждой из которых посещается новый столбец). Итоговая асимптотика составляет <tex> O(n^3) </tex>. == См. также ==* [[Алгоритм Куна для поиска максимального паросочетания]]* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] == Источники информации ==* Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — 2010, 368 стр.

== Литература ==* Асанов М., Баранский В., Расин В. — Дискретная математика[[Категория: Графы, матроиды, алгоритмы — 2010, 368 стр.Алгоритмы и структуры данных]]