Handelsresandeproblemet förklarat
Ge en handelsresande en lista med städer och be om den kortaste resa som besöker var och en av dem en gång och återvänder hem. Vem som helst kan kontrollera en föreslagen rutt, och vem som helst kan förbättra en dålig rutt med blotta ögat, men ingen känner till en snabb metod som alltid hittar den bästa. Handelsresandeproblemet har blivit standardexemplet på ett svårt problem, och metoderna som uppfunnits för att angripa det planerar nu leveranser, borrar kretskort och sätter ihop genom.
Problemet
En rutt besöker varje stad exakt en gång och slutar där den började; dess längd är summan av avstånden längs vägen. Uppgiften är att hitta den kortaste rutten. I versionen här är avstånden raka linjer på en karta, så vägen från A till C är aldrig längre än vägen via B: detta är det metriska handelsresandeproblemet. Problemet diskuterades av matematikern Karl Menger omkring 1930, och namnet blev vanligt under de följande decennierna, när matematiker vid RAND Corporation tog upp det.
Explosionen av rutter
Lås startstaden. Det finns n − 1 val för nästa stad, n − 2 för den därefter och så vidare, och varje rutt kan köras i två riktningar, så det finns (n − 1)! / 2 rutter. För 10 städer är det 181 440, lätt för en dator. För 20 är det omkring 6 × 10¹⁶, och för 70 överstiger det antalet atomer i det observerbara universum. Snabbare datorer hjälper inte mycket: varje extra stad multiplicerar arbetet med ungefär n.
NP-svårt
År 1972 visade Richard Karp att frågan om huruvida en graf har en rundresa genom varje hörn, en hamiltoncykel, hör till en familj av NP-fullständiga problem som alla är lika svåra. Handelsresandeproblemet innehåller den frågan, så det är NP-svårt. En snabb metod för det skulle ge snabba metoder för tusentals andra problem inom schemaläggning, logistik och kryptografi. Huruvida en sådan metod finns är frågan P mot NP, ett av millennieproblemen.
En exakt metod: Held–Karp
År 1962 använde Michael Held och Richard Karp, och oberoende av dem Richard Bellman, dynamisk programmering. För varje mängd S av städer och varje stad j i S beräknas den kortaste väg som börjar i hemstaden, besöker exakt städerna i S och slutar i j. Varje värde följer av värdena för S utan j, så tabellen fylls i från små mängder till stora, och den kortaste rutten kommer fram i slutet. Det kräver omkring n² · 2ⁿ steg i stället för n!, vilket för 30 städer är skillnaden mellan minuter och universums ålder, men det växer fortfarande exponentiellt.
Snabba konstruktionsregler
Närmaste granne reser alltid till den närmaste staden som ännu inte besökts. Den är enkel och snabb, men tenderar att lämna några städer strandsatta som måste hämtas med långa omvägar på slutet, så dess rutter är typiskt omkring 25 % längre än den bästa. Insättningsmetoder håller i stället en sluten slinga och lägger till de återstående städerna en i taget där de kostar minst. År 1976 hittade Nicos Christofides en konstruktion som garanterat ger högst 1,5 gånger optimum på varje metrisk karta, en gräns som stod nästan oslagen i över fyrtio år.
Förbättra en rutt: 2-opt
Lokal sökning börjar från en godtycklig rutt och fortsätter att göra små ändringar som förkortar den. Det klassiska draget, 2-opt, tar bort två kanter och kopplar ihop de två delarna åt andra hållet, vilket vänder på sträckan mellan dem. När två kanter korsar varandra rätar detta drag ut korsningen och sparar längd, så en rutt som 2-opt inte kan förbättra korsar aldrig sig själv. På slumpmässiga kartor ligger 2-opt-rutter typiskt omkring 5 % över optimum. Starkare drag som byter tre kanter, eller Lins och Kernighans metod med variabelt djup från 1973, kommer ännu närmare.
Simulerad glödgning
Lokal sökning kan fastna i en rutt där varje enskilt drag gör den sämre, trots att det finns en mycket bättre rutt. Simulerad glödgning, som tillämpades på det här problemet av Scott Kirkpatrick, Daniel Gelatt och Mario Vecchi år 1983, lånar från metallurgin: den accepterar ett sämre drag med en sannolikhet som beror på en temperatur, hög i början och långsamt sänkt. Tidigt vandrar rutten fritt; i slutet accepteras bara förbättringar. Med tillräckligt långsam avkylning hittar den pålitligt mycket bra rutter.
Utforska det
Öppna demon av handelsresandeproblemet för att placera upp till 200 städer slumpmässigt, på en cirkel, i kluster, i ett rutnät eller var du än klickar. Se närmaste granne lämna sina sista städer strandsatta, se 2-opt reda ut varje korsning, följ temperaturen i simulerad glödgning medan den svalnar, och låt Held–Karp bevisa den kortaste rutten för upp till 12 städer. Jämför alla kör alla metoder på samma karta och visar hur mycket varje rutt ligger över den kortaste som hittats.
Ofta ställda frågor
Var används handelsresandeproblemet?
Överallt där något måste besöka många platser i en effektiv ordning: leverans- och insamlingsrutter, en borrs eller lasers bana över ett kretskort, ordningen i vilken ett teleskop observerar stjärnor, plockordrar i ett lager och, med andra avstånd, ordningen på fragment när en DNA-sekvens sätts ihop.
Vilket är det största problem som någonsin lösts exakt?
År 1954 bevisade George Dantzig, Ray Fulkerson och Selmer Johnson den kortaste rutten genom 49 städer i USA. År 2006 bevisade lösaren Concorde av David Applegate, Robert Bixby, Vašek Chvátal och William Cook den optimala rutten genom 85 900 punkter från en chipdesign, efter flera års datortid.
Är den kortaste rutten alltid fri från korsningar?
Ja, på en plan karta med fågelvägsavstånd. Om två kanter korsade varandra skulle rutten bli kortare om man bytte ut dem mot två sidor i den fyrhörning de bildar, så en rutt med korsningar kan inte vara den kortaste.
Ger heuristikerna samma rutt varje gång?
Närmaste granne, billigaste insättning och 2-opt, så som de används här, är deterministiska: på samma städer ger de samma rutt. Simulerad glödgning börjar från en slumpmässig rutt och gör slumpmässiga drag, så två körningar kan sluta med olika rutter, oftast av nästan samma längd.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna demon av handelsresandeproblemet