@.Sadye leuk om te zien dat je hier ook interesse voor hebt
Correct. Met het balanced assignment algoritme minimaliseer je het verschil tussen de maximale en minimale loopafstand. Hierdoor zal de variatie vaak ook kleiner worden.
Er zijn wel voorbeelden te bedenken waarbij de standaarddeviatie groter wordt, terwijl het verschil tussen maximale en minimale loopafstand kleiner wordt:
x1 = {1, 30, 60, 100}; x1
standaarddeviatie = 42,35; verschil x1
max en x1
min = 100 - 1 = 99
x2 = {1, 2, 3, 99}; x2
standaarddeviatie = 48,51; verschil x2
max en x2
min = 99 - 1 = 98
In dit geval is de spreiding groter bij een kleiner verschil tussen maximale en minimale loopafstand, echter zal in de praktijk verreweg het vaakst ook de spreiding mee afnemen.
Dat maakt dus het balanced assignment algoritme een mooi methode om het verschil in loopafstanden te verkleinen.
Het Hongaars algoritme is een mooie oplossing als je wilt dat alle je troepen totaal gezien zo kort mogelijk onderweg zijn en dus ook zo snel mogelijk weer terug zijn. Het kan uiteraard zo zijn dat een aantal van je troepen ontzettend lang onderweg zijn (noem ik even uitschieters), maar totaal gezien is het de snelste toewijzing (assignment). Nuttig als je zo snel mogelijk weer opnieuw wilt gaan aanvallen.
Het bottleneck assignment algoritme vindt juist de toewijzing tussen aanvalsdorpen en doelen waarbij de maximale loopafstand zo klein mogelijk is.
Dan zullen dus de uitschieters waar ik het net over had, zo klein mogelijk zijn. Echter kan daardoor de totale looptijd wel toenemen.
Het bottleneck assignment algoritme maakt gebruik van het Hongaars algoritme om een optimale toewijzing te vinden.
De uitkomst van het bottleneck assignment algoritme is uitgangspunt voor het balanced assignment algoritme. De toewijzing waarbij de grootste loopafstand zo klein mogelijk gemaakt is, zal namelijk de eerst mogelijke toewijzing zijn waarbij het verschil tussen maximale en minimale loopafstand geminimaliseerd is. Vervolgens wordt op efficiënte wijze gezocht naar andere toewijzingen waarbij dat verschil kleiner is (wat ik nu bedoel wordt dus in
dit boek beschreven op pagina 196).
Kort samengevat:
- Het Hongaars algoritme is ideaal om de totale loopafstand te minimaliseren (handig om, over het algemeen, je troepen zo snel mogelijk aan te laten komen en weer thuis te hebben wanneer ze de aanval overleven);
- Het bottleneck assignment algoritme minimaliseert de grootste loopafstand (handig om eventuele uitschieters in loopafstanden zo klein mogelijk te houden). Dit algoritme maakt gebruik van het Hongaars algoritme;
- Het balanced assignment algoritme is handig om het verschil in looptijden zo klein mogelijk te maken (handig om je aanvallen zo gelijktijdig mogelijk te laten aankomen als je ze op 1 moment verstuurt).
Alle 3 de algoritmes kunnen dus nuttig zijn om toe te passen.
Nummer 2 en 3 maken gebruik van de eerdere algoritmes (zoals je dat zelf ook al had samengevat).
Om ten slotte nog even terug te komen op je vraag naar de benodigde rekentijd:
Op mijn laptop (
Intel(R) Core(TM) i7-6500U CPU @ 2.50GHz, 2601 MHz, 2 core('s), 4 logische processor(s) en 8GB RAM) duurt het Hongaars algoritme op een 1000x1000 matrix die waardes bevat van 1 tot 500, ongeveer 0,12 seconden.
Een matrix van 5000x5000 met waardes van 1 tot 500 duurt ongeveer 2,16 seconden.
Ik gebruik daarbij wel zeer efficiënte code (niet zelf geschreven, R code die
hier op pagina 58+59 gedocumenteerd is. Het gaat om de functie 'solve_LSAP', LSAP staat voor Lineair Sum Assignment Problem wat dus door het Hongaars algoritme wordt opgelost).
Dit lijken mij nog zeer acceptabele tijden. Echter zouden de andere algoritmes al snel een veelvoud langer duren.
Een mogelijke oplossing om rekentijden dan toch nog acceptabel te houden is het afronden op tien-, twintig of vijftigtallen etc (afhankelijk van de waardes die de matrix bevat).
Ik hoop dat het hier wat duidelijker van is geworden
