Page 3 - Grafentheorie HS 5 Handelsreizigersprobleem

HS 5 Handelsreizigersprobleem

5.1.2 Moeilijkheden bij het oplossen van het handelsreizigersprobleem

De vraagstelling van dit probleem is erg eenvoudig te omschrijven. Iedereen begrijpt de vraag.
De meeste wiskundigen vinden dit juist een gemakkelijk probleem. Immers, hoe groot het aantal steden
ook is, het aantal mogelijke oplossingen (routes) is een eindig aantal.
Elke route heeft een bepaalde lengte en onder die eindig aantal routes is er een kortste route.

Je zou alle routes één voor één kunnen bekijken. Het vinden van de kortste route voor een groot aantal
steden door alle mogelijke routes uit te proberen, het zogenaamde “brute kracht algoritme” zal
bijzonder veel tijd kosten en al vrij snel zelfs de rekencapaciteit van de snelste supercomputer
overtreffen.
De grote moeilijkheid van het handelsreizigersprobleem is het bedenken van een optimaal algoritme
waarmee men, voor een gegeven aantal steden , binnen een redelijke tijd een kortste route vindt.
Tot op heden bestaat er voor het handelsreizigersprobleem geen snel en efficiënt algoritme dat altijd de
kortste route vindt. Ten minste…tot op heden heeft geen enkele wiskundige dergelijk algoritme
gevonden. Er bestaan uiteraard wel algoritmen die de kortste afstand benaderen (heuristieken).
Dit betekent dat er keuzes zullen moeten gemaakt worden:

• Indien je met 100% zekerheid de kortste route wil bepalen, dan zal dit (immens) veel tijd kosten.
• Indien je hiervoor niet voldoende tijd hebt , dan zal jouw gevonden route niet noodzakelijk de
kortste zijn.
5.1.3 Aantal Hamiltoncykels

Om het opstellen van de formule voor het berekenen van het aantal Hamiltoncykels in een graaf
veronderstellen wij dat:

• Het handelsreizigersprobleem wordt beschreven met een volledige graaf.
Met andere woorden, ALLE steden zijn onderling verbonden.

• De afstanden zijn symmetrisch. Dit betekent dat wij geen onderscheid maken tussen route
ABCDE en EDCBA.

Voorbeeld:
Wij bepalen bij een eenvoudige volledige graaf met 4 knopen het aantal mogelijke Hamiltoncykels met
als startknoop A.

t
e
n
.
o
l
e
h
t
a
m
.
w
w
ABCDA, ABDCA, ACDBA, ACBDA, ADCBA, ADBCA
w
6 mogelijkheden, 3 verschillende cykels omwille van symmetrie.

© 2021 Ivan De Winne ivan@mathelo.net 2