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

Математическая модель задачи о назначениях строится в виде квадратной матрицы стоимостей размером N на N. Строки матрицы соответствуют исполнителям (агентам), а столбцы — работам (задачам). На пересечении строки и столбца указывается числовая стоимость выполнения конкретной работы конкретным агентом. Целевая функция заключается в строгой минимизации суммарной стоимости назначений. Жесткие ограничения требуют, чтобы каждый исполнитель получил ровно одну уникальную работу, и каждая работа была закреплена ровно за одним уникальным исполнителем. Геометрически это означает поиск идеального паросочетания минимального веса в полном двудольном взвешенном графе.

Создатель Венгерского алгоритма, Гарольд Кун, опирался на фундаментальные теоремы двух выдающихся венгерских математиков начала XX века — Денеша Кенига и Ене Эгервари. Центральной теоремой алгоритма является теорема Кенига-Эгервари: в любом двудольном графе размер максимального паросочетания в точности равен минимальному числу вершин, необходимых для покрытия всех ребер графа. Алгоритм начинается с операции редукции матрицы стоимостей. Математика задачи позволяет безболезненно вычесть минимальный элемент из каждой строки, а затем минимальный элемент из каждого столбца. Эта линейная трансформация не меняет оптимального решения, но создает в матрице множество нулевых элементов, которые и становятся главными кандидатами на идеальное назначение (ведь назначение по нулевой стоимости является наилучшим из возможных).

После проведения редукции алгоритм пытается найти независимый набор из N нулей (так, чтобы в каждой строке и столбце было выбрано не более одного нуля). Если такой набор найден — задача решена, это и есть идеальное оптимальное распределение. Однако часто нули группируются неудачно. На этом этапе включается второй, гениальный шаг алгоритма: необходимо провести минимальное количество горизонтальных и вертикальных линий через матрицу так, чтобы вычеркнуть абсолютно все нулевые элементы. Если минимальное число таких покрывающих линий строго меньше N, значит, идеальное паросочетание построить пока невозможно, и матрица нуждается в дальнейшей корректировке.

Алгоритм находит самый минимальный элемент матрицы, который оказался не зачеркнутым ни одной линией. Это значение вычитается из всех незачеркнутых элементов матрицы и прибавляется ко всем элементам, находящимся на пересечениях двух вычеркивающих линий (элементы, покрытые одной линией, остаются без изменений). Эта виртуозная алгебраическая манипуляция генерирует новые нули в матрице, одновременно разрушая старые тупиковые конфигурации. Процесс проведения линий и корректировки матрицы итеративно повторяется до тех пор, пока минимальное число покрывающих линий не станет равно N. Вычислительная сложность Венгерского алгоритма составляет O(N^3), что делает его невероятно быстрым и строго полиномиальным методом. Сегодня эта математика лежит в основе систем распределения заказов агрегаторов такси и алгоритмов трекинга (Object Tracking) в системах компьютерного зрения, где алгоритм ежесекундно связывает пиксели объектов из предыдущего кадра с пикселями на новом кадре.