Page 9 - Grafentheorie HS 5 Handelsreizigersprobleem

HS 5 Handelsreizigersprobleem

5.3 Benaderingsalgoritmen voor het handelsreizigersprobleem

5.3.1 Het beste-buur algoritme (heuristiek)

Gegeven is een (gewogen) graaf waarbij aan de bogen verbindingen een getal wordt toegekend.
Dit getal stelt niet noodzakelijk de werkelijke (Euclidische) afstand in het vlak maar kan ook weergeven
hoeveel tijd men nodig heeft om van de ene knoop naar een andere knoop te reizen.

Onderstaande afbeeldingen zijn twee voorstellingen van dezelfde graaf!

Het beste-buur-algoritme
Dit is een erg eenvoudige en snelle methode voor het vinden van “een” korte route, die echter niet
altijd de kortste route geeft als resultaat werkt als volgt:

• Kies een willekeurige knoop (stad) naar keuze.
• Ga naar de dichtstbijzijnde knoop (stad) die je nog niet eerder bezocht hebt.

• Herhaal deze werkwijze tot alle knopen (steden) bezocht zijn en keer vanuit de laatste knoop
terug naar de beginknoop.
Wij passen deze werkwijze toe op dit voorbeeld

• Kies als beginknoop A. Ga naar de dichtstbijzijnde knoop (die je nog niet bezocht hebt) E.

t
e
n
.
o
• Ga vanuit E naar de dichtstbijzijnde knoop D l
e
h
t
a
m
.
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 8