Угорський алгоритм

Припустимо, що ми маємо 3 працівників: Джима, Стіва та Алана. Необхідно, щоб один з них прибрав у ванній, інший — підмів підлогу, а третій — помив вікна. Який найкращий (з найменшими витратами) шлях розподілити роботи між ними? Спершу нам необхідно побудувати матрицю витрат на виконання робіт нашими працівниками:

Угорський алгоритм, після застосування його до цієї таблиці, дасть нам мінімальні витрати, з якими можуть бути виконані роботи: Джим прибирає у ванній, Стів підмітає підлогу, а Алан миє вікна.

Дано невід'ємну матрицю nxn, де елемент в і-тому рядку та j-тому стовпці показує вартість призначення j-тої роботи і-тому працівникові. Необхідно знайти розподіл робіт між працівниками з найменшими загальними витратами. Якщо ціллю є знайти розподіл робіт, що максимізує витрати, в постановці задачі необхідно кожну вартість замінити на максимальну вартість мінус дану вартість.

Алгоритм простіше описати, якщо ми сформулюємо проблему використовуючи дводольний граф. Ми маємо повний дводольний граф G=(S, T; E) з вершинами для n працівників (S) та вершинами для n робіт (T), а кожна грань має невід'ємні витрати c(i, j). Нам необхідно знайти досконале паросполучення з мінімальними витратами.

Нехай функція ${\displaystyle y=\left(S\bigcup T\right)\to \ R,\;}$ є потенціалом, якщо ${\displaystyle y\left(i\right)+y\left(j\right)\leq \ c\left(i,j\right)\;}$ для кожного ${\displaystyle i\in S\;}$ та ${\displaystyle j\in T\;}$. Значенням потенціалу є ${\displaystyle v\in S\bigcup T;}$. Витрати кожного досконалого паросполучення щонайменше дорівнюють потенціалу. Угорський метод знаходить досконале паросполучення та потенціал з однаковими витратами/значенням, що доводить оптимальність обох. Фактично, метод знаходить досконале паро сполучення для строгих граней: грань ij називається строгою для потенціалу ${\displaystyle y}$ якщо${\displaystyle y\left(i\right)+y\left(j\right)=\ c\left(i,j\right)\;}$. Нехай ${\displaystyle G_{y}}$ позначає субграф строгих граней. Вартість досконалого паросполучення в ${\displaystyle G_{y}}$ (якщо таке існує) дорівнює вартості ${\displaystyle y}$.

Під час алгоритму ми маємо справу з потенціалом та напрямом ${\displaystyle {\vec {G}}_{y}\ }$ який має властивість, що грані орієнтовані з T в S утворюють сполучення М. На початку, всюди ${\displaystyle y=0}$, а всі грані орієнтовані з S в T (М порожній). На кожному кроці, ми або модифікуємо ${\displaystyle y}$ щоб значення зростало, чи модифікуємо напрям щоб отримати сполучення з якомога більшою кількістю граней. Ми маємо справу з випадком, де всі грані М є строгими. Якщо М є досконалим паросполученням, то задачу розв'язано.

В загальному, нехай ${\displaystyle R_{s}\subseteq S}$ і ${\displaystyle R_{t}\subseteq T}$ є вершинами не покритими М (тобто ${\displaystyle R_{s}}$ складається з вершин в S без вхідних граней, а ${\displaystyle R_{t}}$ складається з вершин в Т без вихідних граней). Нехай ${\displaystyle Z}$ є множиною вершин, що є допустимими в ${\displaystyle {\vec {G}}_{y}\ }$ з ${\displaystyle R_{s}}$ слідкуючи орієнтованою ціллю лише строгим граням. Це можна розрахувати за допомогою пошуку у ширину.

