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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм в переводі на двочасткові графи

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

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

Якщо $R_{t}\cap Z$ є непорожнім, то слід обернути напрям орієнтованої цілі в ${\vec {G}}_{y}\$ з $R_{s}$ до $R_{t}$. Таким чином, розмір відповідного сполучення зростає на 1. Якщо $R_{t}\cap Z$ є порожнім, тоді нехай $\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\}$. $\Delta \;$ є додатнім, оскільки строгі грані відсутні між $Z\cap S$ та $T\setminus \mathbb {Z}$. $Y$ зростає на $\Delta \;$ на вершинах $Z\cap S$ та зменшується на $\Delta \;$ на вершинах $Z\cap T$. Результуючий $y$ все ще є потенціалом. Граф $G_{y}$ змінюється, але досі містить М. Ми орієнтуємо нові грані з S в Т. За означенням $\Delta \;$ множина вершин Z, що досягається з $R_{s}$, зростає (кількість строгих граней не обов'язково зростає).

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

Посилання

• 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.