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

Венгерский алгоритм - классический способ за полиномиальное время решить задачу о назначениях: распределить $n$ работников по $n$ работам так, чтобы суммарная стоимость была минимальной. Идея опубликована Гарольдом Куном в 1955 году (он сослался на работы венгров Кёнига и Эгервари - отсюда название), а в 1957 году Манкр показал оценку $O(n^4)$, позже улучшенную до $O(n^3)$. В современной формулировке это эталонный пример ЛП-двойственности: алгоритм одновременно строит допустимое назначение и допустимые двойственные переменные, а сильный двойственный результат гарантирует оптимальность.

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

Дано $n$ работников, $n$ работ и матрица стоимостей $C = (c_{ij}) \in \mathbb{R}^{n \times n}$, где $c_{ij}$ - затраты, если работник $i$ выполнит работу $j$. Нужно выбрать перестановку $\pi : \{1,\dots,n\} \to \{1,\dots,n\}$, минимизирующую

$\sum_{i=1}^{n} c_{i,\pi(i)} \to \min.$

Если задача про максимум прибыли - переходим к минимуму через $c'_{ij} = M - c_{ij}$, где $M \ge \max c_{ij}$. Если работ больше, чем работников, или наоборот - добавляем фиктивные строки/столбцы с нулевой стоимостью.

Поставленная задача - частный случай минимального по весу совершенного паросочетания в полном двудольном графе $K_{n,n}$, где левые вершины - работники, правые - работы, а вес ребра $(i, j)$ равен $c_{ij}$. Полный перебор перестановок даёт $n!$ вариантов - для $n = 20$ это уже $\sim 2 \cdot 10^{18}$, неприемлемо. Венгерский алгоритм закрывает задачу за $O(n^3)$.

Идея ЛП-двойственности

Запишем задачу как линейное программирование с переменными $x_{ij} \in [0, 1]$:

$$\min \sum_{i,j} c_{ij} x_{ij}, \quad \sum_j x_{ij} = 1, \quad \sum_i x_{ij} = 1, \quad x_{ij} \ge 0.$$

Полиэдр такой задачи - это политоп Биркгофа (двунаправленно стохастические матрицы), и его вершины - именно перестановочные матрицы. Поэтому ЛП-релаксация даёт целочисленный оптимум: задача о назначениях точно решается симплекс-методом, но в нём $O(n^3)$ не гарантировано.

Двойственная задача: найти потенциалы $u_i, v_j$ такие, что

$u_i + v_j \le c_{ij} \quad \forall i, j, \qquad \max \sum_i u_i + \sum_j v_j.$

По теореме сильной двойственности оптимумы прямой и двойственной задач совпадают. Условие дополняющей нежёсткости: $x_{ij} > 0$ только если $u_i + v_j = c_{ij}$. Рёбра, на которых равенство достигнуто, называют жёсткими (tight); они образуют равенственный подграф $G_=$. Если в нём существует совершенное паросочетание - это и есть оптимальное назначение.

Венгерский алгоритм поддерживает допустимые $u, v$ и постепенно увеличивает паросочетание в $G_=$. Когда оно становится совершенным - оптимум найден.

Алгоритм по шагам

Классическая «школьная» формулировка работает прямо с матрицей $C$ и оперирует нулями: место $u_i + v_j = c_{ij}$ занимает $c_{ij} - u_i - v_j = 0$. Шаги:

1. Редукция строк. Из каждой строки вычесть её минимум. В каждой строке появляется хотя бы один ноль.
2. Редукция столбцов. Из каждого столбца вычесть его минимум. В каждом столбце появляется хотя бы один ноль.
3. Покрытие нулей. Найти минимальное число линий (горизонтальных и вертикальных), покрывающих все нули матрицы. Если линий ровно $n$ - назначение возможно: выбрать $n$ независимых нулей (по одному в каждой строке и каждом столбце) и выписать перестановку $\pi$.
4. Обновление. Если линий меньше $n$, пусть $\theta$ - минимум среди непокрытых элементов. Вычесть $\theta$ из всех непокрытых строк и прибавить $\theta$ к покрытым столбцам (или, эквивалентно: вычесть $\theta$ из непокрытых элементов, прибавить $\theta$ к дважды покрытым, не трогать однократно покрытые). Это сохраняет двойственную допустимость, создаёт новый ноль и не теряет старых. Вернуться к шагу 3.

