Hongaars algoritme: verschil tussen versies

Vervolgens passen we rijoperaties toe op deze matrix. De laagste van alle <math>a_i</math> met <math>i</math> 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.

 

 

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

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

 

 

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.

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

 

 

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 bekomen is.

 

 

 

Trek nu lijnen door alle gemarkeerde kolomen en ongemarkeerde rijen.

 

 

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