Hongaars algoritme: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
Regel 16:
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 <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.
0 a2' 0' a4' <br/>
b1' b2' b3' 0' <br/>
| |||