Якщо ${\displaystyle R_{t}\cap Z}$ є непорожнім, то слід обернути напрям орієнтованої цілі в ${\displaystyle {\vec {G}}_{y}\ }$ з ${\displaystyle R_{s}}$ до ${\displaystyle R_{t}}$. Таким чином, розмір відповідного сполучення зростає на 1. Якщо ${\displaystyle R_{t}\cap Z}$ є порожнім, тоді нехай ${\displaystyle \Delta \ =min\left\{c\left(i,j\right)-y\left(i\right)-y\left(j\right):y\in Z\cap S,j\in T\setminus \mathbb {Z} \right\}}$. ${\displaystyle \Delta \;}$ є додатнім, оскільки строгі грані відсутні між ${\displaystyle Z\cap S}$ та ${\displaystyle T\setminus \mathbb {Z} }$. ${\displaystyle Y}$ зростає на ${\displaystyle \Delta \;}$ на вершинах ${\displaystyle Z\cap S}$ та зменшується на ${\displaystyle \Delta \;}$ на вершинах ${\displaystyle Z\cap T}$. Результуючий ${\displaystyle y}$ все ще є потенціалом. Граф ${\displaystyle G_{y}}$ змінюється, але досі містить М. Ми орієнтуємо нові грані з S в Т. За означенням ${\displaystyle \Delta \;}$ множина вершин Z, що досягається з ${\displaystyle R_{s}}$, зростає (кількість строгих граней не обов'язково зростає).

Ці кроки повторюються поки М не є досконалим сполученням, тоді ми отримуємо мінімальну вартість виконання завдання. Час виконання цієї версії методу дорівнює ${\displaystyle O\left(n^{4}\right)}$. М доповнюється n разів, і у фазі, де М не змінюється, існує щонайбільше n потенційних змін (оскільки Z зростає щоразу). Час необхідний для потенційних змін дорівнює ${\displaystyle O\left(n^{2}\right)}$.

Дано n працівників та m робіт, а також матриця nxm, що містить вартість виконання завдання кожним з працівників. Для того, щоб знайти розподіл обов'язків з мінімальними загальними витратами, необхідно виконати наступні кроки:

1. Впорядкувати інформацію в матриці таким чином, щоб рядки матриці представляли «виконавців», а колонки — «завдання», тоді як кожен елемент матриці представляє витрати на виконання певним виконавцем певного завдання.
2. Переконатися в тому, що матриця є квадратною; в протилежному випадку слід додати фіктивний рядок (виконавця) чи колонку (завдання), де кожен елемент буде дорівнювати найбільшому елементу початкової матриці.
3. В кожному рядку від кожного елемента відняти найменше значення для даного рядка.
4. В кожному стовпці від кожного елемента відняти найменше значення для даного стовпця.
5. Викреслити всі нульові елементи з найменш можливою кількістю ліній (якщо кількість ліній дорівнює розмірності матриці, то слід перейти до кроку 9).
6. Додати мінімальний з не викреслених елементів до кожного викресленого елементу (якщо елемент викреслено двома лініями, то додавати слід теж двічі)
7. Від кожного елементу матриці відняти мінімальний елемент.
8. Знову викреслити всі нульові елементи використовуючи найменшу кількість ліній (якщо кількість використаних ліній не дорівнює розмірності матриці, то слід повернутись до кроку 6).
9. Вибрати розподіл «завдань» між «виконавцями» таким чином, щоб в кожному рядкові та стовпці був вибраний лише один нуль.
10. Перенести розподіл на першопочаткову матрицю, ігноруючи фіктивні колонки і рядки. Цей розподіл покаже який «виконавець» яке «завдання» має виконати, а сума виділених елементів покаже загальну вартість виконання робіт.

Дано 5 працівників (A, B, C, D, E) та 4 роботи (W, X, Y, Z), які необхідно розподілити між ними. Витрати на виконання кожним з працівників кожного із завдань представлені у наступній таблиці:

Таким чином, ми отримуємо наступну матрицю:

Отримана матриця має, розмірність 5х4, що суперечить другій стадії вище наведеного алгоритму. Таким чином, маємо додати фіктивну колонку із завданням, кожен елемент якої дорівнює максимальному елементові матриці:

Виконаємо крок 3 (в кожному рядку віднімемо мінімальне значення) і крок 4 (в кожному стовпці віднімаємо мінімальне значення):

Викресливши всі нулі з використанням мінімальної кількості ліній, бачимо, що їх кількість (4) не відповідає розмірності матриці (5х5). Тому виконуємо кроки 6 (до кожного викресленого елементу додаємо найменший з невикреслених) і 7 (віднімаємо від усіх елементів матриці найменший з них):

Знову, викресливши всі нулі з використанням мінімальної кількості ліній, бачимо, що їх кількість (4) не відповідає розмірності матриці (5х5). Тому виконуємо ще одну ітерацію з кроками 6 і 7 алгоритму:

Викресливши всі нулі з використанням мінімальної кількості ліній, їх кількість (5) відповідає розмірності матриці (5х5). Переходимо до 9 кроку, де вибираємо розподіл завдань між виконавцями з урахуванням умови, що в кожному рядку і стовпчику має бути лише один виділений нуль:

Переносимо отриманий розподіл в оригінальну таблицю ігноруючи фіктивний стовпець:

Таким чином, виконавець А робить завдання W, виконавець В виконує завдання У, виконавець С виконує завдання Z, виконавець Е виконує завдання Х, а виконавець D відпочиває. Сукупна вартість виконання цих робіт дорівнює 10+7+14+17=48, що є мінімальною вартістю виконання цих завдань наявними працівниками.

• R.E. Burkard, M. Dell'Amico, S. Martello: Assignment Problems (Revised reprint). SIAM, Philadelphia (PA.) 2012. ISBN 978-1-61197-222-1
• M. Fischetti, «Lezioni di Ricerca Operativa», Edizioni Libreria Progetto Padova, Italia, 1995.
• R. Ahuja, T. Magnanti, J. Orlin, «Network Flows», Prentice Hall, 1993.
• S. Martello, «Jeno Egerváry: from the origins of the Hungarian algorithm to satellite communication». Central European Journal of Operations Research 18, 47–58, 2010

• Bruff, Derek, «The Assignment Problem and the Hungarian Method»,
• Mordecai J. Golin, Bipartite Matching and the Hungarian Method, Course Notes, Hong Kong University of Science and Technology.
• R. A. Pilgrim, Munkres' Assignment Algorithm. Modified for Rectangular Matrices, Course notes, Murray State University.
• Mike Dawes, The Optimal Assignment Problem, Course notes, University of Western Ontario.
• On Kuhn's Hungarian Method — A tribute from Hungary, András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
• Lecture: Fundamentals of Operations Research — Assignment Problem — Hungarian Algorithm, Prof. G. Srinivasan, Department of Management Studies, IIT Madras.
• Extension: Assignment sensitivity analysis (with O(n^4) time complexity), Liu, Shell.
• Solve any Assignment Problem online, provides a step by step explanation of the Hungarian Algorithm.

Реалізації
Note that not all of these satisfy the ${\displaystyle O(n^{3})}$ time constraint.

C implementation with ${\displaystyle O(n^{3})}$ time complexity
Java implementation of ${\displaystyle O(n^{3})}$ time variant
Java implementation of ${\displaystyle O(n^{3})}$ time variant by Shawn T. O'Neil
Python implementation
Ruby implementation with unit tests
C# implementation with ${\displaystyle O(n^{3})}$ time complexity
D implementation with unit tests (port of the Java ${\displaystyle O(n^{3})}$ version)
Online interactive implementation
Graphical implementation with options (Java applet)
Serial and parallel implementations.
Matlab and C
Perl implementation
C++ (STL) implementation (multi-functional bipartite graph version)
C++ implementation
C++ implementation of the ${\displaystyle O(n^{3})}$ algorithm (BSD style open source licensed)
Java implementation with JUnit tests (Apache 2.0)[недоступне посилання з травня 2019]
MATLAB implementation
C implementation
JavaScript implementation with unit tests (port of the Java ${\displaystyle O(n^{3})}$ version)
Clue R package proposes an implementation, solve_LSAP
Node.js implementation on GitHub
Python implementation in scipy package