Problema comis-voiajorului explicată

Dați unui comis-voiajor o listă de orașe și cereți-i cea mai scurtă călătorie care vizitează fiecare oraș o dată și se întoarce acasă. Oricine poate verifica un traseu propus și oricine poate îmbunătăți din ochi unul prost, dar nimeni nu cunoaște o metodă rapidă care să-l găsească întotdeauna pe cel mai bun. Problema comis-voiajorului a devenit exemplul standard de problemă dificilă, iar metodele inventate pentru a o aborda planifică acum livrări, găuresc plăci de circuite și asamblează genomuri.

O hartă cu orașe unite printr-un traseu închis, cu orașul de plecare marcat și un traseu mai scurt, estompat, dedesubt
O hartă cu orașe unite printr-un traseu închis, cu orașul de plecare marcat și un traseu mai scurt, estompat, dedesubt

Problema

Un traseu vizitează fiecare oraș exact o dată și se termină acolo unde a început; lungimea lui este suma distanțelor parcurse. Sarcina este găsirea celui mai scurt traseu. În versiunea de aici, distanțele sunt linii drepte pe o hartă, deci drumul de la A la C nu este niciodată mai lung decât cel prin B: aceasta este problema metrică a comis-voiajorului. Problema a fost discutată de matematicianul Karl Menger în jurul anului 1930, iar numele s-a răspândit în deceniile următoare, când matematicienii de la RAND Corporation au preluat-o.

Karl Menger în 1970. A discutat problema comis-voiajorului în jurul anului 1930.
Karl Menger în 1970. A discutat problema comis-voiajorului în jurul anului 1930.

Explozia traseelor

Fixați orașul de plecare. Există n − 1 variante pentru următorul oraș, n − 2 pentru cel de după și așa mai departe, iar fiecare traseu poate fi parcurs în două sensuri, deci există (n − 1)! / 2 trasee. Pentru 10 orașe, acestea sunt 181.440, ușor pentru un calculator. Pentru 20 sunt aproximativ 6 × 10¹⁶, iar pentru 70 depășesc numărul atomilor din universul observabil. Calculatoarele mai rapide nu ajută prea mult: fiecare oraș în plus înmulțește munca cu aproximativ n.

NP-dificilă

În 1972, Richard Karp a arătat că întrebarea dacă un graf are un traseu închis prin fiecare vârf, un ciclu hamiltonian, face parte dintr-o familie de probleme NP-complete, toate la fel de dificile. Problema comis-voiajorului o conține, deci este NP-dificilă. O metodă rapidă pentru ea ar oferi metode rapide pentru mii de alte probleme din planificare, logistică și criptografie. Dacă o astfel de metodă există este întrebarea P versus NP, una dintre Problemele Mileniului.

O metodă exactă: Held–Karp

În 1962, Michael Held și Richard Karp și, independent de ei, Richard Bellman au folosit programarea dinamică. Pentru fiecare mulțime S de orașe și fiecare oraș j din S, se calculează cel mai scurt drum care pornește din orașul de origine, vizitează exact orașele din S și se termină în j. Fiecare valoare rezultă din valorile pentru S fără j, deci tabelul se completează de la mulțimi mici la mulțimi mari, iar la final rezultă cel mai scurt traseu. Sunt necesari aproximativ n² · 2ⁿ pași în loc de n!, ceea ce pentru 30 de orașe înseamnă diferența dintre minute și vârsta universului, dar numărul lor crește totuși exponențial.

Richard Bellman în 1962, fotografiat de Alfred Eisenstaedt. A dat numele programării dinamice la începutul anilor 1950, pe când lucra la RAND Corporation.
Richard Bellman în 1962, fotografiat de Alfred Eisenstaedt. A dat numele programării dinamice la începutul anilor 1950, pe când lucra la RAND Corporation.

Reguli rapide de construcție

