Венгерский алгоритм решения задачи о назначениях

Венгерский алгоритм — алгоритм, решающий задачу о назначениях за полиномиальное время. Оригинальная версия была придумана и разработана Х. Куном в 1955 году и имела асимптотику [math] O(n^4) [/math], но позже Эдмонс и Карп (а также, независимо от них, Томидзава) показали, что можно улучшить ее до [math] O(n^3) [/math].

Постановка задачи

Пусть дан взвешенный полный двудольный граф [math] K_{n, n} [/math], нужно найти в нем полное паросочетание минимального веса. Вес паросочетания определяется как сумма весов его ребер. Далее будем обозначать левую и правую доли графа за [math] X [/math] и [math] Y [/math] соответственно, вес ребра [math] xy [/math] — как [math] c(xy) [/math].

Некоторые полезные утверждения

Лемма:

Если веса всех ребер графа, инцидентных какой-либо вершине, изменить на одно и то же число, то в новом графе оптимальное паросочетание будет состоять из тех же ребер, что и в старом.

Доказательство:

[math]\triangleright[/math]

Полное паросочетание для каждой вершины содержит ровно одно ребро, инцидентное этой вершине. Указанная операция изменит на одно и то же число вес любого паросочетания. При изменении весов всех ребер, инцидентных данной вершине, на одно и то же число, выбранное ребро останется оптимальным.

[math]\triangleleft[/math]

Далее будем рассматривать только графы с неотрицательной весовой функцией, так как, согласно этой лемме, задачу о назначениях на остальных графах можно свести к задаче о назначениях на них.

Лемма:

Выделим в множествах [math]X[/math] и [math]Y[/math] подмножества [math]X', Y'[/math]. Пусть [math]d = \min \{c(xy)|\ x \in X \setminus X', y \in Y'\}[/math]. Прибавим [math] d [/math] ко всем весам ребер, инцидентных вершинам из [math]X'[/math]. Затем отнимем [math] d [/math] от всех весов ребер, инцидентных вершинам из [math]Y'[/math]. Тогда: Веса всех ребер графа останутся неотрицательными. Веса ребер вида [math]xy[/math], где [math]x \in X', y \in Y'[/math] или [math]x \in X \backslash X', y \in Y \backslash Y'[/math], не изменятся.

Доказательство:

[math]\triangleright[/math]

Рассмотрим матрицу весов графа. Не умаляя общности, можно сказать, что множества [math] X' [/math] и [math] Y' [/math] состоят из первых элементов множеств [math] X [/math] и [math] Y [/math] соответственно (мы упорядочиваем множества по номерам вершин). Тогда вся матрица делится на 4 блока: [math] X' [/math] [math] X \backslash X' [/math] [math] Y' [/math] [math] A + d - d [/math] [math] B - d [/math] [math] Y \backslash Y' [/math] [math] C + d [/math] [math] D [/math] Веса группы [math] A [/math] будут сначала увеличены, а потом уменьшены на [math] d [/math], поэтому они не изменятся, веса группы [math] D [/math] вообще изменяться не будут. Все веса группы [math] B [/math] будут уменьшены на [math] d [/math], но [math] d [/math] — минимум среди этих весов, поэтому они останутся неотрицательными.

[math]\triangleleft[/math]

Лемма:

Если веса всех ребер графа неотрицательны и некоторое полное паросочетание состоит из ребер нулевого веса, то оно является оптимальным.

Доказательство:

[math]\triangleright[/math]

Действительно, паросочетание с какими-то другими весами ребер имеет больший вес и оптимальным не является.

[math]\triangleleft[/math]

Алгоритм

Доказанные ранее утверждения позволяют придумать схему алгоритма, решающего задачу о назначениях: нужно найти полное паросочетание из ребер нулевого веса в графе, полученном из исходного преобразованиями, описанными в первых двух леммах.

Алгоритм, решающий задачу, работает с графом, как с матрицей весов.

1. Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.
2. Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.
3. Ищем в текущем графе полное паросочетание из ребер нулевого веса:
4. • Если оно найдено, то желаемый результат достигнут, алгоритм закончен.
   • В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как нахождение минимального вершинного покрытия в двудольном графе). Теперь применим преобразование из леммы 2. Пусть множества вершин минимального вершинного покрытия из левой и правой долей — [math] X_c [/math] и [math] Y_c [/math] соответственно, тогда берем [math] X' = X_c, Y' = Y \setminus Y_c [/math]. Для этого преобразования [math] d [/math] будет минимумом по всем ребрам между [math] X \setminus X_c [/math] и [math] Y \setminus Y_c [/math], то есть, ребер нулевого веса здесь нет, поэтому, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.

Анализ времени работы

Поиск максимального паросочетания или минимального контролирующего множества в двудольном графе совершается за [math] O(n^3) [/math] операций. При каждом повторении шагов 1-3 в матрице весов появляется новый нуль, который увеличивает размер максимального паросочетания хотя бы на 1, поэтому всего будет совершено [math] O(n) [/math] итераций внешнего цикла. Поэтому, суммарная асимптотика работы данной версии венгерского алгоритма — [math] O(n^4) [/math]. В книге Асанова, а также в реализации на C++ по ссылке ниже предложена оптимизация, которая позволяет улучшить время работы до [math] O(n^3) [/math].

Ссылки

• Венгерский алготитм в Википедии
• Визуализатор алгоритма
• Реализация венгерского алгоритма на C++

Литература

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