Цю статтю треба для відповідності Вікіпедії. (червень 2014) |
Угорський алгоритм — алгоритм комбінаторної оптимізації, що розв'язує задачу про призначення за поліноміальний час і який передує пізнішому симплекс-методу (пряма і двоїста задачі).
Алгоритм був вперше запроваджений в 1955 році [en] у його статті «Угорський метод для задачі про призначення» на основі праць угорських математиків Денеша Кьоніга та [en] (що і дало назву методу).
В 1957 році [en] переглянув алгоритм і дійшов висновку, що він є (строго) поліноміальним. З того часу алгоритм більш відомий як алгоритм Куна-Манкреса або задача про призначення Макреса. Часова складність оригінального алгоритму була O(n4), проте [en] та Річард Карп, а також незалежно від них Томізава, відмітили, що він може бути модифікований для отримання часу виконання O(n3). [en] та [en] розширили метод до загальних транспортних задач. У 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). Нам необхідно знайти досконале паросполучення з мінімальними витратами.
Нехай функція є потенціалом, якщо для кожного та . Значенням потенціалу є . Витрати кожного досконалого паросполучення щонайменше дорівнюють потенціалу. Угорський метод знаходить досконале паросполучення та потенціал з однаковими витратами/значенням, що доводить оптимальність обох. Фактично, метод знаходить досконале паро сполучення для строгих граней: грань ij називається строгою для потенціалу якщо. Нехай позначає субграф строгих граней. Вартість досконалого паросполучення в (якщо таке існує) дорівнює вартості .
Алгоритм в переводі на двочасткові графи
Під час алгоритму ми маємо справу з потенціалом та напрямом який має властивість, що грані орієнтовані з T в S утворюють сполучення М. На початку, всюди , а всі грані орієнтовані з S в T (М порожній). На кожному кроці, ми або модифікуємо щоб значення зростало, чи модифікуємо напрям щоб отримати сполучення з якомога більшою кількістю граней. Ми маємо справу з випадком, де всі грані М є строгими. Якщо М є досконалим паросполученням, то задачу розв'язано.
В загальному, нехай і є вершинами не покритими М (тобто складається з вершин в S без вхідних граней, а складається з вершин в Т без вихідних граней). Нехай є множиною вершин, що є допустимими в з слідкуючи орієнтованою ціллю лише строгим граням. Це можна розрахувати за допомогою пошуку у ширину.
Якщо є непорожнім, то слід обернути напрям орієнтованої цілі в з до . Таким чином, розмір відповідного сполучення зростає на 1. Якщо є порожнім, тоді нехай . є додатнім, оскільки строгі грані відсутні між та . зростає на на вершинах та зменшується на на вершинах . Результуючий все ще є потенціалом. Граф змінюється, але досі містить М. Ми орієнтуємо нові грані з S в Т. За означенням множина вершин Z, що досягається з , зростає (кількість строгих граней не обов'язково зростає).
Ці кроки повторюються поки М не є досконалим сполученням, тоді ми отримуємо мінімальну вартість виконання завдання. Час виконання цієї версії методу дорівнює . М доповнюється n разів, і у фазі, де М не змінюється, існує щонайбільше n потенційних змін (оскільки Z зростає щоразу). Час необхідний для потенційних змін дорівнює .
Матрична інтерпретація
Дано n працівників та m робіт, а також матриця nxm, що містить вартість виконання завдання кожним з працівників. Для того, щоб знайти розподіл обов'язків з мінімальними загальними витратами, необхідно виконати наступні кроки:
- Впорядкувати інформацію в матриці таким чином, щоб рядки матриці представляли «виконавців», а колонки — «завдання», тоді як кожен елемент матриці представляє витрати на виконання певним виконавцем певного завдання.
- Переконатися в тому, що матриця є квадратною; в протилежному випадку слід додати фіктивний рядок (виконавця) чи колонку (завдання), де кожен елемент буде дорівнювати найбільшому елементу початкової матриці.
- В кожному рядку від кожного елемента відняти найменше значення для даного рядка.
- В кожному стовпці від кожного елемента відняти найменше значення для даного стовпця.
- Викреслити всі нульові елементи з найменш можливою кількістю ліній (якщо кількість ліній дорівнює розмірності матриці, то слід перейти до кроку 9).
- Додати мінімальний з не викреслених елементів до кожного викресленого елементу (якщо елемент викреслено двома лініями, то додавати слід теж двічі)
- Від кожного елементу матриці відняти мінімальний елемент.
- Перейти до кроку 5.
- Вибрати розподіл «завдань» між «виконавцями» таким чином, щоб в кожному рядкові та стовпці був вибраний лише один нуль.
- Перенести розподіл на першопочаткову матрицю, ігноруючи фіктивні колонки і рядки. Цей розподіл покаже який «виконавець» яке «завдання» має виконати, а сума виділених елементів покаже загальну вартість виконання робіт.
Приклад розв'язання типової задачі
Дано 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.
- M. Fischetti, «Lezioni di Ricerca Operativa», Edizioni Libreria Progetto Padova, Italia, 1995.
- , , , «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
Примітки
- Harold W. Kuhn, «The Hungarian Method for the assignment problem», , 2: 83–97, 1955. Kuhn's original publication.
- Harold W. Kuhn, «Variants of the Hungarian method for assignment problems», Naval Research Logistics Quarterly, 3: 253—258, 1956.
- J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
- 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, .
- , Munkres' Assignment Algorithm. Modified for Rectangular Matrices, Course notes, .
- , , Course notes, University of Western Ontario.
- On Kuhn's Hungarian Method — A tribute from Hungary, , 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 time constraint.C implementation with time complexity Java implementation of time variant 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 (Java applet) Serial and parallel implementations. Matlab and C Perl implementation 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cyu stattyu treba vikifikuvati dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit dodavannyam dorechnih vnutrishnih posilan abo vdoskonalennyam rozmitki statti cherven 2014 Ugorskij algoritm algoritm kombinatornoyi optimizaciyi sho rozv yazuye zadachu pro priznachennya za polinomialnij chas i yakij pereduye piznishomu simpleks metodu pryama i dvoyista zadachi Algoritm buv vpershe zaprovadzhenij v 1955 roci en u jogo statti Ugorskij metod dlya zadachi pro priznachennya na osnovi prac ugorskih matematikiv Denesha Koniga ta en sho i dalo nazvu metodu V 1957 roci en pereglyanuv algoritm i dijshov visnovku sho vin ye strogo polinomialnim Z togo chasu algoritm bilsh vidomij yak algoritm Kuna Mankresa abo zadacha pro priznachennya Makresa Chasova skladnist originalnogo algoritmu bula O n4 prote en ta Richard Karp a takozh nezalezhno vid nih Tomizava vidmitili sho vin mozhe buti modifikovanij dlya otrimannya chasu vikonannya O n3 en ta en rozshirili metod do zagalnih transportnih zadach U 2006 roci bulo vidkrito sho Karl Gustav Yakobi rozv yazav zadachu pro priznachennya v 19 storichchi a jogo rozv yazok bulo opublikovano posmertno v 1890 roci latinskoyu movoyu Poyasnennya LejmanaPripustimo sho mi mayemo 3 pracivnikiv Dzhima Stiva ta Alana Neobhidno shob odin z nih pribrav u vannij inshij pidmiv pidlogu a tretij pomiv vikna Yakij najkrashij z najmenshimi vitratami shlyah rozpodiliti roboti mizh nimi Spershu nam neobhidno pobuduvati matricyu vitrat na vikonannya robit nashimi pracivnikami Pribrati u vannij Pidmesti pidlogu Pomiti vikna Dzhim 1 2 3 Stiv 3 3 3 Alan 3 3 2 Ugorskij algoritm pislya zastosuvannya jogo do ciyeyi tablici dast nam minimalni vitrati z yakimi mozhut buti vikonani roboti Dzhim pribiraye u vannij Stiv pidmitaye pidlogu a Alan miye vikna Postanovka zadachiDano nevid yemnu matricyu nxn de element v i tomu ryadku ta j tomu stovpci pokazuye vartist priznachennya j toyi roboti i tomu pracivnikovi Neobhidno znajti rozpodil robit mizh pracivnikami z najmenshimi zagalnimi vitratami Yaksho cillyu ye znajti rozpodil robit sho maksimizuye vitrati v postanovci zadachi neobhidno kozhnu vartist zaminiti na maksimalnu vartist minus danu vartist Algoritm prostishe opisati yaksho mi sformulyuyemo problemu vikoristovuyuchi dvochastkovij graf Mi mayemo povnij dvochastkovij graf G S T E z vershinami dlya n pracivnikiv S ta vershinami dlya n robit T a kozhna gran maye nevid yemni vitrati c i j Nam neobhidno znajti doskonale parospoluchennya z minimalnimi vitratami Nehaj funkciya y S T R displaystyle y left S bigcup T right to R ye potencialom yaksho y i y j c i j displaystyle y left i right y left j right leq c left i j right dlya kozhnogo i S displaystyle i in S ta j T displaystyle j in T Znachennyam potencialu ye v S T displaystyle v in S bigcup T Vitrati kozhnogo doskonalogo parospoluchennya shonajmenshe dorivnyuyut potencialu Ugorskij metod znahodit doskonale parospoluchennya ta potencial z odnakovimi vitratami znachennyam sho dovodit optimalnist oboh Faktichno metod znahodit doskonale paro spoluchennya dlya strogih granej gran ij nazivayetsya strogoyu dlya potencialu y displaystyle y yakshoy i y j c i j displaystyle y left i right y left j right c left i j right Nehaj G y displaystyle G y poznachaye subgraf strogih granej Vartist doskonalogo parospoluchennya v G y displaystyle G y yaksho take isnuye dorivnyuye vartosti y displaystyle y Algoritm v perevodi na dvochastkovi grafiPid chas algoritmu mi mayemo spravu z potencialom ta napryamom G y displaystyle vec G y yakij maye vlastivist sho grani oriyentovani z T v S utvoryuyut spoluchennya M Na pochatku vsyudi y 0 displaystyle y 0 a vsi grani oriyentovani z S v T M porozhnij Na kozhnomu kroci mi abo modifikuyemo y displaystyle y shob znachennya zrostalo chi modifikuyemo napryam shob otrimati spoluchennya z yakomoga bilshoyu kilkistyu granej Mi mayemo spravu z vipadkom de vsi grani M ye strogimi Yaksho M ye doskonalim parospoluchennyam to zadachu rozv yazano V zagalnomu nehaj R s S displaystyle R s subseteq S i R t T displaystyle R t subseteq T ye vershinami ne pokritimi M tobto R s displaystyle R s skladayetsya z vershin v S bez vhidnih granej a R t displaystyle R t skladayetsya z vershin v T bez vihidnih granej Nehaj Z displaystyle Z ye mnozhinoyu vershin sho ye dopustimimi v G y displaystyle vec G y z R s displaystyle R s slidkuyuchi oriyentovanoyu cillyu lishe strogim granyam Ce mozhna rozrahuvati za dopomogoyu poshuku u shirinu Yaksho R t Z displaystyle R t cap Z ye neporozhnim to slid obernuti napryam oriyentovanoyi cili v G y displaystyle vec G y z R s displaystyle R s do R t displaystyle R t Takim chinom rozmir vidpovidnogo spoluchennya zrostaye na 1 Yaksho R t Z displaystyle R t cap Z ye porozhnim todi nehaj D m i n c i j y i y j y Z S j T 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 D displaystyle Delta ye dodatnim oskilki strogi grani vidsutni mizh Z S displaystyle Z cap S ta T Z displaystyle T setminus mathbb Z Y displaystyle Y zrostaye na D displaystyle Delta na vershinah Z S displaystyle Z cap S ta zmenshuyetsya na D displaystyle Delta na vershinah Z T displaystyle Z cap T Rezultuyuchij y displaystyle y vse she ye potencialom Graf G y displaystyle G y zminyuyetsya ale dosi mistit M Mi oriyentuyemo novi grani z S v T Za oznachennyam D displaystyle Delta mnozhina vershin Z sho dosyagayetsya z R s displaystyle R s zrostaye kilkist strogih granej ne obov yazkovo zrostaye Ci kroki povtoryuyutsya poki M ne ye doskonalim spoluchennyam todi mi otrimuyemo minimalnu vartist vikonannya zavdannya Chas vikonannya ciyeyi versiyi metodu dorivnyuye O n 4 displaystyle O left n 4 right M dopovnyuyetsya n raziv i u fazi de M ne zminyuyetsya isnuye shonajbilshe n potencijnih zmin oskilki Z zrostaye shorazu Chas neobhidnij dlya potencijnih zmin dorivnyuye O n 2 displaystyle O left n 2 right Matrichna interpretaciyaDano n pracivnikiv ta m robit a takozh matricya nxm sho mistit vartist vikonannya zavdannya kozhnim z pracivnikiv Dlya togo shob znajti rozpodil obov yazkiv z minimalnimi zagalnimi vitratami neobhidno vikonati nastupni kroki Vporyadkuvati informaciyu v matrici takim chinom shob ryadki matrici predstavlyali vikonavciv a kolonki zavdannya todi yak kozhen element matrici predstavlyaye vitrati na vikonannya pevnim vikonavcem pevnogo zavdannya Perekonatisya v tomu sho matricya ye kvadratnoyu v protilezhnomu vipadku slid dodati fiktivnij ryadok vikonavcya chi kolonku zavdannya de kozhen element bude dorivnyuvati najbilshomu elementu pochatkovoyi matrici V kozhnomu ryadku vid kozhnogo elementa vidnyati najmenshe znachennya dlya danogo ryadka V kozhnomu stovpci vid kozhnogo elementa vidnyati najmenshe znachennya dlya danogo stovpcya Vikresliti vsi nulovi elementi z najmensh mozhlivoyu kilkistyu linij yaksho kilkist linij dorivnyuye rozmirnosti matrici to slid perejti do kroku 9 Dodati minimalnij z ne vikreslenih elementiv do kozhnogo vikreslenogo elementu yaksho element vikresleno dvoma liniyami to dodavati slid tezh dvichi Vid kozhnogo elementu matrici vidnyati minimalnij element Perejti do kroku 5 Vibrati rozpodil zavdan mizh vikonavcyami takim chinom shob v kozhnomu ryadkovi ta stovpci buv vibranij lishe odin nul Perenesti rozpodil na pershopochatkovu matricyu ignoruyuchi fiktivni kolonki i ryadki Cej rozpodil pokazhe yakij vikonavec yake zavdannya maye vikonati a suma vidilenih elementiv pokazhe zagalnu vartist vikonannya robit Priklad rozv yazannya tipovoyi zadachiDano 5 pracivnikiv A B C D E ta 4 roboti W X Y Z yaki neobhidno rozpodiliti mizh nimi Vitrati na vikonannya kozhnim z pracivnikiv kozhnogo iz zavdan predstavleni u nastupnij tablici 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 Takim chinom mi otrimuyemo nastupnu matricyu 10 19 8 15 10 18 7 17 13 16 9 14 12 19 8 19 14 17 10 19 Otrimana matricya maye rozmirnist 5h4 sho superechit drugij stadiyi vishe navedenogo algoritmu Takim chinom mayemo dodati fiktivnu kolonku iz zavdannyam kozhen element yakoyi dorivnyuye maksimalnomu elementovi matrici 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 Vikonayemo krok 3 v kozhnomu ryadku vidnimemo minimalne znachennya i krok 4 v kozhnomu stovpci vidnimayemo minimalne znachennya 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 Vikreslivshi vsi nuli z vikoristannyam minimalnoyi kilkosti linij bachimo sho yih kilkist 4 ne vidpovidaye rozmirnosti matrici 5h5 Tomu vikonuyemo kroki 6 do kozhnogo vikreslenogo elementu dodayemo najmenshij z nevikreslenih i 7 vidnimayemo vid usih elementiv matrici najmenshij z nih 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 Znovu vikreslivshi vsi nuli z vikoristannyam minimalnoyi kilkosti linij bachimo sho yih kilkist 4 ne vidpovidaye rozmirnosti matrici 5h5 Tomu vikonuyemo she odnu iteraciyu z krokami 6 i 7 algoritmu 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 Vikreslivshi vsi nuli z vikoristannyam minimalnoyi kilkosti linij yih kilkist 5 vidpovidaye rozmirnosti matrici 5h5 Perehodimo do 9 kroku de vibirayemo rozpodil zavdan mizh vikonavcyami z urahuvannyam umovi sho v kozhnomu ryadku i stovpchiku maye buti lishe odin vidilenij nul 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 Perenosimo otrimanij rozpodil v originalnu tablicyu ignoruyuchi fiktivnij stovpec 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 Takim chinom vikonavec A robit zavdannya W vikonavec V vikonuye zavdannya U vikonavec S vikonuye zavdannya Z vikonavec E vikonuye zavdannya H a vikonavec D vidpochivaye Sukupna vartist vikonannya cih robit dorivnyuye 10 7 14 17 48 sho ye minimalnoyu vartistyu vikonannya cih zavdan nayavnimi pracivnikami LiteraturaR 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 Network Flows Prentice Hall 1993 S Martello Jeno Egervary from the origins of the Hungarian algorithm to satellite communication Central European Journal of Operations Research 18 47 58 2010PrimitkiHarold W Kuhn The Hungarian Method for the assignment problem 2 83 97 1955 Kuhn s original publication Harold W Kuhn Variants of the Hungarian method for assignment problems Naval Research Logistics Quarterly 3 253 258 1956 J Munkres Algorithms for the Assignment and Transportation Problems Journal of the Society for Industrial and Applied Mathematics 5 1 32 38 1957 March http www lix polytechnique fr ollivier JACOBI jacobiEngl htmPosilannyaBruff Derek The Assignment Problem and the Hungarian Method 1 Mordecai J Golin Bipartite Matching and the Hungarian Method Course Notes Munkres Assignment Algorithm Modified for Rectangular Matrices Course notes Course notes University of Western Ontario On Kuhn s Hungarian Method A tribute from Hungary 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 Realizaciyi Note that not all of these satisfy the O n 3 displaystyle O n 3 time constraint C implementation with O n 3 displaystyle O n 3 time complexity Java implementation of O n 3 displaystyle O n 3 time variant Python implementation Ruby implementation with unit tests C implementation with O n 3 displaystyle O n 3 time complexity D implementation with unit tests port of the Java O n 3 displaystyle O n 3 version Online interactive implementation Java applet Serial and parallel implementations Matlab and C Perl implementation C implementation C implementation of the O n 3 displaystyle O n 3 algorithm BSD style open source licensed Java implementation with JUnit tests Apache 2 0 nedostupne posilannya z travnya 2019 MATLAB implementation C implementation JavaScript implementation with unit tests port of the Java O n 3 displaystyle O n 3 version Clue R package proposes an implementation solve LSAP Node js implementation on GitHub Python implementation in scipy package