Hongaars algoritme

Het Hongaars algoritme is een combinatorisch optimalisatiealgoritme dat een toewijzingsprobleem oplost in een tijd van orde $O(n^{3})$. De eerste versie, gekend als de Hongaarse methode, werd uitgevonden en gepubliceerd door Harold Kuhn in 1955. Deze versie werd herwerkt door James Munkres in 1957 en wordt sindsdien het Hongaars algoritme, het Munkres toewijzingsalgoritme of het Kuhn-Munkres algoritme genoemd.

Het algoritme ontwikkeld door Kuhn was in grote mate gebaseerd op het werk van twee andere Hongaarse wiskundigen: Dénes König en Jenő Egerváry.

Voorbeeld: een minimalisatieprobleem

Zij gegeven $n$ arbeiders, $n$ taken en een $n\times n$ matrix die de kosten bevat van elke mogelijke toewijzing van een taak aan een arbeider. De bedoeling is om nu een toewijzing te vinden met minimale kost.

Om te beginnen wordt het probleem uitgeschreven in een matrix:

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

Hierin zijn a, b, c en d de arbeiders die de taken 1, 2, 3 en 4 moeten uitvoeren. a1, a2, a3 en a4 stellen de kosten voor wanneer persoon a respectievelijk de taak 1, 2, 3, of 4 uitvoert. Analoog voor de andere notaties. De matrix is vierkant, dit betekent dat elke arbeider slechts één taak kan uitvoeren en dat elke taak zal uitgevoerd worden.

Vervolgens passen we rijoperaties toe op deze matrix. De laagste van alle $a_{i}$ met $i$ tussen 1 en 4 wordt gekozen. Deze waarde wordt afgetrokken van de andere elementen in die rij. Dit zorgt er voor dat er minstens één nul in deze rij komt te staan. Men krijg meerdere nullen wanneer er gelijke elementen met de laagste waarde in die rij staan. Deze procedure wordt herhaald voor elke rij. Nu hebben we dus een matrix met minstens één nul op elke rij. Nu proberen we de arbeiders toe te wijzen zodat elke arbeider slechts één taak doet en de kost voor elke taak nul is. Dit is hier onder geïllustreerd.\\ 0     a2'   0'   a4'
b1'   b2'   b3'   0'
0'    c2'   c3'   c4'
d1'   0'    d3'  d4'

De nullen die aangeduid zijn door 0' zijn de toegewezen taken.

In sommige gevallen kan het zijn dat er geen toewijzing mogelijk is:

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

Merk op dat taak 1 efficiënt kan gedaan worden door zowel arbeider a en c. Beide kunnen echter niet toegewezen worden aan dezelfde taak. Merk ook op dat niemand taak 3 efficiënt doet. Om dit te vermijden, herhalen we de bovestande procedure voor alle kolomen en kijken dan na of een toewijzing mogelijk is. In de meeste gevallen zal dit het resultaat geven, maar het is echter nog steeds mogelijk dat er geen toewijzing kan gemaakt worden. Dan moet de onsterstaande procedure gevolgd worden:

Probeer zoveel mogelijk taken toe te wijzen en doe dan het volgende (wijs taken toe in rijen 2, 3 en 4)

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

Markeer alle rijen die geen toewijzingen hebben (rij 1). Markeer vervolgens alle kolomen die een nul hebben in die rij (kolom 1). Markeer dan alle rijen die toewijzingen hebben in de gegeven kolom (rij 3). Markeer vervolgens alle kolomen die toewijzingen hebben in de gegeven rijen. Herhaal dit tot er een gesloten lus bekomen is.

×

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

Trek nu lijnen door alle gemarkeerde kolomen en ongemarkeerde rijen.

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

Merk op: omdat het hier onmogelijk is om een vertikale lijn te trekken, wordt een horizontale lijn gebuikt om de eerste kolom te schrappen.

Uit de elementen die overblijven zoekt men de laagste waarde. Trek deze waarde af van alle elementen die niet geschrapt zijn. Tel deze waarde bij de elementen die op de kruising van twee lijnen liggen. Laat de andere elemten onveranderd. Wijs nu de taken toe a.d.h.v. bovenstaande regels. Herhaal deze procedure totdat een toewijzing mogelijk is.