Поиск минимального покрытия нулей сводится к теореме Кёнига: число линий в покрытии равно размеру максимального паросочетания на нулях. То есть алгоритм Куна для невзвешенного двудольного графа здесь - внутренняя процедура.

Сложность: от $O(n^4)$ к $O(n^3)$

Каждая итерация добавляет хотя бы одну новую жёсткую дугу или увеличивает паросочетание. Прямолинейная реализация Манкра 1957 года тратит $O(n^2)$ на поиск паросочетания и $O(n^2)$ на обновление, всего $O(n^4)$ - итераций тоже $O(n^2)$.

Оптимизация до $O(n^3)$ держит для каждого правого узла $j$ минимум $\min_i (c_{ij} - u_i - v_j)$ по уже обработанным левым узлам и пересчитывает его за $O(n)$ при добавлении нового левого узла. Тогда поиск увеличивающей цепи через жёсткий подграф вместе с обновлением потенциалов укладывается в $O(n^2)$ на итерацию, а итераций ровно $n$ - по одной на каждую вершину левой доли. Итого:

$T = O(n^3), \quad \text{память} = O(n^2).$

Это та самая «Jonker–Volgenant»-реализация (1987), которая используется в большинстве библиотек, включая SciPy linear_sum_assignment.

Корректность

Алгоритм одновременно поддерживает три инварианта:

1. Двойственная допустимость: после редукции и каждого обновления $u_i + v_j \le c_{ij}$ для всех $i, j$. На покрытых строках/столбцах знак сохраняется явно, на непокрытых - за счёт правильного знака $\theta$.
2. Жёсткое паросочетание: текущее $M$ состоит только из жёстких рёбер ($u_i + v_j = c_{ij}$).
3. Прогресс: за итерацию либо растёт $|M|$, либо появляется новое жёсткое ребро. Поэтому через $O(n^2)$ итераций (а в $O(n^3)$-варианте - через ровно $n$ внешних итераций) $|M| = n$.

Когда $|M| = n$, паросочетание совершенно, все его рёбра жёсткие, и

$\sum_i c_{i, \pi(i)} = \sum_i (u_i + v_{\pi(i)}) = \sum_i u_i + \sum_j v_j.$

Правая часть - значение двойственной задачи, и по сильной двойственности оно совпадает с оптимумом прямой. Значит, найденное назначение оптимально.

Типовая задача 4 на 4

Матрица стоимостей:

