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

Венгерский алгоритм простыми словами: задача о назначениях, потенциалы и двойственность, реализация за O(n³) на Python, сравнение с алгоритмом Куна и потоком минимальной стоимости.

14 мин чтенияалгоритмы · графы · python

Коротко

ПараметрЗначение
Задачаназначить n работников на n работ с минимальной суммарной стоимостью
СложностьO(n³) (вариант с потенциалами), память O(n²) под матрицу
Главная идеяпотенциалы строк и столбцов + поиск увеличивающих цепей по «нулевым» рёбрам
Родственникиалгоритм Куна (без весов), поток минимальной стоимости (общий случай)
В Pythonscipy.optimize.linear_sum_assignment
  • Перебор — O(n!)O(n!), динамика по подмножествам — O(2n⋅n)O(2^n \cdot n), венгерский алгоритм — O(n3)O(n^3).
  • Жадность не работает: самая дешёвая пара может испортить всё остальное.
  • Венгерский алгоритм — это алгоритм Куна, который ищет паросочетание только по «выгодным» рёбрам и умеет аккуратно расширять набор таких рёбер.

Задача о назначениях

Есть n курьеров и n заказов. Матрица cost[i][j] — сколько минут курьеру i ехать до заказа j. Каждый курьер берёт ровно один заказ, каждый заказ достаётся ровно одному курьеру. Нужно минимизировать суммарное время.

Формально — найти перестановку σ\sigma, на которой достигается

min⁡σ∑i=1ncost[i][σ(i)]\min_{\sigma} \sum_{i=1}^{n} cost[i][\sigma(i)]

На языке графов это совершенное паросочетание минимального веса в полном двудольном графе: слева строки, справа столбцы, вес ребра (i, j) — cost[i][j].

Пример, с которым будем работать дальше:

            заказ 0  заказ 1  заказ 2  заказ 3
курьер 0       9        2        7        8
курьер 1       6        4        3        7
курьер 2       5        8        1        8
курьер 3       7        6        9        4

Оптимум — 13: курьер 0 → заказ 1 (2), курьер 1 → заказ 0 (6), курьер 2 → заказ 2 (1), курьер 3 → заказ 3 (4).

Та же задача встречается под разными именами: распределение машин по заявкам, сопоставление объектов между кадрами видео при трекинге, назначение преподавателей на курсы, сопоставление предсказаний с разметкой (так устроен матчинг в детекторе DETR).

Наивные подходы

Перебор

from itertools import permutations def brute_force(cost): n = len(cost) return min( sum(cost[i][perm[i]] for i in range(n)) for perm in permutations(range(n)) )

n!n! перестановок: при n = 10 это 3,6 млн, при n = 15 — больше триллиона. Годится только как эталон для тестов.

Жадность

«Берём самую дешёвую клетку, вычёркиваем строку и столбец, повторяем». Контрпример из двух строк:

1    2
2  100

Жадный алгоритм возьмёт 1, после чего останется только 100 — итого 101. Оптимум — 2 + 2 = 4. Дешёвое назначение сейчас может заблокировать единственный разумный вариант для другой строки.

Динамика по подмножествам

Назначаем строки по порядку, в маске храним занятые столбцы: O(2n⋅n)O(2^n \cdot n). Это стандартное решение на собеседовании при n ≤ 15–20, подробно — в статье про битмаски в ДП. Дальше n = 20–25 не уедет.

Венгерский алгоритм решает задачу за полином и спокойно работает с матрицами в тысячи строк.

Откуда название и при чём тут Кун

Алгоритм опубликовал Гарольд Кун в 1955 году и назвал его венгерским в честь работ Дёнеша Кёнига и Енё Эгервари. Позже Джеймс Манкрес показал, что он полиномиален, поэтому в англоязычной литературе часто пишут Kuhn–Munkres. Версию за O(n3)O(n^3) получили в начале 1970-х (Эдмондс и Карп, Томидзава). А в 2006 году выяснилось, что по сути тот же метод описал Карл Якоби ещё в XIX веке — его работа вышла посмертно.

