Problema comis-voiajorului

Problema călătorului de vânzări (adesea numită TSP) este o problemă algoritmică clasică în domeniul informaticii și al cercetării operaționale. Ea este axată pe optimizare. În acest context, o soluție mai bună înseamnă adesea o soluție mai ieftină, mai scurtă sau mai rapidă. TSP este o problemă matematică. Este cel mai ușor de exprimat sub forma unui grafic care descrie locațiile unui set de noduri.

Problema comis-voiajorului călător a fost definită în anii 1800 de către matematicianul irlandez W. R. Hamilton și de matematicianul britanic Thomas Kirkman. Jocul Icosian al lui Hamilton era un puzzle recreativ bazat pe găsirea unui ciclu hamiltonian. Forma generală a TSP pare să fi fost studiată pentru prima dată de matematicieni în anii 1930 la Viena și la Harvard, în special de Karl Menger. Menger definește problema, ia în considerare algoritmul evident de forță brută și observă caracterul neoptimal al euristicii celui mai apropiat vecin:

Numim problema mesagerului (deoarece în practică această problemă ar trebui rezolvată de fiecare poștaș, oricum și de mulți călători) sarcina de a găsi, pentru un număr ﬁnit de puncte ale căror distanțe pereche sunt cunoscute, cea mai scurtă rută care leagă punctele. Bineînțeles, această problemă este rezolvabilă printr-un număr finit de multe încercări. Nu se cunosc reguli care ar împinge numărul de încercări sub numărul de permutări ale punctelor date. Regula conform căreia ar trebui să se meargă mai întâi de la punctul de plecare la punctul cel mai apropiat, apoi la punctul cel mai apropiat de acesta etc., în general, nu produce cel mai scurt traseu.

Hassler Whitney, de la Universitatea Princeton, a introdus la scurt timp după aceea numele de problema vânzătorului ambulant.

Un agent de vânzări dorește să viziteze toate orașele A, B, C și D. Care este cea mai bună cale de a face acest lucru (cele mai ieftine bilete de avion și timpul de călătorie minim)?

Traseul optim al unui agent de vânzări care vizitează cele mai mari 15 orașe din Germania. Traseul prezentat este cel mai scurt dintre cele 43.589.145.600 de trasee posibile.

William Rowan Hamilton

Expunerea problemei

Problema agentului de vânzări călător descrie un vânzător care trebuie să călătorească între N orașe. Ordinea în care face acest lucru nu îl interesează, atâta timp cât vizitează fiecare oraș o dată în timpul călătoriei și termină acolo unde a fost la început. Fiecare oraș este conectat la alte orașe apropiate, sau noduri, prin avioane, drumuri sau căi ferate. Fiecăreia dintre aceste legături dintre orașe îi sunt atașate una sau mai multe greutăți (sau costuri). Costul descrie cât de "dificil" este să traversezi această muchie a grafului și poate fi dat, de exemplu, de costul unui bilet de avion sau de tren, sau poate de lungimea muchiei, sau de timpul necesar pentru a finaliza traversarea. Vânzătorul dorește ca atât costurile de deplasare, cât și distanța pe care o parcurge să fie cât mai mici posibil.

Problema comis-voiajorului călător este tipică pentru o clasă largă de probleme de optimizare "dificile" care îi intrigă pe matematicieni și pe informaticieni de ani de zile. Cel mai important este faptul că are aplicații în știință și inginerie. De exemplu, în fabricarea unei plăci de circuite, este important să se determine cea mai bună ordine în care un laser va face mii de găuri. O soluție eficientă la această problemă reduce costurile de producție pentru producător.

Dificultate

În general, problema vânzătorului ambulant este greu de rezolvat. Dacă există o modalitate de a împărți această problemă în probleme componente mai mici, componentele vor fi cel puțin la fel de complexe ca și cea inițială. Aceasta este ceea ce informaticienii numesc probleme NP-hard.

Mulți oameni au studiat această problemă. Cea mai simplă (și cea mai costisitoare soluție) este de a încerca pur și simplu toate posibilitățile. Problema este că, pentru N orașe, există (N-1) posibilități factoriale. Acest lucru înseamnă că pentru doar 10 orașe există peste 180 de mii de combinații de încercat (deoarece orașul de start este definit, pot exista permutări pentru celelalte nouă). Noi numărăm doar jumătate, deoarece fiecare traseu are un traseu egal în sens invers cu aceeași lungime sau cost. 9! / 2 = 181 440

Soluțiile exacte ale problemei pot fi găsite, folosind algoritmi de ramificare și delimitare. Acest lucru este posibil în prezent pentru un număr de până la 85 900 de orașe.
Abordările euristice utilizează un set de reguli de ghidare pentru selectarea nodului următor. Dar, deoarece euristica are ca rezultat aproximări, nu va oferi întotdeauna soluția optimă, deși euristica admisibilă de înaltă calitate poate găsi o soluție utilă într-o fracțiune din timpul necesar pentru o rezolvare completă a problemei prin forță brută. Un exemplu de euristică pentru un nod ar fi o însumare a numărului de noduri nevizitate care se află "aproape" de un nod conectat. Acest lucru ar putea încuraja vânzătorul să viziteze un grup de noduri apropiate grupate împreună înainte de a trece la un alt grup natural din graf. A se vedea Algoritmi Monte Carlo și Algoritmi Las Vegas.

Întrebări și răspunsuri

Î: Ce este problema vânzătorului călător?

R: Traveling Salesman Problem (TSP) este o problemă algoritmică clasică în domeniul informaticii și al cercetării operaționale. Ea se concentrează pe optimizare, soluțiile mai bune însemnând adesea soluții mai ieftine, mai scurte sau mai rapide.

Î: Cum se exprimă TSP?

R: TSP este cel mai ușor de exprimat sub forma unui grafic care descrie locațiile unui set de noduri.

Î: Cine a definit primul TSP?

R: Problema comis-voiajorului călător a fost definită în anii 1800 de către matematicianul irlandez W. R. Hamilton și de către matematicianul britanic Thomas Kirkman.

Î: Cine a studiat-o în continuare în anii 1930?

R: În anii 1930, matematicienii Karl Menger de la Viena și Harvard au studiat-o mai amănunțit.

Î: Ce a introdus Hassler Whitney la scurt timp după aceea?

R: Hassler Whitney, de la Universitatea Princeton, a introdus denumirea de "problema comis-voiajorului călător" la scurt timp după definirea acesteia.

Î: Ce înseamnă "soluție mai bună" în acest context?

R: În acest context, o soluție mai bună înseamnă adesea o soluție mai ieftină, mai scurtă sau mai rapidă.

Î: Ce algoritm a fost considerat evident de către Menger atunci când a studiat TSP?

R: Menger a considerat evident un algoritm de forță brută atunci când a studiat TSP și a observat că utilizarea euristicii celui mai apropiat vecin nu produce întotdeauna rezultate optime.