Hoe om die Hongaarse algoritme te gebruik

Die Hongaarse algoritme laat die "minimum gelykheid" toe. Dit kan gebruik word in verskeie gevalle waar daar verskeie kostes vir `n groep aktiwiteite is en elke aktiwiteit moet deur `n ander persoon gedoen word om die minimum koste te vind om al die aktiwiteite te voltooi.

conținut

Stappe
Dinge
Dinge wat jy nodig het

stappe

Rangskik u inligting in `n matriks met die "mense" aan die linkerkant en die "aktiwiteite" aan die bokant, met die koste vir elke paar in die middel.

Maak seker dat die matriks vierkantig is met kolomme en valse rye as u dit nodig sien. Konvensioneel is elke element in die ry / kolom dieselfde as die grootste getal in die matriks.

Verminder die rye deur die minimum waarde van elke ry vir die ry af te trek.

Verminder die kolomme deur die minimum waarde van elke kolom vir daardie kolom af te trek.

Bedek die nul elemente met so min lyne as moontlik. (As die aantal lyne gelyk is aan die aantal rye, gaan dan na stap 9).

Voeg die minimum ontdek items by elke item wat gedek word. As `n item twee keer gedek is, voeg die minimum element twee keer by.

Trek die minimum element van elke element in die matriks af.

Dit dek weer die elemente van nul. As die aantal lyne wat die nul elemente dek, nie gelyk is aan die aantal rye nie, gaan terug na stap 6.

Kies die paartjie deur `n stel nulle te kies, sodat elke ry of kolom slegs een gekies het.

Pas die paar toe op die oorspronklike matriks en gooi die valse rye weg. Dit sal wys wie die aktiwiteit moet doen, en die koste sal jou die minimum totale koste gee