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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

В 1957 році Джеймс Манкрес[en] переглянув алгоритм і дійшов висновку, що він є (строго) поліноміальним.[3] З того часу алгоритм більш відомий як алгоритм Куна-Манкреса або задача про призначення Макреса. Часова складність оригінального алгоритму була O(n4), проте Джек Едмондс[en] та Річард Карп, а також незалежно від них Томізава, відмітили, що він може бути модифікований для отримання часу виконання O(n3). Лестер Рандольф Форд (молодший)[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). Нам необхідно знайти досконале паросполучення з мінімальними витратами.

Нехай функція є потенціалом, якщо для кожного та . Значенням потенціалу є . Витрати кожного досконалого паросполучення щонайменше дорівнюють потенціалу. Угорський метод знаходить досконале паросполучення та потенціал з однаковими витратами/значенням, що доводить оптимальність обох. Фактично, метод знаходить досконале паро сполучення для строгих граней: грань ij називається строгою для потенціалу якщо. Нехай позначає субграф строгих граней. Вартість досконалого паросполучення в (якщо таке існує) дорівнює вартості .

Алгоритм в переводі на дводольні графи[ред. | ред. код]

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

В загальному, нехай і є вершинами не покритими М (тобто складається з вершин в S без вхідних граней, а складається з вершин в Т без вихідних граней). Нехай є множиною вершин, що є допустимими в з слідкуючи орієнтованою ціллю лише строгим граням. Це можна розрахувати за допомогою пошуку у ширину.

Якщо є непорожнім, то слід обернути напрям орієнтованої цілі в з до . Таким чином, розмір відповідного сполучення зростає на 1. Якщо є порожнім, тоді нехай . є додатнім, оскільки строгі грані відсутні між та . зростає на на вершинах та зменшується на на вершинах . Результуючий все ще є потенціалом. Граф змінюється, але досі містить М. Ми орієнтуємо нові грані з S в Т. За означенням множина вершин Z, що досягається з , зростає (кількість строгих граней не обов'язково зростає).

Ці кроки повторюються поки М не є досконалим сполученням, тоді ми отримуємо мінімальну вартість виконання завдання. Час виконання цієї версії методу дорівнює . М доповнюється n разів, і у фазі, де М не змінюється, існує щонайбільше n потенційних змін (оскільки Z зростає щоразу). Час необхідний для потенційних змін дорівнює .

Матрична інтерпретація[ред. | ред. код]

Дано 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), які необхідно розподілити між ними. Витрати на виконання кожним з працівників кожного із завдань представлені у наступній таблиці:

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
1 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
0 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

Посилання[ред. | ред. код]

Реалізації
Note that not all of these satisfy the time constraint.
C implementation with time complexity
Java implementation of time variant
Java implementation of time variant by Shawn T. O'Neil
Python implementation
Ruby implementation with unit tests
C# implementation with time complexity
D implementation with unit tests (port of the Java 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 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 version)
Clue R package proposes an implementation, solve_LSAP
Node.js implementation on GitHub
Python implementation in scipy package