Тот самый Кун — автор алгоритма Куна для максимального паросочетания. Это не совпадение: венгерский алгоритм внутри и есть поиск увеличивающих цепей, только по специально отобранным рёбрам.

Интуиция: вычитаем из строк и столбцов

Главное наблюдение: если из всей строки вычесть одно и то же число, оптимальное назначение не изменится. В любом назначении из этой строки берётся ровно одна клетка, поэтому стоимость каждого варианта уменьшится на одну и ту же величину. Со столбцами то же самое.

Значит, матрицу можно «прижимать» к нулю, не меняя ответа. Если после этого найдётся назначение, целиком состоящее из нулей, а все числа неотрицательны, — оно оптимально: дешевле нуля не бывает.

Разберём на матрице 3×3:

4  1  3
2  0  5
3  2  2

Шаг 1. Вычитаем минимум каждой строки (1, 0, 2):

3  0  2
2  0  5
1  0  0

Шаг 2. Вычитаем минимум каждого столбца (1, 0, 0):

2  0  2
1  0  5
0  0  0

Шаг 3. Ищем паросочетание по нулям. Это ровно алгоритм Куна на двудольном графе, где ребро (i, j) есть, если в клетке ноль. Строки 0 и 1 обе могут взять только столбец 1, поэтому совершенного паросочетания нет — максимум два.

Шаг 4. Создаём новые нули. Все нули покрываются двумя линиями: столбцом 1 и строкой 2. Минимум среди непокрытых клеток — 1. Вычитаем его из непокрытых строк (0 и 1) и прибавляем к покрытому столбцу 1 — так нули в нём сохраняются, а в непокрытой части появляется новый:

1  0  1
0  0  4
0  1  0

Теперь есть нулевое назначение: (0,1), (1,0), (2,2). В исходной матрице это 1 + 2 + 2 = 5 — оптимум.

Так выглядит классический «ручной» венгерский метод из учебников по исследованию операций. Для программы он неудобен: минимальное покрытие линиями нужно искать отдельно, а наивная реализация работает за O(n4)O(n^4). Поэтому в коде используют эквивалентную формулировку через потенциалы.

Потенциалы и двойственная задача

Вместо того чтобы переписывать матрицу, будем хранить, сколько уже вычли из каждой строки и каждого столбца:

  • u[i] — потенциал строки i;
  • v[j] — потенциал столбца j;
  • приведённая стоимость клетки — cij′=cij−ui−vjc'_{ij} = c_{ij} - u_i - v_j.

Потенциалы называются допустимыми, если все приведённые стоимости неотрицательны:

ui+vj≤cijдля всех i,ju_i + v_j \le c_{ij} \quad \text{для всех } i, j

Сложим это неравенство по клеткам любого назначения σ\sigma. Каждая строка и каждый столбец войдут ровно по одному разу:

∑iui+∑jvj≤∑iciσ(i)\sum_i u_i + \sum_j v_j \le \sum_i c_{i\sigma(i)}

То есть сумма потенциалов — нижняя оценка стоимости любого назначения. Если нашлось назначение, у которого все клетки «жёсткие» (ui+vj=ciju_i + v_j = c_{ij}, то есть приведённая стоимость ноль), то оценка достигнута и назначение оптимально.

В примере выше итоговые потенциалы: u = [2, 1, 2], v = [1, -1, 0]. Их сумма — 5, ровно стоимость найденного назначения. Это и есть сертификат оптимальности.

Математически это двойственность линейного программирования: исходная задача — минимизировать стоимость назначения, двойственная — максимизировать ∑ui+∑vj\sum u_i + \sum v_j при ограничениях ui+vj≤ciju_i + v_j \le c_{ij}. Венгерский алгоритм одновременно строит решения обеих и останавливается, когда они сходятся.

