Hongaars algoritme
Het Hongaars algoritme is een combinatorisch optimalisatiealgoritme dat een toewijzingsprobleem oplost in een tijd van orde . De eerste versie, bekend als de Hongaarse methode, werd bedacht en gepubliceerd door Harold Kuhn in 1955. Deze versie werd bewerkt 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 bewerken
Zij gegeven arbeiders, taken en een -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 kosten.
Om te beginnen wordt het probleem uitgeschreven in een matrix:
1 2 3 4 a a1 a2 a3 a4 b b1 b2 b3 b4 c c1 c2 c3 c4 d d1 d2 d3 d4
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 als persoon a respectievelijk de taak 1, 2, 3, of 4 uitvoert. Analoog voor de andere elementen. 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 ai met i = 1, 2, 3 of 4 wordt gekozen. Deze waarde wordt afgetrokken van de andere elementen in die rij. Dit zorgt ervoor dat er minstens één nul in deze rij komt te staan. Men krijgt meerdere nullen als 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 kosten voor elke taak nul is. Dit is hier onder geïllustreerd.
1 2 3 4 a 0 a2' 0' a4' b b1' b2' b'3 0' c 0' c2' c3' c4' d 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:
1 2 3 4 a 0 a2' a3' a4' b b1' b2' b'3 0' c 0' c2' c3' c4' d 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 bovenstaande procedure voor alle kolommen 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 onderstaande procedure gevolgd worden:
Probeer zo veel mogelijk taken toe te wijzen en doe dan het volgende (wijs taken toe in rijen 2, 3 en 4)
1 2 3 4 a 0 a2' a3' a4' b b1' b2' b'3 0' c 0' c2' c3' c4' d d1' 0' d3' d4'
Markeer alle rijen die geen toewijzingen hebben (rij 1). Markeer vervolgens alle kolommen 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 kolommen die toewijzingen hebben in de gegeven rijen. Herhaal dit tot er een gesloten lus ontstaat.
× 1 2 3 4 a 0 a2' a3' a4' × b b1' b2' b'3 0' c 0' c2' c3' c4' × d d1' 0' d3' d4'
Trek nu lijnen door alle gemarkeerde kolommen en ongemarkeerde rijen. (In plaats van lijnen te trekken zijn de elementen in rood aangegeven.)
× 1 2 3 4 a 0 a2' a3' a4' × b b1' b2' b'3 0' c 0' c2' c3' c4' × d d1' 0' d3' d4'
Uit de overgebleven elementen 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 elementen onveranderd. Wijs nu de taken toe aan de hand van bovenstaande regels. Herhaal deze procedure totdat een toewijzing mogelijk is.