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

Угорський алгоритм — алгоритм комбінаторної оптимізації, що розв'язує задачу про призначення за поліноміальний час і який передує пізнішому симплекс-методу (пряма і двоїста задачі).

Алгоритм був вперше запроваджений в 1955 році Гарольдом Куном^[en] у його статті «Угорський метод для задачі про призначення» на основі праць угорських математиків Денеша Кьоніга та Ейгена Егерварі^[en] (що і дало назву методу).[1][2]

В 1957 році Джеймс Манкрес^[en] переглянув алгоритм і дійшов висновку, що він є (строго) поліноміальним.[3] З того часу алгоритм більш відомий як алгоритм Куна-Манкреса або задача про призначення Макреса. Часова складність оригінального алгоритму була O(n^4), проте Джек Едмондс^[en] та Річард Карп, а також незалежно від них Томізава, відмітили, що він може бути модифікований для отримання часу виконання O(n^3). Лестер Рандольф Форд (молодший)^[en] та Делберт Рей Фулкерсон^[en] розширили метод до загальних транспортних задач. У 2006 році було відкрито, що Карл Густав Якобі розв'язав задачу про призначення в 19 сторіччі, а його розв'язок було опубліковано посмертно в 1890 році латинською мовою.[4]

Пояснення Леймана

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

	Прибрати у ванній	Підмести підлогу	Помити вікна
Джим	$1	$2	$3
Стів	$3	$3	$3
Алан	$3	$3	$2

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

Постановка задачі

Дано невід'ємну матрицю 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. Перейти до кроку 5.
9. Вибрати розподіл «завдань» між «виконавцями» таким чином, щоб в кожному рядкові та стовпці був вибраний лише один нуль.
10. Перенести розподіл на першопочаткову матрицю, ігноруючи фіктивні колонки і рядки. Цей розподіл покаже який «виконавець» яке «завдання» має виконати, а сума виділених елементів покаже загальну вартість виконання робіт.

Приклад розв'язання типової задачі

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

	W	X	Y	Z
A	10	19	8	15
B	10	18	7	17
C	13	16	9	14
D	12	19	8	19
E	14	17	10	19

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

10	19	8	15
10	18	7	17
13	16	9	14
12	19	8	19
14	17	10	19

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

10	19	8	15	19
10	18	7	17	19
13	16	9	14	19
12	19	8	19	19
14	17	10	19	19

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

2	11	0	7	11
3	11	0	10	12
4	7	0	5	10
4	11	0	10	11
4	7	0	9	9

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

1	5	2	3	3
1	4	1	5	3
3	1	2	1	2
2	4	1	5	2
3	1	2	5	1

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

1	4	2	2	2
1	3	1	4	2
4	1	3	1	2
2	3	1	4	1
4	1	3	5	1

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

0	3	1	1	1
0	2	0	3	1
3	0	2	0	1
1	2	0	3	0
3	0	2	4	0

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

	W	X	Y	Z
A	10	19	8	15
B	10	18	7	17
C	13	16	9	14
D	12	19	8	19
E	14	17	10	19

Таким чином, виконавець А робить завдання 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

Примітки

1. Harold W. Kuhn, «The Hungarian Method for the assignment problem», Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
2. Harold W. Kuhn, «Variants of the Hungarian method for assignment problems», Naval Research Logistics Quarterly, 3: 253—258, 1956.
3. J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
4. http://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm

Посилання

• Bruff, Derek, «The Assignment Problem and the Hungarian Method», [1]
• 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