© h.hofstede (h.hofstede@hogeland.nl)

De Handelsreiziger
       
Een handelsreiziger moet een aantal steden bezoeken en dan terugkeren naar zijn startpunt. De reistijden tussen de steden zijn gegeven. De vraag is:  Hoe speelt hij dat in een zo kort mogelijke tijd klaar?

Wiskundig herkennen wij deze vraag natuurlijk direct:
       

" Zoek een minimum-gewichts  Hamilton-cykel in een gewogen volledige graaf"
       
Zo'n cykel zullen we vanaf nu een optimale cykel noemen.
En nou komt het:  Daar is nog geen waterdicht algoritme voor bekend!!!
Gelukkig zijn er wel een paar algoritmen bekend om een "redelijk goede" route te vinden. De meest gebruikte is de volgende:
       
Maak er gewoon eentje, en ga die dan verbeteren.
       
Hier zie je een makkelijk te proberen mogelijkheid:
       

       
Stel dat je een Hamiltoncykel (S = start) zoals links hebt gevonden.
Kies dan twee knopen A en M uit die cykel,  waarvan B en N de volgenden in de cykel zijn.
Dan kun je de cykel veranderen zoals rechts is gedaan.
Als nu geldt dat    AM + BN <  AB + MN  dan heb je een betere cykel gevonden, immers de eerste twee zijn toegevoegd, en de laatste twee zijn weggelaten.
Dat is makkelijk (door een computerprogramma) voor alle koppeltjes A, M te testen. En daarna kun je met die nieuwe verbeterde cykel gewoon het hele verhaal nog een keer gaan proberen, en dan nog een keer, en dan nog een keer....

Hier zie je hoe het werkt. De begincykel is willekeurig gekozen,  ernaast staat steeds welke koppeltjes AM-BN er geprobeerd zijn:
       

       
Ga zelf maar na dat er nu geen verbetering meer is.....  
       
       

© h.hofstede (h.hofstede@hogeland.nl)