miniatura|Soluție a unei probleme a comis-voiajorului: linia neagră arată cea mai scurtă buclă posibilă care conectează toate punctele roșii Problema comis-voiajorului (PCV) pune următoarea întrebare: „Dată fiind o listă de orașe și distanțele între fiecare două orașe, care este cel mai scurt traseu posibil care vizitează fiecare oraș o singură dată și se întoarce la orașul de origine?” Ea este o problemă NP-dificilă în , cu importanță în și în .
PCV este un caz special al și a problemei rutării vehiculelor.
În teoria complexității, versiunea de decizie a PCV (unde, dată fiind o lungime L, sarcina este de a stabili dacă graful are un ciclu complet mai scurt decât L) aparține clasei problemelor NP-complete. Astfel, este posibil ca pentru orice algoritm pentru PCV să crească superpolinomial (dar nu mai mult decât ) cu numărul de orașe.
Problema a fost formulată pentru prima dată în 1930 și este una dintre cele mai intens studiate probleme de optimizare. Ea este utilizată ca test pentru multe metode de optimizare. Chiar dacă problema este dificilă computațional, se cunosc numeroși și , astfel încât unele cazuri cu zeci de mii de orașe pot fi rezolvate complet și chiar probleme cu milioane de orașe pot fi aproximate cu o eroare de 1%.Vezi PCV cu turul mondial deja rezolvată cu o aproximație de 0,05% de soluția optimă. A fost abordată și prin computația cu ADN, de Leonard Adleman.
PCV are mai multe aplicații, chiar și în cea mai pură formulare, cum ar fi în planificare, logistică, și la fabricarea de microcipuri. Ușor modificată, ea apare ca o subproblemă în multe domenii, cum ar fi secvențierea ADN-ului. În aceste aplicații, conceptul de oraș reprezintă, de exemplu, clienți, puncte de sudură, sau fragmente de ADN (nucleotidă), și conceptul de distanță reprezintă durata de deplasare, costul de realizare, sau o măsură a similarității între fragmente de ADN. PCV apare și în astronomie, astronomii care observă mai multe surse dorind să minimizeze timpul petrecut de telescop în mișcare între surse. În multe aplicații se pot impune constrângeri suplimentare, cum ar fi resursele limitate sau ferestre de timp.
Istoria Originile problemei comis-voiajorului nu sunt bine cunoscute. Un manual pentru vânzătorii ambulanți din 1832 menționează problema și include exemple de drumuri optime prin Germania și Elveția, dar nu conține nicio tratare matematică."Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (Comis-voiajorul — cum trebuie el să fie și ce trebuie să facă pentru a primi comisioane și pentru a fi sigur de fericitul succes al afacerii sale — de un bătrân commis-voyageur) thumb|right|upright|William Rowan Hamilton Problema comis-voiajorului a fost formulată matematic în anii 1800 de către matematicianul irlandez W. R. Hamilton și de matematicianul britanic . al lui Hamilton era un puzzle bazat pe găsirea unui ciclu hamiltonian.O discuție despre primele lucrări ale lui Hamilton și Kirkman se poate găsi în Graph Theory 1736–1936 Forma generală a PCV pare să fi fost mai întâi studiată de către matematicieni în anii 1930, la Viena și la Harvard, în special de către , care a definit problema, a considerat algoritmul evident al forței brute, și a observat neoptimalitatea euristicii bazate pe vecinul cel mai apropiat:
Prima dată a fost analizată matematic în anii 1930 de către Merrill Flood, care încerca să rezolve problema rutării unui autobuz școlar. de la Universitatea Princeton a introdus numele de problema comis-voiajorului puțin după aceea.O tratare amănunțită a legăturii între Menger și Whitney precum și a creșterii studiului PCV se poate găsi în articolul lui din 2005 „On the history of combinatorial optimization (till 1960)”.
În deceniile anilor 1950 și 1960, problema a devenit din ce în ce mai populară în cercurile științifice din Europa și SUA după ce Corporația RAND din Santa Monica a oferit premii pentru pași spre rezolvarea problemei. Contribuții remarcabile au fost făcute de către George Dantzig, și de la Corporația RAND, care au exprimat problema în termeni de programare liniară întreagă și a dezvoltat pentru soluționarea ei. Ei au scris ceea ce este considerat a fi lucrarea de căpătâi a acestei teme în care, cu aceste metode noi, au rezolvat un caz cu 49 de orașe în mod optim prin construirea unui drum și demonstrând că niciun alt drum nu poate fi mai scurt. Dantzig, Fulkerson și Johnson au speculat însă că, dacă se dă o soluție cvasioptimă, am putea fie găsi una optimă sau demonstra optimalitatea celei date, prin adăugarea de cantități mici de inegalități suplimentare (tăieturi). Ei au folosit această idee pentru a rezolva problema lor inițială cu 49 de orașe folosind un model cu șiruri. Ei au găsitcă au nevoie de doar 26 de reduceri pentru a ajunge la o soluție pentru problema lor cu 49 de orașe. Deși această lucrare nu dădea o abordare algoritmică a PCV, ideile care erau enunțate în ea au fost indispensabile pentru crearea mai târziu de soluții exacte pentru PCV, cu toate că aveau să treacă 15 ani înainte de a fi găsită o abordare algoritmică pentru realizarea acestor reduceri. Ca și metodele cu plan secant, Dantzig, Fulkerson și Johnson au folosit algoritmi (ramificare și limitare) poate pentru prima dată.
În următoarele decenii, problema a fost studiată de mulți cercetători din matematică, informatică, chimie, fizică și alte științe. În anii 1960, însă, a fost creată o nouă abordare care, în loc să caute soluțiile optime, producea o soluție a cărei lungime era demonstrabil delimitată de un multiplu al lungimii optime, și astfel de crea limite inferioare pentru problemă; acestea pot fi apoi utilizate cu abordări branch and bound. O metodă în acest sens a fost crearea un arbore minim de acoperire al grafului și apoi dublarea tuturor muchiilor sale, care produce limita ca lungimea unui drum optim să fie cel mult dublul ponderii unui arbore minim de acoperire.
Christofides a făcut un pas mare în acest demers, oferind o abordare pentru care se știe cel mai rău caz. Algoritmul dat în 1976 era în cel mai rău caz de 1,5 ori mai lung decât soluția optimă. Cum algoritmul era atât simplu cât și rapid, mulți sperau că va deschide drumul către o metodă care să dea o soluție cvasioptimă. Cu toate acestea, până în 2011, când a fost depășită cu mai puțin de o miliardime de procent, ea a rămas metoda cu cel mai bun scenariu în cel mai rău caz.
Richard M. Karp a arătat în 1972 că problema ciclului hamiltonian este NP-completă, ceea ce presupune NP-duritatea PCV. De aici a apărut o explicație matematică a aparentei dificultăți computaționale de a găsi drumuri optime.
S-au făcut mari progrese la sfârșitul anilor 1970 și în anii 1980, când Grötschel, Padberg, Rinaldi și alții au reușit să rezolve exact cazuri cu până la 2392 orașe, folosind plane secante și .
În 1990, Applegate, Bixby, Chvátal, și Cook au dezvoltat programul Concorde, care a fost folosit în multe soluții recente. Gerhard Reinelt a publicat în 1991 TSPLIB, o colecție de instanțe de referință de diferite grade de dificultate, care a fost folosită de mai multe grupuri de cercetare pentru a compara rezultatele. În 2006, Cook și alții au calculat un drum optim printr-un exemplu cu 85.900 de orașe dat de un o problemă de aranjare a circuitelor pe un microcip, în prezent cel mai mare exemplu rezolvat din TSPLIB. Pentru multe alte cazuri cu milioane de orașe, se pot găsi soluții garantate a avea o eroare de 2-3% față de drumul optim..
Descriere
Ca problemă de grafuri miniatura|PCV simetric cu patru orașe PCV poate fi modelată ca graf neorientat ponderat, astfel încât orașele să fie noduri ale grafului, drumurile să fie muchii, iar distanța unei căi să fie ponderea fiecărei muchii. Este o problemă de minimizare cu începere și terminare într-un anumit nod, după ce se vizitează fiecare nod o singură dată. De multe ori, modelul este un graf complet (adică fiecare pereche de noduri este conectată prin câte o muchie). Dacă nu există o cale între două orașe, adăugarea unei muchii arbitrar de lungi de margine va face graful complet, fără a afecta drumul optim.
Asimetrică și simetrică În PCV simetrică, distanța dintre două orașe este aceeași în fiecare direcție opusă, formând un graf neorientat. Această simetrie înjumătățește numărul de soluții posibile. În PCV asimetrică, se poate să nu existe căi în ambele direcții sau distanțele pot fi diferite, formând un graf orientat. Accidentele în trafic, , și cursele cu costuri diferite în funcție de sens sunt exemple de ce cazuri reale ar putea duce la ruperea acestei simetrii.
Probleme similare sau asociate O formulare echivalentă în termeni de teoria grafurilor este: Dat fiind un graf ponderat complet (unde nodurile ar reprezenta orașe, muchiile ar reprezenta drumuri, și ponderile ar fi costul sau distanța drumului), să se găsească un ciclu hamiltonian de pondere minimă. Cu sau fără cerința de revenire la orașul inițial, complexitatea problemei este aceeași. O altă problemă asociată este (PCV cu bottleneck): să se găsească un ciclu hamiltonian într-un graf ponderat, care să aibă cea mai mică pondere maximă a unei muchii. Problema este de o importanță practică considerabilă, în afara domeniului evident de aplicabilitate în transporturi și logistică. Un exemplu clasic este în producția de circuite imprimate: programarea unui traseu al mașinii de găurit pe un PCB. În asemenea aplicații robotizate, „orașele” sunt piesele sau găurile (de diferite dimensiuni) de executat, iar „costul călătoriei” cuprinde timpi pentru reutilarea robotului.
tratează „state” care au unul sau mai multe „orașe” și comis-voiajorul trebuie să viziteze exact un „oraș” din fiecare „stat”. O aplicație a ei se poate întâlni la ordonarea unei soluții la cu scopul de a minimiza schimbările de cuțit. O alta implică operația de găurire la fabricarea semiconductorilor, vezi și . Noon și Bean au demonstrat că problea comis-voiajorului generalizată poate fi transformată într-o problemă a comis-voiajorului standard cu același număr de orașe, dar cu o modificare a . Secvențială comanda problemă se ocupă cu problema de a vizita un set de orașe în care prevalează raporturile dintre orașe există. O întrebare frecventă la interviurile de angajare la Google este cum să se ruteze datele între nodurile de prelucrare; timpul de transfer al datelor variază de la rută la rută, dar și nodurile diferă în funcție de puterea lor de calcul și de capacitatea de stocare, complicând problema găsirii rutei pe care să se trimită datele. Problema cumpărătorului ambulant tratează un cumpărător care este însărcinat să achiziționeze o mulțime de produse. El poate cumpăra aceste produse în mai multe orașe, dar la prețuri diferite și nu toate orașele oferă aceleași produse. Obiectivul este de a găsi o rută între o submulțime de orașe, care minimizează costul total (costuri de călătorie + costul de cumpărare) și care permite achiziționarea tuturor produselor solicitate.
Formulare în termeni de programare liniară cu întregi PCV poate fi formulată ca o ., pp.308-309.Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)Dantzig, George B. (1963), Linear Programming and Extensions, Princeton, NJ: PrincetonUP, pp. 545–7, ISBN 0-691-08000-3, a șasea tipărire, 1974. Se etichetează orașele cu numere de la 1, ..., n și se definește:
Pentru i = 1, ..., n, fie o variabilă binară, și distanța de la orașul i la orașul j. Atunci, PCV poate fi scrisă ca următoarea problemă de programare liniară cu numere întregi: