Изменения

'''''Венгерский алгоритм ''''' (англ. ''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> ребер, то есть, новое ребро можно добавить в последнее найденное паросочетание, увеличив его размер на 1. Значитзначит, всего будет совершено не более <tex> O(n^2) </tex> итераций внешнего цикла. Поэтому, суммарная асимптотика верхняя оценка времени работы данного метода — <tex> O(n^5) </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^42) </tex>) , надо поддерживать вспомогательные минимумы по каждому из столбцов <tex> j </tex>. === Реализация === <tex> \mathtt{a[1 \dots n][1 \dots m]} </tex> {{---}} прямоугольная входная матрица, где <tex> \mathtt{n \leqslant m} </tex>. Матрица хранится в 1-индексации.

== Алгоритм за <tex>O(\mathtt{u[0 \dots n^3)], ~ 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> 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> i \mathtt{way[1 \dots m]} </tex>{{-ую строку--}} массив, а в первых <tex> i - 1 </tex> строках максимальное паросочетание уже найденосодержащий информацию о том, где эти минимумы достигаются, чтобы мы могли впоследствии восстановить [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|увеличивающую цепочку]].

Множество строк '''function''' hungarianAlgorithm(a): '''for''' i = 1 '''to''' n <texfont color=darkgreen> C // рассматриваем строки матрицы ''a'' </texfont>, из которых мы будем вычитать минимумы, вначале состоит только из строки p[0] = i <texfont color=darkgreen> i // для удобства реализации </texfont>, множество j0 = 0 <texfont color=darkgreen> R // свободный столбец </texfont> пусто. Применим к матрице операцию заполняем массивы ''minv'' {{---}} <tex> R\uparrow\downarrow C infty </tex>. Если новый нуль с координатами , ''used'' {{---}} ''false'' '''while''' ''true'' <texfont color=darkgreen> xy // ищем свободный столбец </texfont> появился в столбце, не занятом паросочетанием, то дополняющая цепь найдена used[j0] = ''true'', i0 = p[j0] <texfont color=darkgreen> xy // помечаем посещенными столбец ''j0'' и строку ''i0'' </texfont> — ее последнее ребро. Если нет пересчитываем массив ''minv'', то существует элемент находим в нем минимум ''<tex> x'y \delta </tex> из паросочетания. Тогда добавим строку '' (изначально ''<tex> x' \infty </tex> '') и столбец ''j1'', в котором он достигнут '''for''' j = 0 '''to''' m <texfont color=darkgreen> y // производим пересчет потенциала ''u'' и ''v'', соответствующее изменение ''minv'' </texfont> в множества '''if''' used[j] u[p[j]] += <tex> C \delta </tex> и v[j] -= <tex> R \delta </tex> соответственно, отметим '''else''' minv[j] -= <tex> xy \delta </tex> как замену для <tex> x если нашли свободный столбец {{---}} выходим из цикла ищем увеличивающуюся цепочку, пользуясь массивом предков ''way''y </tex> и повторим операцию.

После того, как === Время работы ===Оценим время работы алгоритма. Во внешнем цикле мы нашли дополняющую цепьдобавляем в рассмотрение строки матрицы одну за другой. Каждая строка обрабатывается за время <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> итераций, как мы удалим на каждой из паросочетания все ребра цепи, принадлежащие ему и добавим не принадлежащие, суммарный размер паросочетания увеличитсякоторых посещается новый столбец).

Краткий псевдокод данного алгоритма выглядит примерно так: '''HungarianAlgorithm'''Итоговая асимптотика составляет <tex> O(An^3) 1 '''for''' i = 0</tex>..height-1 2 '''do''' 3 создать в матрице A новый нулевой элемент 4 '''while''' новый элемент приводит к коллизии 5 изменить метки элементов вдоль найденной цепочки 6 '''return''' найденное паросочетание

При добавлении строки с номером <tex> i </tex> на поиск дополняющей цепи требуется <tex> O(i) </tex> итераций, если каждая итерация требует <tex> O(m) </tex> действий, то общее время работы алгоритма составляет <tex> O(mn^2) </tex>== См. При наивной реализации <tex> m также = O(n^2) </tex>. Но можно не пересчитывать каждый раз все измененные элементы матрицы. Вместо них будем хранить и обновлять =* [[Алгоритм Куна для каждой строки поиска максимального паросочетания]]* [[Связь максимального паросочетания и каждого столбца минимум по данной строке/столбцу. Текущее значение элемента минимального вершинного покрытия в каждый момент можно восстановить, используя эти вспомогательные массивы. При выполнении преобразования <tex> R\uparrow\downarrow C </tex> изменим соответствующие элементы массивов на <tex>d</tex>. Так можно выполнять все требуемые действия за <tex> O(n) </tex> операций, тогда на выполнение всего алгоритма потребуется <tex> O(n^3) </tex> действий.двудольных графах]]

== Ссылки Источники информации ==* Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — 2010, 368 стр.

 == Литература ==* Асанов М., Баранский В., Расин В. — Дискретная математика[http: Графы, матроиды, алгоритмы — 2010, 368 стр//e-maxx.ru/algo/assignment_hungary Венгерский алгоритм решения задачи о назначениях]