Весь алгоритм держится на двух инвариантах:

  1. потенциалы всегда допустимы (cij′≥0c'_{ij} \ge 0);
  2. все рёбра текущего паросочетания жёсткие (cij′=0c'_{ij} = 0).

Алгоритм за O(n³)

Строки добавляются в паросочетание по одной. Для очередной строки i ищем увеличивающую цепь до свободного столбца по жёстким рёбрам — как в алгоритме Куна. Если цепь не находится, меняем потенциалы так, чтобы появилось новое жёсткое ребро, и продолжаем поиск с того места, где остановились.

Как менять потенциалы. Пусть уже посещены строки Z1Z_1 и столбцы Z2Z_2 (это вершины, достижимые из i по чередующимся жёстким путям). Возьмём

Δ=min⁡i∈Z1, j∉Z2cij′\Delta = \min_{i \in Z_1,\ j \notin Z_2} c'_{ij}

и сделаем u[i] += Δ для строк из Z1Z_1 и v[j] -= Δ для столбцов из Z2Z_2. Что произойдёт:

  • для рёбер внутри посещённой части (строка из Z1Z_1, столбец из Z2Z_2) c′c' не меняется — паросочетание и найденные жёсткие пути сохраняются;
  • для рёбер «строка из Z1Z_1 → непосещённый столбец» c′c' уменьшается на Δ\Delta и остаётся неотрицательным по выбору Δ\Delta, а хотя бы одно ребро становится жёстким;
  • рёбра из непосещённых строк в посещённые столбцы только дорожают.

Новое жёсткое ребро ведёт в новый столбец. Если он свободен — цепь найдена. Если занят — переходим в его строку и повторяем.

Чтобы не пересчитывать Δ\Delta каждый раз с нуля за O(n2)O(n^2), для каждого непосещённого столбца храним minv[j] — минимальную приведённую стоимость ребра в него из посещённых строк. Тогда один шаг стоит O(n)O(n).

Реализация

def hungarian(cost): """cost: матрица n x m, n <= m. Возвращает (минимальная стоимость, assignment), где assignment[i] — столбец, назначенный строке i.""" n, m = len(cost), len(cost[0]) INF = float('inf') u = [0] * (n + 1) # потенциалы строк v = [0] * (m + 1) # потенциалы столбцов p = [0] * (m + 1) # p[j] — строка, занявшая столбец j (0 — свободен) way = [0] * (m + 1) # way[j] — предыдущий столбец на пути к j for i in range(1, n + 1): p[0] = i # фиктивный столбец 0 «держит» новую строку j0 = 0 minv = [INF] * (m + 1) used = [False] * (m + 1) while True: used[j0] = True i0, delta, j1 = p[j0], INF, 0 for j in range(1, m + 1): if not used[j]: cur = cost[i0 - 1][j - 1] - u[i0] - v[j] if cur < minv[j]: minv[j], way[j] = cur, j0 if minv[j] < delta: delta, j1 = minv[j], j for j in range(m + 1): if used[j]: u[p[j]] += delta v[j] -= delta else: minv[j] -= delta j0 = j1 if p[j0] == 0: # дошли до свободного столбца break while j0: # разворачиваем увеличивающую цепь j1 = way[j0] p[j0] = p[j1] j0 = j1 assignment = [0] * n for j in range(1, m + 1): if p[j]: assignment[p[j] - 1] = j - 1 total = sum(cost[i][assignment[i]] for i in range(n)) return total, assignment cost = [ [9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4], ] print(hungarian(cost)) # (13, [1, 0, 2, 3])

Это классическая компактная реализация, широко известная в русскоязычном олимпиадном сообществе. Разберём, что в ней происходит.

Индексация с единицы. Строки и столбцы нумеруются с 1, а столбец 0 — фиктивный. Перед добавлением строки i пишем p[0] = i: как будто строка уже «сидит» в столбце 0. Тогда поиск цепи начинается единообразно — из занятого столбца j0 = 0 переходим в его строку.

Внутренний цикл — это Дейкстра. used — посещённые столбцы, minv[j] — текущее «расстояние» до столбца j в приведённых стоимостях, delta — минимальное среди непосещённых. Каждая итерация берёт ближайший столбец j1 и помечает его посещённым. Ничего не напоминает? Это алгоритм Дейкстры на плотном графе за O(n2)O(n^2) — без кучи, простым проходом по массиву.

Пересчёт потенциалов. Строки посещённых столбцов (u[p[j]]) получают +delta, сами посещённые столбцы — -delta, а minv непосещённых уменьшается на delta, потому что все они измеряются относительно изменившихся u. Строка p[0] = i тоже попадает под used[0], так что новая строка обновляется вместе с остальными.

way — дерево путей. way[j] запоминает, из какого столбца мы пришли в j. Когда добрались до свободного столбца, идём назад по way и сдвигаем строки: каждый столбец на пути забирает строку предыдущего. Это то же инвертирование увеличивающей цепи, что и у Куна, только записанное через столбцы.

Ответ. Можно не пересчитывать сумму в конце: после работы алгоритма -v[0] равно минимальной стоимости. Но явная сумма по assignment нагляднее и не ломается, если вы поменяете обработку потенциалов.

Почему O(n³)

  • Внешний цикл — n фаз, по одной на строку.
  • В каждой фазе хотя бы один новый столбец помечается посещённым, поэтому внутренний while делает не больше m + 1 итераций.
  • Каждая итерация — два прохода по столбцам, O(m)O(m).

Итого O(n⋅m2)O(n \cdot m^2), для квадратной матрицы — O(n3)O(n^3). Память — O(n+m)O(n + m) сверх самой матрицы.

Проверка на случайных тестах

Венгерский алгоритм легко сломать опечаткой в индексах, а на маленьком примере ошибка может не проявиться. Сверяйтесь с перебором:

import random random.seed(1) for _ in range(2000): n = random.randint(1, 6) c = [[random.randint(-20, 50) for _ in range(n)] for _ in range(n)] assert hungarian(c)[0] == brute_force(c), c print('ok')

Отрицательные стоимости алгоритму не мешают: потенциалы стартуют с нуля, а первый же шаг сдвигает их под минимум строки.

Практические варианты задачи

Максимизация

Если в матрице прибыль и её нужно максимизировать, умножьте всё на −1 (или вычтите каждый элемент из максимума) и решайте задачу на минимум:

profit = [[7, 5, 9], [8, 3, 6], [4, 9, 2]] total, a = hungarian([[-x for x in row] for row in profit]) print(-total, a) # 26 [2, 0, 1]

Прямоугольная матрица

Реализация выше уже поддерживает n ≤ m: работников меньше, чем заказов, часть столбцов останется свободной. Если строк больше, транспонируйте матрицу. Другой вариант — дополнить её до квадратной фиктивными строками или столбцами из нулей.

Запрещённые пары

Поставьте в клетку большое число BIG, заметно больше любой реальной суммы. Если ответ получился ≥ BIG, допустимого назначения нет. Не используйте здесь float('inf'): разность inf - inf даёт nan, и алгоритм тихо сломается.

Готовая библиотека

В реальном проекте на Python берите scipy.optimize.linear_sum_assignment. Она реализована на C, поддерживает прямоугольные матрицы и флаг maximize=True:

import numpy as np from scipy.optimize import linear_sum_assignment cost = np.array([[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]]) rows, cols = linear_sum_assignment(cost) print(cols, cost[rows, cols].sum()) # [1 0 2 3] 13

На случайной матрице 400×400 у меня она отработала примерно в 40 раз быстрее чистого Python из этой статьи (около 0,01 с против 0,5 с).

Сравнение: Кун, венгерский алгоритм и min-cost flow

Все три — родственники. Каждый ищет увеличивающие цепи в двудольном графе, разница в том, что они оптимизируют.

КунВенгерскийMin-cost flow
Что ищетмаксимальное паросочетаниесовершенное паросочетание минимального весапоток заданной величины минимальной стоимости
Весанетдада
СложностьO(V⋅E)O(V \cdot E)O(n3)O(n^3)O(F⋅Elog⁡V)O(F \cdot E \log V) с Дейкстрой и потенциалами
Графлюбой двудольный, обычно разреженныйполная матрица n × mпроизвольная сеть
Пропускные способности11любые
Код~15 строк~40 строк~60 строк

Венгерский против Куна

Кун отвечает на вопрос «сколько пар можно составить», веса для него не существуют. Венгерский алгоритм решает взвешенную задачу, а Кун у него внутри: поиск цепи по жёстким рёбрам — это try_kuhn, только с умной добавкой новых рёбер через потенциалы.

Если веса одинаковые или их нет — берите Куна. Если матрица 0/1 и нужно максимальное паросочетание, венгерский тоже справится (поставьте 0 на допустимые пары и 1 на остальные), но это стрельба из пушки по воробьям.

Венгерский против потока минимальной стоимости

Задача о назначениях естественно сводится к потоку минимальной стоимости: исток → строки (пропускная способность 1, стоимость 0), строка i → столбец j (1, cost[i][j]), столбцы → сток (1, 0). Пропускаем n единиц потока, каждый раз по кратчайшему пути в остаточной сети:

from collections import deque def assignment_mcmf(cost): """Задача о назначениях через поток минимальной стоимости (SPFA).""" n = len(cost) s, t, N = 2 * n, 2 * n + 1, 2 * n + 2 graph = [[] for _ in range(N)] # ребро: [куда, пропускная, стоимость, индекс обратного] def add_edge(a, b, cap, w): graph[a].append([b, cap, w, len(graph[b])]) graph[b].append([a, 0, -w, len(graph[a]) - 1]) for i in range(n): add_edge(s, i, 1, 0) add_edge(n + i, t, 1, 0) for j in range(n): add_edge(i, n + j, 1, cost[i][j]) total = 0 for _ in range(n): # n раз ищем кратчайший путь s -> t dist = [float('inf')] * N prev = [None] * N # (вершина, номер ребра) in_queue = [False] * N dist[s] = 0 queue = deque([s]) while queue: a = queue.popleft() in_queue[a] = False for k, (b, cap, w, _) in enumerate(graph[a]): if cap and dist[a] + w < dist[b]: dist[b] = dist[a] + w prev[b] = (a, k) if not in_queue[b]: in_queue[b] = True queue.append(b) total += dist[t] b = t while b != s: # проталкиваем единицу потока a, k = prev[b] edge = graph[a][k] edge[1] -= 1 graph[b][edge[3]][1] += 1 b = a return total print(assignment_mcmf(cost)) # 13

Обратные рёбра имеют отрицательную стоимость, поэтому здесь нужен Беллман-Форд или его очередная версия SPFA. Стандартное ускорение — потенциалы Джонсона: после каждой итерации прибавить к потенциалу вершины найденное расстояние. Тогда все приведённые стоимости неотрицательны и можно запускать Дейкстру (тот же трюк, что в алгоритме Джонсона).

И вот главный вывод: венгерский алгоритм — это и есть min-cost flow с потенциалами Джонсона, заточенный под полный двудольный граф. u и v — потенциалы, внутренний цикл — Дейкстра за O(n2)O(n^2) на плотном графе, каждая фаза — один кратчайший путь из истока в сток. Специализация убирает всё лишнее: нет явных рёбер, нет кучи, нет обратных рёбер в памяти.

На практике это заметно. На случайных матрицах в моих замерах версия с SPFA выше обрабатывала 200×200 около 2 секунд, а венгерский алгоритм — меньше десятой доли секунды.

Когда всё-таки нужен поток:

  • у работника может быть несколько заказов, у заказа — несколько исполнителей (пропускные способности больше 1);
  • граф не полный и сильно разреженный, а вершин десятки тысяч;
  • задача — часть большей сети: есть промежуточные узлы, ограничения на маршруты, обязательный объём.

Если же у вас квадратная или прямоугольная матрица стоимостей и каждый элемент берётся максимум один раз — венгерский алгоритм проще и быстрее.

На собеседовании

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

  • LeetCode 1879 «Minimum XOR Sum of Two Arrays» — n ≤ 14;
  • LeetCode 1947 «Maximum Compatibility Score Sum» — n ≤ 8;
  • LeetCode 1066 «Campus Bikes II» — до 10 работников;
  • LeetCode 2172 «Maximum AND Sum of Array»;
  • LeetCode 2850 «Minimum Moves to Spread Stones Over Grid».

Ожидаемое решение — динамика по маскам. Но если вы распознали задачу о назначениях и сказали это вслух, интервьюер почти наверняка спросит: «А если n = 1000?» Правильный ответ — венгерский алгоритм за O(n3)O(n^3) или linear_sum_assignment.

Для примера, 1879 обоими способами:

from functools import lru_cache def minimum_xor_sum(nums1, nums2): cost = [[a ^ b for b in nums2] for a in nums1] return hungarian(cost)[0] def minimum_xor_sum_dp(nums1, nums2): n = len(nums1) @lru_cache(maxsize=None) def dp(mask): i = bin(mask).count('1') # сколько элементов nums1 уже назначено if i == n: return 0 return min( (nums1[i] ^ nums2[j]) + dp(mask | 1 << j) for j in range(n) if not mask >> j & 1 ) return dp(0) print(minimum_xor_sum([1, 0, 3], [5, 3, 4])) # 8 print(minimum_xor_sum_dp([1, 0, 3], [5, 3, 4])) # 8

Признаки задачи о назначениях в условии:

  • два набора объектов, между которыми нужна биекция (или инъекция из меньшего в больший);
  • у каждой пары своя стоимость, и стоимости не зависят друг от друга;
  • минимизируется или максимизируется сумма.

Если оптимизируется не сумма, а максимум (минимизировать самую долгую поездку), — это другая задача: бинарный поиск по ответу плюс проверка паросочетанием Куна. Подробнее о приёме — в статье про бинарный поиск по ответу.

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

Жадный выбор вместо алгоритма. Самая частая ошибка на интервью: «берём минимальную пару и повторяем». Контрпример из двух строк выше.

float('inf') для запрещённых пар. inf - inf = nan, сравнения с nan всегда ложны, и алгоритм выдаёт мусор без ошибки. Используйте большое конечное число.

Строк больше, чем столбцов. Реализация требует n ≤ m. При n > m для лишней строки свободного столбца нет: delta остаётся бесконечным, j1 — нулём, и внутренний цикл зависает навсегда. Транспонируйте матрицу.

Путаница индексов. Внутри всё с единицы, снаружи — с нуля. Ошибка на единицу в cost[i0 - 1][j - 1] проходит на симметричных примерах. Тестируйте против перебора на случайных матрицах.

Забыли, что ищется совершенное паросочетание. Венгерский алгоритм всегда назначает все строки. Если допустимо оставить работника без заказа, добавьте фиктивные столбцы со стоимостью «простоя».

Минимум вместо суммы. Минимизировать максимальную стоимость в назначении — другая задача, венгерский алгоритм её не решает.

Что запомнить

  • Задача о назначениях — совершенное паросочетание минимального веса в полном двудольном графе.
  • Вычитание константы из строки или столбца не меняет оптимального назначения — на этом построен весь метод.
  • Потенциалы u, v дают нижнюю оценку ∑u+∑v\sum u + \sum v; назначение по жёстким рёбрам её достигает и потому оптимально.
  • Реализация за O(n3)O(n^3) — это алгоритм Куна по жёстким рёбрам плюс Дейкстра на плотном графе для пересчёта потенциалов.
  • По сути это min-cost flow с потенциалами Джонсона, специализированный под матрицу. Поток нужен, когда пропускные способности больше единицы или граф разреженный и огромный.
  • На собеседовании при n ≤ 15–20 пишите динамику по маскам, а венгерский алгоритм называйте как масштабируемое решение.

Потренироваться в спокойной обстановке

Все задачи