$$C = \begin{pmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 8 \\ 7 & 6 & 9 & 4 \end{pmatrix}.$$

Редукция строк (минимумы $2, 3, 1, 4$):

$$\begin{pmatrix} 7 & 0 & 5 & 6 \\ 3 & 1 & 0 & 4 \\ 4 & 7 & 0 & 7 \\ 3 & 2 & 5 & 0 \end{pmatrix}.$$

Редукция столбцов (минимумы $3, 0, 0, 0$):

$$\begin{pmatrix} 4 & 0 & 5 & 6 \\ 0 & 1 & 0 & 4 \\ 1 & 7 & 0 & 7 \\ 0 & 2 & 5 & 0 \end{pmatrix}.$$

Минимальное покрытие нулей - 4 линии (строки 2 и 4, столбцы 2 и 3). Назначение существует: например, $1 \to 2$, $2 \to 1$, $3 \to 3$, $4 \to 4$. Сумма $c_{1,2} + c_{2,1} + c_{3,3} + c_{4,4} = 2 + 6 + 1 + 4 = 13$. Это и есть оптимум.

Применения

• Распределение задач. Сотрудники на проекты, водители на маршруты, врачи на смены - везде, где у пары есть числовая «стоимость» и нужно покрыть все позиции.
• Шипп-планирование. Назначение судов на причалы, грузовиков на доки, контейнеров на платформы. Часто матрица не квадратная - её дополняют фиктивными столбцами.
• Computer vision matching. Сопоставление детекций между кадрами в трекинге (SORT, DeepSORT), ключевых точек, ассоциация лиц с треками. Стоимость - расстояние между признаками; алгоритм даёт глобальный оптимум.
• Экономика. Двусторонние рынки с трансфертами - модель Шепли-Шубика; венгерский алгоритм находит конкурентное равновесие.

Сравнение с потоковыми и аукционным алгоритмами

• Min-cost max-flow. Задача о назначениях - частный случай: исток → работники → работы → сток, пропускные способности 1, стоимости $c_{ij}$. SSP с потенциалами даёт $O(n^3 \log n)$. Гибче (другие ограничения, не-квадратные матрицы), но константа выше - базовый поток без стоимостей считается алгоритмом Эдмондса-Карпа.
• Аукционный алгоритм Бертсекаса (1979). Работники-«покупатели» итеративно повышают цены работ. $O(n^3)$ в худшем случае, хорошо параллелится. Применяется в радарном трекинге.
• Венгерский (Куна-Манкр) - классика, лучшая средняя константа на квадратной плотной матрице, $O(n^3)$ гарантированно.

Для $n$ до $\sim 10^3$ - почти всегда венгерский. Для $n \sim 10^4$ и разреженных матриц - потоковые или аукцион.

Частые ошибки

• Забывают про двойную редукцию. Только строки или только столбцы - не работает: должна быть и горизонтальная, и вертикальная.
• Неправильное обновление при недостающем покрытии. Нужно вычитать $\theta$ из непокрытых строк (или элементов) и прибавлять к покрытым столбцам - иначе нарушится двойственная допустимость и алгоритм зациклится.
• Применяют к не-квадратной матрице без дополнения. Если $m \ne n$, нужно дополнить фиктивными работниками/работами с нулевой (или $M$ для максимума) стоимостью. Иначе совершенного паросочетания не будет.
• Решают «максимум» как «минимум» без замены знака. Корректно: $c'_{ij} = M - c_{ij}$ с $M \ge \max c_{ij}$. Просто менять знак нельзя: появятся отрицательные значения и редукция выдаст ерунду.
• Считают, что любое покрытие минимально. Покрытие должно быть минимальным по числу линий (по теореме Кёнига = размеру максимального паросочетания на нулях). Если линий $n$, но они не минимальны, можно ошибочно решить, что назначение нашлось.

FAQ

Чем венгерский алгоритм отличается от алгоритма Куна? Алгоритм Куна решает невзвешенную задачу - найти максимальное паросочетание в двудольном графе, $O(VE)$. Венгерский алгоритм работает со взвешенной задачей и минимизирует сумму стоимостей при покрытии всех вершин, $O(n^3)$. Кун - внутренняя процедура венгерского алгоритма на шаге поиска покрытия нулей.

Почему сложность именно $O(n^3)$, а не быстрее? Внешний цикл - $n$ итераций (по числу левых вершин). На каждой итерации поиск увеличивающей цепи через жёсткий подграф плюс обновление потенциалов стоят $O(n^2)$. Существуют асимптотически более быстрые методы для специальных классов матриц (например, $O(n^{2.5})$ для двоичных), но в общем случае $O(n^3)$ - лучшая известная оценка для строго детерминированных алгоритмов.

Как обрабатывать прямоугольную матрицу $m \times n$? Дополнить меньшую сторону фиктивными вершинами с нулевой стоимостью до квадратной. После решения отбросить назначения на фиктивные элементы - они и так не несут затрат. Современные реализации (SciPy linear_sum_assignment) делают это автоматически.

Коротко

Венгерский алгоритм решает задачу о назначениях за $O(n^3)$: минимизирует сумму стоимостей при распределении $n$ работников по $n$ работам. Идея - ЛП-двойственность: алгоритм поддерживает допустимые двойственные переменные $u_i, v_j$ и постепенно увеличивает совершенное паросочетание в равенственном подграфе. Школьная формулировка с матрицей: вычитание минимумов из строк и столбцов, поиск минимального покрытия нулей линиями, обновление матрицы вычитанием минимума по непокрытым элементам. Корректность гарантируется сильной двойственностью ЛП. Применяется в логистике, computer vision, биоинформатике, экономике двусторонних рынков. На больших и разреженных задачах уступает потоковым и аукционным алгоритмам, но для плотных квадратных матриц до $n \sim 10^3$ - стандарт.