Венгерский метод

Венгерский метод — это комбинаторный алгоритм оптимизации, предназначенный для решения задачи о назначениях, также известной как задача выбора. Он находит оптимальное (минимальное или максимальное по стоимости) назначение \( n \) работников на \( n \) работ при условии, что каждый работник выполняет ровно одну работу, а каждая работа выполняется ровно одним работником. Алгоритм является полиномиальным, его вычислительная сложность составляет \( O(n^3) \). Метод был разработан американским математиком венгерского происхождения Гарольдом Куном в 1955 году и получил своё название в честь венгерских математиков Денеша Кёнига и Эджера Эрдеша, чьи теоремы легли в основу доказательства корректности алгоритма.

История

Задача о назначениях является частным случаем транспортной задачи и общей задачи линейного программирования. В начале XX века венгерские математики Денеш Кёниг и Эджер Эрдеш разработали теоремы о паросочетаниях в двудольных графах. В 1931 году Кёниг доказал теорему, устанавливающую связь между максимальным паросочетанием и минимальным вершинным покрытием в двудольном графе. Эта теорема, известная как теорема Кёнига, стала ключевым элементом для построения эффективного алгоритма.

В 1955 году американский математик Гарольд Кун, работая в Принстонском университете, опубликовал статью «The Hungarian method for the assignment problem». Он адаптировал идеи Кёнига и Эрдеша для решения задачи о назначениях, предложив алгоритм, который гарантированно находит оптимальное решение за полиномиальное время. В 1957 году Джеймс Манкрес (James Munkres) усовершенствовал алгоритм, показав, что его можно реализовать за время \( O(n^3) \). Эта версия часто называется алгоритмом Куна-Манкреса или просто венгерским алгоритмом.

Математическая постановка задачи

Пусть задана квадратная матрица \( C \) размера \( n \times n \), где элемент \( c_{ij} \) представляет собой стоимость (или выигрыш) назначения \( i \)-го работника на \( j \)-ю работу. Требуется найти такое взаимно однозначное соответствие между работниками и работами (перестановку \( \pi \)), чтобы суммарная стоимость была минимальной (или максимальной):

\[ \min_{\pi} \sum_{i=1}^{n} c_{i,\pi(i)} \]

где \( \pi \) — перестановка чисел от 1 до \( n \).

Основные теоремы

В основе венгерского метода лежат две теоремы теории графов:

Теорема Кёнига

В двудольном графе размер максимального паросочетания равен размеру минимального вершинного покрытия. Эта теорема позволяет сводить задачу поиска паросочетания к задаче о покрытии.

Лемма о потенциалах

Для задачи о назначениях вводится понятие потенциала. Потенциалы \( u_i \) и \( v_j \) — это числа, приписанные строкам и столбцам матрицы, такие что для всех \( i, j \) выполняется неравенство:

\[ u_i + v_j \le c_{ij} \]

(для задачи минимизации). Сумма всех потенциалов \( \sum u_i + \sum v_j \) является нижней границей для стоимости любого назначения. Если удаётся найти такое паросочетание, что для всех его рёбер выполняется равенство \( u_i + v_j = c_{ij} \), то это паросочетание является оптимальным.

Описание алгоритма

Венгерский метод решает задачу минимизации. Для задачи максимизации достаточно умножить все элементы матрицы на -1 или вычесть их из максимального значения.

Алгоритм состоит из нескольких этапов:

Этап 1: Редукция матрицы

Из каждого элемента каждой строки вычитается минимальный элемент этой строки. Затем из каждого элемента каждого столбца вычитается минимальный элемент этого столбца. После этой операции в каждой строке и каждом столбце появляется хотя бы один нулевой элемент. Сумма вычтенных величин равна нижней границе стоимости оптимального назначения.

Этап 2: Поиск максимального паросочетания по нулям

В полученной матрице строится двудольный граф, рёбрами которого являются нулевые элементы. Необходимо найти максимальное паросочетание в этом графе. Если удаётся найти паросочетание, покрывающее все строки и все столбцы (то есть размером \( n \)), то это паросочетание и есть оптимальное решение. Если нет — переходят к следующему этапу.

Этап 3: Построение минимального вершинного покрытия

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

Этап 4: Коррекция потенциалов

Находится минимальный элемент среди элементов, не входящих в вершинное покрытие. Этот элемент вычитается из всех непокрытых строк и прибавляется ко всем покрытым столбцам. В результате появляются новые нулевые элементы, и алгоритм возвращается к этапу 2.

Процесс повторяется до тех пор, пока не будет найдено паросочетание размера \( n \).

Сложность и эффективность

Венгерский метод имеет вычислительную сложность \( O(n^3) \). Это делает его эффективным для задач с размерностью до нескольких тысяч элементов. Для задач с большей размерностью могут использоваться приближённые алгоритмы или алгоритмы на основе симплекс-метода.

Применение

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

• Логистика и транспорт: распределение транспортных средств по маршрутам, минимизация времени доставки.
• Производство: распределение станков по задачам, минимизация времени обработки деталей.
• Информатика: решение задачи о назначении в системах распределённых вычислений, балансировка нагрузки на серверы.
• Экономика: распределение ресурсов между проектами, оптимизация портфеля инвестиций.
• Обработка изображений: сопоставление точек на двух изображениях (например, в задачах стереозрения или отслеживания объектов).
• Биоинформатика: выравнивание последовательностей ДНК, сопоставление генов.

Модификации и обобщения

Существует несколько модификаций венгерского метода:

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

Критика и ограничения

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

Источники

• Kuhn, H. W. (1955). «The Hungarian method for the assignment problem». Naval Research Logistics Quarterly, 2(1-2), 83-97.
• Munkres, J. (1957). «Algorithms for the assignment and transportation problems». Journal of the Society for Industrial and Applied Mathematics, 5(1), 32-38.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). «Алгоритмы: построение и анализ». 3-е изд. — М.: Вильямс.
• Papadimitriou, C. H., Steiglitz, K. (1998). «Combinatorial Optimization: Algorithms and Complexity». Dover Publications.