SUMit Roostersoftware > Wekelijkse Noot > December 2002 > Handelsreiziger | English · Zoek... |
Handelsreiziger |
Maandag, 2 december 2002 | Oktober 2002 November 2002 Hobbel Tol View Wissel Januari 2003 Februari 2003 | |
Er bestaat geen perfecte oplossing voor het probleem van de rondreizende verkoper.
Wat is de kortst mogelijke route
|
Bekijk de routeplanner voor Nederland die via punten sorteert. | ||
Het probleem van de handelsreiziger is
NP-complete.
Er is één algoritme bekend dat de optimale oplossing bepaalt: met brute kracht alle mogelijkheden aflopen. Voor grotere problemen is dat ondoenlijk door de combinatorische explosie van het aantal mogelijkheden. Toch ziet u hierboven een Java applet die razendsnel een uitstekende oplossing zoekt, zelfs langs honderden of zelfs duizend punten. Hoe kan dat? De applet hierboven toont niet altijd de optimale oplossing, wel altijd eentje die op z'n minst uitstekend is. Soms een 10, meestal een 9,9!Het achterliggende geavanceerde algoritme is behoorlijk complex. Het heeft mij diverse sessies met de kikker gekost om het uit te denken. Het algoritme vraagt aardig wat rekenwerk, maar bepaalt toch razendsnel een uitstekende oplossing, een route met lage, of zelfs mimimale kosten. Toepassingen
|
|||
Nieuw op het web:
Turnvereniging ODIN, Amstelveen.
Proficiat Web designer Lassie. |