- Rutt
- Kortaste hittade
- Start
| Metod | Längd | Över kortaste | Steg |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
Handelsresandeproblemet
En handelsresande måste besöka varje stad en gång och sedan återvända hem. Vilken ordning gör resan kortast? Frågan är lätt att ställa men, när antalet städer växer, hopplös att besvara genom att pröva varje ordning: 30 städer ger redan omkring 4,4 × 10³⁰ rundresor. Strö ut städer på en karta eller klicka ut dina egna, och se snabba tumregler, smarta förbättringar och en exakt metod bygga sina rutter steg för steg – och hur nära de snabba metoderna kommer. Välj hur städerna ska placeras och hur många de ska vara, välj en metod och tryck på Lös för att se den bygga en rundresa steg för steg, eller på Ett steg för att gå ett drag i taget. Klicka på kartan för att lägga till en stad, eller klicka på en stad för att ta bort den. Jämför alla kör alla metoder på samma städer och visar hur långt var och en ligger från den kortaste rutt som hittats. Den röda staden är där resan börjar.
Hur det fungerar
- Välj en layout och antalet städer, eller klicka på kartan för att placera dina egna och klicka på en stad för att ta bort den.
- Välj en metod och tryck på Lös för att följa den steg för steg, eller på Ett steg för att gå ett drag i taget.
- Tryck på Jämför alla för att köra alla metoder på samma städer och läs av hur mycket varje rutt ligger över den kortaste som hittats.
Varför det är svårt
Med n städer finns det (n − 1)! / 2 olika rundresor, eftersom det inte spelar någon roll var du börjar eller åt vilket håll du åker. Det blir 12 för 5 städer, 181 440 för 10 och omkring 6 × 10¹⁶ för 20. Ingen metod är känd som hittar den kortaste resan för varje karta på en tid som bara växer som en potens av n; problemet är NP-svårt. Den bästa exakta metoden i den här appen, Held–Karps dynamiska programmering från 1962, behöver fortfarande omkring n² · 2ⁿ steg och är därför begränsad till 12 städer här.
Bra rutter snabbt
I praktiken hittas nästan kortaste rutter snabbt. Närmaste granne åker alltid till den närmaste obesökta staden och hamnar typiskt omkring 25 % över den bästa rutten. Billigaste insättning låter en slinga växa och lägger till den stad som förlänger den minst. 2-opt tar en godtycklig rutt och fortsätter att ersätta två kanter med två kortare, vilket tar bort varje korsning och oftast hamnar inom omkring 5 %. Simulerad glödgning gör slumpmässiga 2-opt-drag och accepterar, så länge den fortfarande är „het“, några drag som gör rutten längre, så att den kan klättra ur återvändsgränder innan den stabiliseras.
Ofta ställda frågor
Finns det en formel för den kortaste rutten?
Nej. Den kortaste rutten beror på de exakta positionerna för alla städer, och ingen känd metod hittar den för varje karta utan att i värsta fall kräva en arbetsmängd som växer exponentiellt. För några hundra eller tusen städer bevisar specialiserade exakta lösare som Concorde ändå optimala rutter genom att kombinera linjärprogrammering med smart beskärning, och den största instans som hittills lösts exakt har 85 900 punkter.
Varför tar 2-opt bort varje korsning?
Om två kanter i en rutt korsar varandra bildar de fyra städer som de förbinder en fyrhörning vars diagonaler är de två kanterna. Att byta ut dem mot två motstående sidor i fyrhörningen är alltid kortare enligt triangelolikheten och vänder på sträckan av rutten däremellan. 2-opt fortsätter att göra sådana byten tills inget hjälper längre, så den slutliga rutten korsar aldrig sig själv.
Vad är temperaturen i simulerad glödgning?
Den styr hur villig metoden är att acceptera ett drag som gör rutten längre. Ett drag som lägger till d till längden accepteras med sannolikheten e^(−d/T). Vid en hög temperatur T går nästan vad som helst, vilket låter rutten ta sig ur ett dåligt arrangemang; när T sjunker blir metoden girig och stabiliseras. Namnet kommer från att metall kyls långsamt så att atomerna hittar ett arrangemang med låg energi.
Varför är den exakta metoden begränsad till 12 städer?
Held–Karp lagrar den kortaste vägen för varje delmängd av städer och varje möjlig sista stad, vilket är omkring n · 2ⁿ tal, och fyller i vart och ett med n jämförelser. För 12 städer blir det några hundra tusen steg; för 25 städer skulle det bli miljarder. Det är ändå enormt mycket snabbare än att pröva alla (n − 1)! / 2 rutter: för 12 städer skulle det vara nästan 20 miljoner.
Skickas något till en server?
Nej. Städerna och alla fem metoder körs i din webbläsare. De städer du klickar ut sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor