Den handelsrejsendes problem forklaret

Giv en handelsrejsende en liste over byer, og spørg efter den korteste tur, der besøger hver af dem én gang og vender hjem igen. Alle kan kontrollere en foreslået rute, og alle kan forbedre en dårlig rute på øjemål, men ingen kender en hurtig metode, der altid finder den bedste. Den handelsrejsendes problem er blevet standardeksemplet på et svært problem, og de metoder, der er opfundet til at angribe det, planlægger nu leverancer, borer printplader og samler genomer.

Et kort med byer forbundet af en lukket rute, med startbyen markeret og en svag, kortere rute nedenunder
Et kort med byer forbundet af en lukket rute, med startbyen markeret og en svag, kortere rute nedenunder

Problemet

En rute besøger hver by nøjagtigt én gang og slutter, hvor den startede; dens længde er summen af afstandene undervejs. Opgaven er at finde den korteste rute. I versionen her er afstandene rette linjer på et kort, så turen fra A til C er aldrig længere end turen via B: Det er den metriske udgave af den handelsrejsendes problem. Gåden blev diskuteret af matematikeren Karl Menger omkring 1930, og navnet blev almindeligt i de følgende årtier, da matematikere ved RAND Corporation tog det op.

Karl Menger i 1970. Han behandlede handelsrejsende-problemet omkring 1930.
Karl Menger i 1970. Han behandlede handelsrejsende-problemet omkring 1930.

Eksplosionen af ruter

Fastlæg startbyen. Der er n − 1 valg for den næste by, n − 2 for den efter, og så videre, og hver rute kan køres i to retninger, så der er (n − 1)! / 2 ruter. For 10 byer er det 181.440, let for en computer. For 20 er det omkring 6 × 10¹⁶, og for 70 overstiger det antallet af atomer i det observerbare univers. Hurtigere computere hjælper ikke meget: Hver ekstra by ganger arbejdet med omkring n.

NP-hård

I 1972 viste Richard Karp, at spørgsmålet om, hvorvidt en graf har en rundtur gennem alle knuder, en hamiltonkreds, tilhører en familie af NP-komplette problemer, der alle er lige svære. Den handelsrejsendes problem indeholder det spørgsmål, så det er NP-hårdt. En hurtig metode til det ville give hurtige metoder til tusindvis af andre problemer inden for planlægning, logistik og kryptografi. Om en sådan metode findes, er spørgsmålet P versus NP, et af Millennium Prize-problemerne.

En eksakt metode: Held–Karp

I 1962 brugte Michael Held og Richard Karp, og uafhængigt af dem Richard Bellman, dynamisk programmering. For hver mængde S af byer og hver by j i S beregnes den korteste vej, der starter i hjembyen, besøger nøjagtigt byerne i S og slutter i j. Hver værdi følger af værdierne for S uden j, så tabellen udfyldes fra små mængder til store, og den korteste rute kommer ud til sidst. Det kræver omkring n² · 2ⁿ trin i stedet for n!, hvilket for 30 byer er forskellen mellem minutter og universets alder, men det vokser stadig eksponentielt.

Richard Bellman i 1962, fotograferet af Alfred Eisenstaedt. Han gav dynamisk programmering navn i begyndelsen af 1950’erne, mens han arbejdede hos RAND Corporation.
Richard Bellman i 1962, fotograferet af Alfred Eisenstaedt. Han gav dynamisk programmering navn i begyndelsen af 1950’erne, mens han arbejdede hos RAND Corporation.

Hurtige konstruktionsregler

Nærmeste nabo rejser altid til den nærmeste by, der endnu ikke er besøgt. Den er enkel og hurtig, men har en tendens til at efterlade nogle få byer, som må samles op med lange omveje til sidst, så dens ruter typisk er omkring 25 % længere end den bedste. Indsættelsesmetoder holder i stedet en lukket løkke og tilføjer de resterende byer én ad gangen der, hvor de koster mindst. I 1976 fandt Nicos Christofides en konstruktion, der garanteret giver højst 1,5 gange optimum på ethvert metrisk kort, en grænse, der stod næsten uslået i over fyrre år.

Forbedring af en rute: 2-opt

Lokal søgning starter fra en vilkårlig rute og bliver ved med at lave små ændringer, der gør den kortere. Det klassiske træk, 2-opt, fjerner to kanter og forbinder de to stykker den anden vej igen, hvilket vender strækningen mellem dem om. Når to kanter krydser hinanden, fjerner dette træk krydsningen og sparer længde, så en rute, som 2-opt ikke kan forbedre, krydser aldrig sig selv. På tilfældige kort ligger 2-opt-ruter typisk omkring 5 % over optimum. Stærkere træk, der bytter tre kanter, eller Lin og Kernighans metode med variabel dybde fra 1973, kommer endnu tættere på.

Simuleret udglødning

Lokal søgning kan sidde fast i en rute, hvor hvert enkelt træk gør den dårligere, selv om der findes en meget bedre rute. Simuleret udglødning, som Scott Kirkpatrick, Daniel Gelatt og Mario Vecchi anvendte på dette problem i 1983, låner fra metallurgien: Den accepterer et dårligere træk med en sandsynlighed, der afhænger af en temperatur, som er høj i starten og langsomt sænkes. Tidligt vandrer ruten frit; til sidst accepteres kun forbedringer. Med langsom nok afkøling finder den pålideligt meget gode ruter.

Udforsk det

Åbn demoen af den handelsrejsendes problem for at placere op til 200 byer tilfældigt, på en cirkel, i klynger, i et gitter eller hvor du klikker. Se nærmeste nabo efterlade sine sidste byer, se 2-opt rede alle krydsninger ud, følg temperaturen i simuleret udglødning, mens den køler af, og lad Held–Karp bevise den korteste rute for op til 12 byer. Sammenlign alle kører alle metoder på det samme kort og viser, hvor meget hver rute ligger over den korteste fundne.

Ofte stillede spørgsmål

Hvor bruges den handelsrejsendes problem?

Overalt, hvor noget skal besøge mange steder i en effektiv rækkefølge: leverings- og indsamlingsruter, en bors eller lasers bane hen over en printplade, rækkefølgen, hvori et teleskop observerer stjerner, plukkeordrer på et lager og, med andre afstande, rækkefølgen af fragmenter, når en DNA-sekvens samles.

Hvad er det største problem, der nogensinde er løst eksakt?

I 1954 beviste George Dantzig, Ray Fulkerson og Selmer Johnson den korteste rute gennem 49 byer i USA. I 2006 beviste løseren Concorde af David Applegate, Robert Bixby, Vašek Chvátal og William Cook den optimale rute gennem 85.900 punkter fra et chipdesign efter flere års computertid.

Er den korteste rute altid fri for krydsninger?

Ja, på et fladt kort med afstande i lige linje. Hvis to kanter krydsede hinanden, ville det at bytte dem ud med to sider af den firkant, de danner, gøre ruten kortere, så en rute med krydsninger kan ikke være den korteste.

Giver heuristikkerne den samme rute hver gang?

Nærmeste nabo, billigste indsættelse og 2-opt, som de bruges her, er deterministiske: På de samme byer giver de den samme rute. Simuleret udglødning starter fra en tilfældig rute og laver tilfældige træk, så to kørsler kan ende med forskellige ruter, som regel af næsten samme længde.

Er du klar til at prøve?

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

Åbn demoen af den handelsrejsendes problem