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.

0 &nbsp;&nbsp;&nbsp; a2' &nbsp; 0'&nbsp;&nbsp; a4' <br/>

b1' &nbsp; b2' &nbsp; b3' &nbsp; 0' <br/>

 

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)

d1' &nbsp; 0' &nbsp;&nbsp; d3'&nbsp; d4' <br/>

 

 

&times;

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

 

 

[[Categorie:Algoritme]]