Routelengte
Kortste gevonden
Stappen
Mogelijke routes
  • Route
  • Kortste gevonden
  • Start

Methode Lengte Boven kortste Stappen
- - -
- - -
- - -
- - -
- - -

Meer over het handelsreizigersprobleem

Handelsreizigersprobleem

Een handelsreiziger moet elke stad één keer bezoeken en weer naar huis terugkeren. In welke volgorde is de reis het kortst? De vraag is makkelijk te stellen, maar naarmate het aantal steden groeit, is ze hopeloos te beantwoorden door elke volgorde te proberen: 30 steden geven al ongeveer 4,4 × 10³⁰ rondreizen. Strooi steden over een kaart of klik je eigen steden aan, en kijk hoe snelle vuistregels, slimme verbeteringen en één exacte methode stap voor stap hun routes opbouwen, en hoe dicht de snelle methoden in de buurt komen. Kies hoe de steden verdeeld zijn en hoeveel het er zijn, kies een methode en druk op Oplossen om te zien hoe die stap voor stap een rondreis opbouwt, of op Stap om één zet tegelijk te doen. Klik op de kaart om een stad toe te voegen, of klik op een stad om die te verwijderen. Alles vergelijken laat elke methode op dezelfde steden lopen en toont hoe ver elke methode van de kortste gevonden route af zit. De rode stad is het vertrekpunt van de reis.

Hoe het werkt

  1. Kies een indeling en het aantal steden, of klik op de kaart om je eigen steden te plaatsen en klik op een stad om die te verwijderen.
  2. Kies een methode en druk op Oplossen om die stap voor stap te volgen, of op Stap om één zet tegelijk te doen.
  3. Druk op Alles vergelijken om elke methode op dezelfde steden te laten lopen en lees af hoeveel elke route boven de kortste gevonden route ligt.

Waarom het moeilijk is

Met n steden zijn er (n − 1)! / 2 verschillende rondreizen, omdat het niet uitmaakt waar je begint of in welke richting je rijdt. Dat zijn er 12 voor 5 steden, 181.440 voor 10 en ongeveer 6 × 10¹⁶ voor 20. Er is geen methode bekend die voor elke kaart de kortste reis vindt in een tijd die slechts groeit als een macht van n; het probleem is NP-moeilijk. De beste exacte methode in deze app, dynamisch programmeren volgens Held–Karp uit 1962, heeft nog altijd ongeveer n² · 2ⁿ stappen nodig en is hier daarom beperkt tot 12 steden.

Snel goede routes

In de praktijk worden bijna kortste routes snel gevonden. Dichtstbijzijnde buur rijdt altijd naar de dichtstbijzijnde nog niet bezochte stad en eindigt doorgaans ongeveer 25% boven de beste route. Goedkoopste invoeging laat een lus groeien en voegt telkens de stad toe die haar het minst verlengt. 2-opt neemt een willekeurige route en vervangt steeds twee verbindingen door twee kortere, wat elke kruising verwijdert en meestal tot op ongeveer 5% komt. Simulated annealing doet willekeurige 2-opt-zetten en accepteert, zolang het nog „heet“ is, ook enkele zetten die de route langer maken, zodat het uit doodlopende situaties kan klimmen voordat het tot rust komt.

Veelgestelde vragen

Bestaat er een formule voor de kortste route?

Nee. De kortste route hangt af van de precieze posities van alle steden, en geen enkele bekende methode vindt haar voor elke kaart zonder, in het slechtste geval, een hoeveelheid werk die exponentieel groeit. Voor een paar honderd of duizend steden bewijzen gespecialiseerde exacte solvers zoals Concorde toch optimale routes door lineair programmeren te combineren met slim snoeien, en de grootste instantie die tot nu toe exact is opgelost, telt 85.900 punten.

Waarom verwijdert 2-opt elke kruising?

Als twee verbindingen van een route elkaar kruisen, vormen de vier steden die ze verbinden een vierhoek waarvan de diagonalen die twee verbindingen zijn. Ze vervangen door twee tegenover elkaar liggende zijden van de vierhoek is volgens de driehoeksongelijkheid altijd korter, en keert het stuk route ertussen om. 2-opt blijft zulke verwisselingen doen tot geen enkele meer helpt, dus de uiteindelijke route kruist zichzelf nooit.

Wat is de temperatuur bij simulated annealing?

Die bepaalt hoe bereid de methode is een zet te accepteren die de route langer maakt. Een zet die d aan de lengte toevoegt, wordt geaccepteerd met kans e^(−d/T). Bij een hoge temperatuur T kan bijna alles, waardoor de route aan een slechte indeling kan ontsnappen; naarmate T daalt, wordt de methode gulzig en komt ze tot rust. De naam komt van het langzaam afkoelen van metaal, zodat de atomen een rangschikking met lage energie vinden.

Waarom is de exacte methode beperkt tot 12 steden?

Held–Karp slaat het kortste pad op voor elke deelverzameling van steden en elke mogelijke laatste stad, wat ongeveer n · 2ⁿ getallen zijn, en vult elk daarvan in met n vergelijkingen. Voor 12 steden zijn dat een paar honderdduizend stappen; voor 25 steden zouden het er miljarden zijn. Het is nog altijd enorm veel sneller dan alle (n − 1)! / 2 routes proberen: voor 12 steden zouden dat er bijna 20 miljoen zijn.

Wordt er iets naar een server gestuurd?

Nee. De steden en alle vijf methoden draaien in je browser. De steden die je aanklikt, blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor