Mađarski algoritam

Mađarski algoritam je kombinatorijalni optimizacioni algoritam koji rešava problem dodele koji ima složenost subeksponencijalno vremena i koji iščekuje kasnije primal-dual metode. Razvio ga je i objavio 1955. godine Harold Kan, koji ga je nazvao Mađarski algoritam jer je on svoj rad zasnovao na radu dvojice mađarskih matematičara: Dénes Kőnig and Jenő Egerváry.

Džejms Mankres je proceni o aloritam 1957. i uvideo da je vremensa složenost subeksponencijalno vreme. Od tada je algoritam poznat i kao Kan-Mankresov algoritam ili Mankresov algoritam dodele. Teorija kompleksnosti ovog algoritam je bila O(n^4), ali su Edmonds i Karp, i odvojeno od njih Tomicava uvideli da može da dostigne i kubnu složenost. Ford i Falkerson su unapredili metodu do opšteg problema transportacije. 2006. otkriveno je da je Karl Gustav Džakobi rešio taj problem u 19. veku, i da je rešenje objavljeno 1890. na latinskom jeziku.

Jednostavno objašnjenje problema dodele

U ovom primeru postoje tru radnika: Pera, Mika i Žika. Jedan od njih mora da očisti toalet, jedan da briše podove, i jedan da pere prozore, ali sva trojica traže različitu platu za različite probleme. Problem je naći najjeftiniji način da se raspodeli posao. Problem može da se predstavi matricom cena. Na primer:

	Brisanje toaleta	Brisanje podova	Brisanje prozora
Pera	$2	$3	$3
Mika	$3	$2	$3
Žika	$3	$3	$2

Mađarska metoda, kada se primeni na tabelu iznad, daje minimalnu cenu, koja bi bila 6$ tako što bi Pera prao toalet, Mika brisao podove, a Žika prozore.

Podešavanje

Uzimamo nenegativnu kvadratnu matricu, gde je element u i-toj koloni i j-tom redu predstavlja cenu dodele j-tog posla i-tom radniku. Moramo da nađemo posao radnicima koji će nas najmanje koštati. 

Algoritam se može jednostavnije objasniti ako formulišemo problem pomoću bipartitivnog grafa. Ako imamo potpuni bipartitivni graf G = (S, T, E) sa n radnika grana (S) i n poslova grana (T), gde svaka grana ima nenegativnu cenu c(i, j). Hoćemo da nađemo najbolje poklapanje sa minimalnom cenom.

Sada pozivamo funkciju y: (S U T) -> R čiji je potencijal y(i) + y(j) <= c(i, j) za svako i koje pripada S, j koji pripadaju T. Može se primetiti da je cena savršenog poklapanja  bar vrednost svakog potencijala. Mađarska metoda nalazi savršeno poklapanje i potencijal sa jednakim cenama koji dokazuje optimalnost.

Algoritam predstavljen preko bipartitivnog grafa

Tokom rada algoritma čuvamo potencijal y i orijentaciju Gy koja ima osobinu da su sve grane orijentisane od T do S čine poklapanje M. Inicijano y je 0 svuda, i sve grane su orijentisane od S do T, a M je prazno. U svakom korak uili menjamo y tako što mu vrednost povećavamo ili menjamo orijantaciju da bismo postigli poklapanje sa više grana. Završili smo ako je M savršeno poklapanje.

U generalnom koraku, neka su $R_{S}\subseteq S$ and $R_{T}\subseteq T$ čvorovi koji nisu pređeni sa M (tako se $R_{S}$ sastoji od čvorova u S bez ulaznih grana i $R_{T}$ koji se sadrži od čvorova iz T bez izlaznih grana). Neka je $Z$ set čvorova koji mogu da se dohvate u  ${\overrightarrow {G_{y}}}$ od $R_{S}$ pomoću usmerene putanje koja prati samo grane koje su zbijene. Ovo može da se izračuna pomoću pretrage u dubinu.

Ako je $R_{T}\cap Z$ neprazan, onda okreni orijentaciju putanje usmerenog grafa  ${\overrightarrow {G_{y}}}$ od $R_{S}$ do $R_{T}$. Tako je veličina odgovarajućih poklapanja povećana za 1.

Ako je $R_{T}\cap Z$ prazan, onda neka je$\Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$. $\Delta$ pozitivan jer nema zbijenih grana u $Z\cap S$ i  $T\setminus Z$. Povećaj y by $\Delta$ na čvorovima $Z\cap S$ i smanji y za $\Delta$ na čvoroima $Z\cap T$. Rezultujuće y je i dalje potencijal. Graf $G_{y}$ se menja, ali i dalje sadrži M. Orijentišemo nove grane od S do T. Po definiciji $\Delta$ set Z čvorova koji mogu da se dohvate od $R_{S}$ se povećava (napomena je da se broj zbijenih grana ne mora povećati).

Ponavljamo ove korake sve dok M jeste savršeno poklapanje, i tom slučaju dobijamo minimalnu cenu za dodelu. Složenost ove verzije je O(n^4): M se povećava n puta, a u fazi gde je M nepromenjeno, postoji najviše n potencijalnih promena. Vreme koje je potrebno za potencijalnu promenu je O(n^2).

Interpretacija algoritma preko matrica

