Page 11 - Grafentheorie HS 5 Handelsreizigersprobleem

HS 5 Handelsreizigersprobleem

5.3.2 Het invoegingsalgoritme (heuristiek)

Het invoegingsalgoritme werkt volgens het principe van het toevoegen aan een gedeeltelijke route van
nieuwe bogen die nog niet in deze route zitten.

https://www.geogebra.org/m/mejgnjba

Het invoegingsalgoritme
Kies willekeurig 2 steden. De gedeeltelijke route is dan één boog tussen beide steden.
Indien de gedeeltelijke route nog niet alle knopen bevat voeg een knoop toe zodanig dat de toevoeging
een nieuwe gedeeltelijke kortste route oplevert met 3 knopen.
Herhaal deze werkwijze voor de overige knopen.

• Kies een boog (verbinding) van de graaf bijvoorbeeld de boog AC, start in knoop A.
Vanuit deze boog kunnen wij ofwel de knoop B ofwel de knoop G toevoegen.

Bij het toevoegen van de knoop B is de toename van de lengte van de route 12 + 8 – 10 = 10
Bij het toevoegen van de knoop G is de toename van de lengte van de route 12 + 9 – 10 = 11

Wij voegen B toe zodanig dat de nieuwe route ACB het kortst is.

• Vanuit de route ACB kunnen nu ofwel de knoop D ofwel de knoop G worden toegevoegd. t
e
n
.
o
l
e
h
t
a
m
.
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 10