Page 5 - Grafentheorie HS 5 Handelsreizigersprobleem

P. 5

HS 5 Handelsreizigersprobleem

Het aantal mogelijkheden neemt zeer snel toe.
Aantal hoofdsteden Aantal mogelijkheden
n
6 5.4.3.2.1 = 120

7 6.5.4.3.2.1 = 720
8 7.6.5.4.3.2.1 = 5040

9 8.7.6.5.4.3.2.1 = 40320
10 9.8.7.6.5.4.3.2.1 = 362880

11 10. 9.8.7.6.5.4.3.2.1 = 3628800
20 …. = 121645100408832000

50 …. =608281864034267560872252163321295376887552831379210240000000000
100 9.3326215443944152681699238856266700490715968264381621468592 × 10^157

Veralgemening van de formule voor n steden.

Formule (n-1).(n-2).(n-3)…. 3.2.1
Dergelijke formule noteert men korter als (n-1)!

Het uitroepteken staat voor het begrip faculteit in de wiskunde, dit is het product van (n-1)
opeenvolgende natuurlijke getallen.

Indien men om symmetrieredenen geen onderscheid maakt tussen route ABCDEF en FEDCBA dan
worden de aantallen gehalveerd en wordt de formule (n-1)!/2
Op zoek naar de kortste reisroute

De vraagstelling van dit handelsreizigers probleem is erg eenvoudig. Het is ook vrij gemakkelijk om voor
een klein aantal steden alle mogelijke routes te berekenen en hiermee de lengte van elke route te
berekenen en zodoende de kortste route te vinden.
Voor vijf steden zou men dan van alle 24 mogelijke routes de afstand kunnen berekenen en hiermee de
kunnen route bepalen. Dit is nog haalbaar indien men over voldoende geduld en tijd beschikt.

t
e
n
.
o
De rechtstreekse manier om dit op te lossen door gebruik te maken van snelle computers wordt al snel l e
onmogelijk voor meer dan 25 steden aangezien het aantal mogelijkheden zeer groot wordt. h
t
Omdat de kortste route bij het handelsreizigersprobleem zo moeilijk exact te berekenen is, werken veel a
informatici tegenwoordig met computerprogramma’s die benaderingen van de route maken. Daarmee m
.
heb je niet de ideale route, maar het verschil met die route is vaak erg klein. In de praktijk zijn de w
benaderingen daarom heel goed te gebruiken. w
Opmerking w
Een benaderingslogaritme noemt men ook een heuristiek.

1 2 3 4 5 6 7 8 9 10