Ako imamo n radnika i zadataka, i nxn matricu koja sadrži cene dodele nekog posla svakom radniku, tražimo najbolju varijantu.

Prvo se problem zadaje kao matrica ispod:

${\begin{bmatrix}a1&a2&a3&a4\\b1&b2&b3&b4\\c1&c2&c3&c4\\d1&d2&d3&d4\end{bmatrix}}$

gde su a, b, c, i d radnici koji moraju da rade poslove 1, 2, 3, 4. a1, a2, a3, i a4 obeležavaju šta bi se desilo kad bi radnik a, radio određene zadatke. Isto važi i za ostale simbole takođe. Matrica je kvadratna, tako da svaki radnik može da obavlja jedan posao.

Korak 1

Onda radimo operacije sa kolonama. Da bismo izveli to, najmanji od ai se umanjujeod vsakog element au tom redu. To će dovesti do bar jedne nule u tom redu. Ova radnja se obavlja za sve kolone. Sada imamo matricu sa najmanje jednom nulom po jednom redu. Sada pokušavamo da dodelimo poslove agentima tako da svaki agent radi samo jedan posao. Ovo je ilustrovano ispod:

0	a2'	a3'	a4'
b1'	b2'	b3'	0
c1'	0	c3'	c4'
d1'	d2'	0	d4'

Nule koje su opisane kao 0’ su dodeljeni poslovi

Korak 2

Ponekad se može ispostaviti da je matricu u ovoj gazi neupotrebljiva za operaciju dodele, kao što je prikazano u primeru ispod.

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

U slučaju iznad, nijedna dodela ne može da se izvrši. Napomena je da se u zadatak 1 efikasno odradio za agenta a i c. Ne mogu obojica da dobiju isti zadatak. Takođe treba napomenuti da niko ne obavlja zadatak 3 efikasno. Da bi se ovo prevazišlo, ponavljamo proceduru iznas po svim kolonama, i onda opet gledamo da li su dodele moguće.

U većini slučajeva će ovo da da rezultat, ali ako ne, proces se opet ponavlja itd.

Korak 3

Sve nule u matrici moraju da budu prođene tako što ćemo markirati što manje kolona i redova je moguće. Sledeća procedura obavlja to:

Prvo, dodeljujemo što više zadataka je moguće.

• Red 1 ima jednu nulu, znači da je dodeljen. Nula u redu 3 je precrtana jer je u istoj koloni 
• Red 2 ima jednu nulu, i onda je dodeljena 
• Jedina nula u redu 3 je precrtana, tako da ništa nije dodeljeno 
• Red 4 ima dve neprecrtane nule. Bilo koja od njih može biti dodeljena, a druga nula će biti precrtana 

Alterantivno, nula u redu 3 može biti dodeljena, što bi prouzrokovalo nulu u prvom redu da bude precrtana.

0'	a2'	a3'	a4'
b1'	b2'	b3'	0'
0	c2'	c3'	c4'
d1'	0'	0	d4'

A sad deo sa crtanjem:

• Obeležimo sve redove koji nemaju dodele 
• Obeležimo sve neoznačene kolone koje imaju nule u novoobeleženim redovima 
• Obeležimo sve redove koje imaju kolone sa prethodne tačke 
• Ponavljamo za sve neoznačene redove 

×
0'	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0	c2'	c3'	c4'	×
d1'	0'	0	d4'

Sada crtamo linije kroz sve obeležene kolone i neobeležene redove

×
0'	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0	c2'	c3'	c4'	×
d1'	0'	0	d4'

Ovo je samo jedan način za crtanje matrice. Postoji još nekoliko dokazanih i proverenih načina sa istim ishodom

Korak 4

Sada uklanjamo obeležene redove i kolone. Onda će matrica izgledati ovako.

${\begin{bmatrix}a2&a3&a4\\c2&c3&c4\end{bmatrix}}$

Vratimo se na korak 1 i ponaljavmo proces dok matrica nije prazna.

Bibliografija

• 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

Spoljašnje veze

• Bruff, Derek, "The Assignment Problem and the Hungarian Method", [1] Arhivirano na sajtu Wayback Machine (5. januar 2012)
• 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 Arhivirano na sajtu Wayback Machine (9. avgust 2017), 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.

Implementacije

(Napomena: neće svi algoritmi ispod da zadovolje  O(n^3) složenost)

• C implementation with $O(n^{3})$ time complexity
• Java implementation of $O(n^{3})$ time variant
• Python implementation (see also here)
• Ruby implementation with unit tests
• C# implementation
• D implementation with unit tests (port of the Java $O(n^{3})$ version) Arhivirano na sajtu Wayback Machine (30. decembar 2019)
• Online interactive implementation Please note that this implements a variant of the algorithm as described above.
• Graphical implementation with options (Java applet)
• Serial and parallel implementations.
• Implementation in Matlab and C Arhivirano na sajtu Wayback Machine (3. maj 2008)
• Perl implementation
• Lisp implementation
• C++ (STL) implementation (multi-functional bipartite graph version) Arhivirano na sajtu Wayback Machine (16. februar 2020)
• C++ implementation
• C++ implementation of the $O(n^{3})$ algorithm (BSD style open source licensed)
• Another C++ implementation with unit tests
• MATLAB implementation
• C implementation
• Javascript implementation
• The clue R package proposes an implementation, solve_LSAP