Cel mai apropiat vecin merge mereu la cel mai apropiat oraș încă nevizitat. Este simplu și rapid, dar tinde să lase izolate câteva orașe care trebuie culese la final cu ocoluri lungi, așa că traseele lui sunt de obicei cu aproximativ 25% mai lungi decât cel mai bun. Metodele de inserție păstrează în schimb o buclă închisă și adaugă orașele rămase unul câte unul acolo unde costă cel mai puțin. În 1976, Nicos Christofides a găsit o construcție care garantează cel mult 1,5 ori optimul pe orice hartă metrică, o limită care a rămas aproape neîntrecută peste patruzeci de ani.

Îmbunătățirea unui traseu: 2-opt

Căutarea locală pornește de la orice traseu și face în mod repetat mici modificări care îl scurtează. Mutarea clasică, 2-opt, elimină două muchii și reconectează cele două bucăți invers, ceea ce inversează porțiunea dintre ele. Ori de câte ori două muchii se încrucișează, această mutare le descurcă și economisește lungime, deci un traseu pe care 2-opt nu îl mai poate îmbunătăți nu se intersectează niciodată cu el însuși. Pe hărți aleatorii, traseele 2-opt sunt de obicei cu aproximativ 5% peste optim. Mutările mai puternice, care schimbă trei muchii, sau metoda cu adâncime variabilă a lui Lin și Kernighan din 1973 ajung și mai aproape.

Recoacerea simulată

Căutarea locală se poate bloca într-un traseu în care fiecare mutare individuală îl înrăutățește, deși există un traseu mult mai bun. Recoacerea simulată, aplicată acestei probleme de Scott Kirkpatrick, Daniel Gelatt și Mario Vecchi în 1983, împrumută din metalurgie: acceptă o mutare mai proastă cu o probabilitate care depinde de o temperatură, ridicată la început și coborâtă treptat. La început traseul rătăcește liber; la final sunt acceptate doar îmbunătățirile. Cu o răcire suficient de lentă, găsește în mod fiabil trasee foarte bune.

Explorați

Deschideți demonstrația problemei comis-voiajorului pentru a plasa până la 200 de orașe la întâmplare, pe un cerc, în grupuri, pe o grilă sau oriunde dați clic. Urmăriți cum cel mai apropiat vecin își lasă izolate ultimele orașe, vedeți cum 2-opt descurcă fiecare încrucișare, urmăriți temperatura recoacerii simulate pe măsură ce se răcește și lăsați Held–Karp să demonstreze cel mai scurt traseu pentru până la 12 orașe. Compară toate rulează fiecare metodă pe aceeași hartă și arată cu cât este fiecare traseu mai lung decât cel mai scurt găsit.

Întrebări frecvente

Unde se folosește problema comis-voiajorului?

Oriunde ceva trebuie să viziteze multe locuri într-o ordine eficientă: rute de livrare și de colectare, traiectoria unui burghiu sau a unui laser pe o placă de circuit, ordinea în care un telescop observă stelele, culegerea comenzilor într-un depozit și, cu alte distanțe, ordinea fragmentelor la asamblarea unei secvențe de ADN.

Care este cea mai mare problemă rezolvată vreodată exact?

În 1954, George Dantzig, Ray Fulkerson și Selmer Johnson au demonstrat cel mai scurt traseu prin 49 de orașe din Statele Unite. În 2006, solverul Concorde al lui David Applegate, Robert Bixby, Vašek Chvátal și William Cook a demonstrat traseul optim prin 85.900 de puncte dintr-un proiect de cip, după ani de timp de calcul.

Este cel mai scurt traseu întotdeauna fără încrucișări?

Da, pe o hartă plană cu distanțe în linie dreaptă. Dacă două muchii s-ar încrucișa, înlocuirea lor cu două laturi ale patrulaterului pe care îl formează ar scurta traseul, deci un traseu cu încrucișări nu poate fi cel mai scurt.

Dau euristicile de fiecare dată același traseu?

Cel mai apropiat vecin, inserția cea mai ieftină și 2-opt, așa cum sunt folosite aici, sunt deterministe: pe aceleași orașe dau același traseu. Recoacerea simulată pornește de la un traseu aleatoriu și face mutări aleatorii, așa că două rulări se pot încheia cu trasee diferite, de obicei de aproape aceeași lungime.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Deschideți demonstrația problemei comis-voiajorului