Rutelængde
Korteste fundne
Trin
Mulige ruter
  • Rute
  • Korteste fundne
  • Start

Metode Længde Over korteste Trin
- - -
- - -
- - -
- - -
- - -

Mere om den handelsrejsendes problem

Den handelsrejsendes problem

En handelsrejsende skal besøge hver by én gang og vende hjem igen. Hvilken rækkefølge giver den korteste tur? Spørgsmålet er let at stille, men når antallet af byer vokser, er det håbløst at besvare ved at prøve alle rækkefølger: 30 byer giver allerede omkring 4,4 × 10³⁰ rundture. Strø byer ud på et kort, eller klik dine egne ind, og se hurtige tommelfingerregler, smarte forbedringer og én eksakt metode bygge deres ruter trin for trin – og se, hvor tæt de hurtige metoder kommer på. Vælg, hvordan byerne er placeret, og hvor mange der er, vælg en metode, og tryk på Løs for at se den bygge en rundtur trin for trin, eller på Ét trin for at gå ét træk ad gangen. Klik på kortet for at tilføje en by, eller klik på en by for at fjerne den. Sammenlign alle kører alle metoder på de samme byer og viser, hvor langt hver af dem er fra den korteste fundne rute. Den røde by er der, hvor turen starter.

Sådan virker det

  1. Vælg et layout og antallet af byer, eller klik på kortet for at placere dine egne, og klik på en by for at fjerne den.
  2. Vælg en metode, og tryk på Løs for at følge den trin for trin, eller på Ét trin for at gå ét træk ad gangen.
  3. Tryk på Sammenlign alle for at køre alle metoder på de samme byer, og aflæs, hvor meget hver rute ligger over den korteste fundne.

Hvorfor det er svært

Med n byer er der (n − 1)! / 2 forskellige rundture, fordi det er ligegyldigt, hvor du starter, og hvilken vej rundt du kører. Det er 12 for 5 byer, 181.440 for 10 og omkring 6 × 10¹⁶ for 20. Der kendes ingen metode, der finder den korteste tur for ethvert kort på en tid, der kun vokser som en potens af n; problemet er NP-hårdt. Den bedste eksakte metode i denne app, Held–Karps dynamiske programmering fra 1962, kræver stadig omkring n² · 2ⁿ trin og er derfor begrænset til 12 byer her.

Gode ruter hurtigt

I praksis findes næsten korteste ruter hurtigt. Nærmeste nabo kører altid til den nærmeste ubesøgte by og ender typisk omkring 25 % over den bedste rute. Billigste indsættelse lader en løkke vokse og tilføjer den by, der forlænger den mindst. 2-opt tager en vilkårlig rute og bliver ved med at erstatte to kanter med to kortere, hvilket fjerner alle krydsninger og som regel kommer inden for omkring 5 %. Simuleret udglødning laver tilfældige 2-opt-træk og accepterer, så længe den stadig er „varm“, nogle træk, der gør ruten længere, så den kan klatre ud af blindgyder, før den falder til ro.

Ofte stillede spørgsmål

Findes der en formel for den korteste rute?

Nej. Den korteste rute afhænger af de nøjagtige positioner af alle byerne, og ingen kendt metode finder den for ethvert kort uden i værste fald en arbejdsmængde, der vokser eksponentielt. For nogle hundrede eller tusind byer beviser specialiserede eksakte løsere som Concorde alligevel optimale ruter ved at kombinere lineær programmering med smart beskæring, og den største instans, der indtil videre er løst eksakt, har 85.900 punkter.

Hvorfor fjerner 2-opt alle krydsninger?

Hvis to kanter i en rute krydser hinanden, danner de fire byer, de forbinder, en firkant, hvis diagonaler er de to kanter. At bytte dem ud med to modstående sider i firkanten er altid kortere ifølge trekantsuligheden og vender strækningen af ruten imellem om. 2-opt bliver ved med at lave sådanne ombytninger, indtil ingen hjælper længere, så den endelige rute krydser aldrig sig selv.

Hvad er temperaturen i simuleret udglødning?

Den styrer, hvor villig metoden er til at acceptere et træk, der gør ruten længere. Et træk, der lægger d til længden, accepteres med sandsynligheden e^(−d/T). Ved en høj temperatur T går næsten alt, hvilket lader ruten slippe ud af en dårlig opstilling; når T falder, bliver metoden grådig og falder til ro. Navnet kommer fra at køle metal langsomt af, så dets atomer finder en opstilling med lav energi.

Hvorfor er den eksakte metode begrænset til 12 byer?

Held–Karp gemmer den korteste vej for hver delmængde af byer og hver mulig sidste by, hvilket er omkring n · 2ⁿ tal, og udfylder hvert af dem med n sammenligninger. For 12 byer er det nogle hundrede tusind trin; for 25 byer ville det være milliarder. Det er stadig enormt meget hurtigere end at prøve alle (n − 1)! / 2 ruter: For 12 byer ville det være næsten 20 millioner.

Bliver der sendt noget til en server?

Nej. Byerne og alle fem metoder kører i din browser. De byer, du klikker ind, bliver i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor