Hoe het Hongaarse algoritme te gebruiken

Het Hongaarse algoritme maakt het mogelijk om de "minimale gelijkheid" te vinden. Dit kan worden gebruikt in verschillende gevallen waarbij er meerdere kosten zijn voor een groep activiteiten en elke activiteit moet worden gedaan door een andere persoon om de minimumkosten te vinden om alle activiteiten te voltooien.

Inhoud

Stappen
Spul
Dingen die je nodig hebt

stappen

Plaats uw informatie in een matrix met de "mensen" aan de linkerkant en de "activiteiten" bovenaan, met de kosten voor elk paar in het midden.

Zorg ervoor dat de matrix vierkant is met kolommen en valse rijen als u het nodig vindt. Conventioneel is elk element in de rij / kolom hetzelfde als het grootste getal in de matrix.

Verklein de rijen door de minimumwaarde van elke rij voor die rij af te trekken.

Verklein de kolommen door de minimumwaarde van elke kolom voor die kolom in te korten.

Bedek de nulelementen met zo min mogelijk regels. (Als het aantal regels gelijk is aan het aantal rijen, ga dan naar stap 9).

Voeg de minimaal ontdekte items toe aan elk bestreken item. Als een item twee keer is afgedekt, voegt u het minimale element er twee keer aan toe.

Trek het minimumelement van elk element in de matrix af.

Het dekt opnieuw de elementen van nul. Als het aantal lijnen dat de nulelementen bedekt niet gelijk is aan het aantal rijen, gaat u terug naar stap 6.

Selecteer het paar door een reeks nullen te kiezen, zodat elke rij of kolom er maar één heeft geselecteerd.

Pas het paar toe op de originele matrix en negeer de valse rijen. Dit laat zien wie welke activiteit moet doen, en het optellen van de kosten levert u de minimale totale kosten op

spul

Als u het maximum wilt vinden in plaats van het minimum, vermenigvuldigt u elk getal in stap 1 met -1 en volgt u vervolgens de stappen zoals ze zijn geschreven.

Dingen die je nodig hebt

papier
Potlood / pen

Delen op sociale netwerken:

Verwant