Problema comis-voiajorului

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 Format:Ill-wd, cu importanță în Format:Ill-wd și în Format:Ill-wd.

PCV este un caz special al Format:Ill-wd ș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 Format:Ill-wd pentru orice algoritm pentru PCV să crească superpolinomial (dar nu mai mult decât Format:Ill-wd) 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 Format:Ill-wd și Format:Ill-wd, 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%. 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ă.

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 Format:Ill-wd. Format:Ill-wd al lui Hamilton era un puzzle bazat pe găsirea unui ciclu hamiltonian. 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 Format:Ill-wd, care a definit problema, a considerat algoritmul evident al forței brute, și a observat neoptimalitatea euristicii bazate pe vecinul cel mai apropiat: Format:Citat

Prima dată a fost analizată matematic în anii 1930 de către Merrill Flood, care încerca să rezolve problema rutării unui autobuz școlar. Format:Ill-wd de la Universitatea Princeton a introdus numele de problema comis-voiajorului puțin după aceea.

Î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, Format:Ill-wd și Format:Ill-wd de la Corporația RAND, care au exprimat problema în termeni de programare liniară întreagă și a dezvoltat Format:Ill-wd 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 Format:Ill-wd (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 Format:Ill-wd.

Î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

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. Format:Ill-wd, Format:Ill-wd, ș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 Format:Ill-wd (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.

• Format:Ill-wd 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 Format:Ill-wd cu scopul de a minimiza schimbările de cuțit. O alta implică operația de găurire la fabricarea semiconductorilor, vezi și Format:US patent. 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 Format:Ill-wd.
• 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 Format:Ill-wd. Se etichetează orașele cu numere de la 1, ..., n și se definește:

$x_{ij}=\{\begin{array}{cc}1& \text{drumul duce de la }i\text{ la }j\\ 0& \text{altfel}\end{array}$

Pentru i = 1, ..., n, fie $u_i$ o variabilă binară, și $c_{ij}$ 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:

$\begin{array}{cccc}\min & \sum _{i=1}^n\sum _{j\ne i,j=1}^n{c}_{ij}{x}_{ij}:& & \\ & 0\le x_{ij}\le 1& & i,j=1,\dots ,n;\\ & u_i\in 𝐙& & i=1,\dots ,n;\\ & \sum _{i=1,i\ne j}^n{x}_{ij}=1& & j=1,\dots ,n;\\ & \sum _{j=1,j\ne i}^n{x}_{ij}=1& & i=1,\dots ,n;\\ & u_i-u_j+n{x}_{ij}\le n-1& & 2\le i\ne j\le n.\end{array}$

Primul set de egalități impune ca la fiecare oraș să se ajungă dintr-un singur alt oraș și nu mai multe; iar al doilea set de egalități cere ca din fiecare oraș să se plece într-un singur alt oraș. Ultimele constrângeri impun existența unui singur drum care să acopere toate orașele, și nu două sau mai multe drumuri deconectate care acoperă orașele numai împreună. Pentru a demonstra aceasta, mai jos se arată (1) că fiecare soluție fezabilă conține doar un șir închis de orașe, și (2) că, pentru fiecare drum care acoperă toate orașele, există valori pentru variabilele binare $u_i$ care satisfac constrângerile.

Pentru a demonstra că fiecare soluție fezabilă conține doar o secvență închisă de orașe, este suficient să se arate că fiecare subdrum dintr-o soluție fezabilă trece prin orașul 1 (de remarcat că egalitatea asigură că nu poate fi decât un singur astfel de drum). Pentru că, dacă am însuma toate inegalitățile corespunzătoare lui $x_{ij}=1$ pentru orice subdrum de k pași care nu trece prin orașul 1, obținem:

$nk\le (n-1)k,$

ceea ce este o contradicție.

Acum trebuie să se arate că pentru fiecare drum care acoperă toate orașele, există valori pentru variabilele binare $u_i$ care satisfac constrângerile.

Fără a pierde din generalitate, se definește drumul ca avându-și originea (și capătul) în orașul 1. Fie $u_i=t$ dacă orașul i este vizitat în pasul t (i, t = 1, 2, ..., n). Atunci

$u_i-u_j\le n-1,$

deoarece $u_i$ poate fi mai mare decât n și $u_j$ poate fi nu mai mic decât 1; prin urmare, constrângerile sunt îndeplinite ori de câte ori $x_{ij}=0.$ Pentru $x_{ij}=1$, avem:

$u_i-u_j+n{x}_{ij}=(t)-(t+1)+n=n-1,$

care satisface constrângerile.

Calculul unei soluții

Liniile tradiționale de atac pentru problemele NP-dure sunt următoarele:

• Elaborarea de Format:Ill-wd, care lucrează destul de repede doar pentru probleme de mici dimensiuni.
• Elaborarea de algoritmi euristici (sau suboptimali), de exemplu, algoritmi care produc soluții aparent sau probabil bune, dar care nu pot fi demonstrate a fi optime.
• Găsirea de cazuri speciale pentru problemă („subprobleme”) pentru care sunt posibile  fie euristici mai bune, fie rezultate exacte.

Algoritmi exacți

Cea mai directă soluție ar încercarea tuturor permutărilor (combinații ordonate) și a vedea care cea este mai ieftină (folosind Format:Ill-wd). Timpul de rulare pentru această abordare este într-un factor polinomial de $O(n!)$, factorialul numărului de orașe, astfel încât această soluție devine nepractică chiar și pentru doar 20 de orașe.

Una dintre cele mai vechi aplicații ale Format:Ill-wd este Format:Ill-wd, care rezolvă problema în timp $O(n^2{2}^n)$.

O soluție simetrică a PCV cu 7 orașe folosind căutarea cu forță brută. Notă: Numărul de permutări: (7-1)!/2 = 360

Îmbunătățirea acestor limite de timp pare a fi dificilă. De exemplu, nu s-a stabilit dacă există un algoritm exact pentru PCV care se execută în timp $O(1.9999^n)$.

Alte abordări sunt:

• Diverși algoritmi branch-and-bound, care pot fi folosiți pentru a procesa PCV-uri cu 40-60 de orașe.

Soluție a PCV cu 7 orașe, folosind un algoritm branch and bound simplu. Notă: numărul de permutări este mult mai mic decât căutarea cu forța brută

• Algoritmi cu ameliorare progresivă care folosesc tehnici ce amintesc de programarea liniară. Funcționează bine cu până la 200 de orașe.
• Implementări de Format:Ill-wd și Format:Ill-wd; aceasta este metoda preferată pentru rezolvarea problemelor cu număr de mare de orașe. Ea deține actualul record, rezolvarea unei instanțe cu 85.900 de orașe, vezi Format:Harvtxt.

O soluție exactă pentru 15.112 de localități germane din TSPLIB a fost găsită în 2001 cu ajutorul Format:Ill-wd propusă de George Dantzig, Format:Ill-wd și Format:Ill-wd în 1954, pe bază de programare liniară. Calculele au fost efectuate pe o rețea de 110 procesoare situate la Universitatea Rice și la Universitatea PrincetonFormat:Necesită citare Timpul total de calcul a fost echivalent cu 22,6 ani pe un singur Format:Ill-wd la 500 MHz. În mai 2004, problema comis-voiajorului de vizitare a tuturor celor 24.978 de localități din Suedia a fost rezolvată: s-a găsit un drum de lungime aproximativ 72.500 kilometri a fost găsit și s-a demonstrat că nu există drumuri mai scurte. În martie 2005, problema comis-voiajorului de vizitare a tuturor celor 33.810 de puncte dintr-un circuit a fost rezolvată cu ajutorul Format:Ill-wd: s-a găsit un drum de lungime 66.048.945 de unități și s-a demonstrat că nu există drumuri mai scurte. Calculul a folosit aproximativ 15,7 ani-procesor (Cook et al. 2006). În aprilie 2006, un exemplu în 85,900 puncte fost rezolvat cu ajutorul Concorde TSP Solver, cu o durată de 136 ani-procesor, a se vedea Format:Harvtxt.

Algoritmi euristici și aproximativi

S-au conceput diverse euristici și Format:Ill-wd, care produc rapid soluții bune. Metodele moderne pot găsi soluții pentru probleme extrem de mari (milioane de orașe) într-un termen rezonabil, care sunt cu o mare probabilitate la doar 2-3% distanță de soluția optimă.

Euristicile cunoscute se împart în mai multe categorii.

Euristici constructive

Algoritmul „cel mai apropiat vecin” pentru o PCV cu 7 orașe. Soluția dată variază în funcție de punctul de pornire

Algoritmul „Format:Ill-wd” (Nearest Neighbor, NN; un algoritm greedy) permite comis-voiajorului să aleagă cel mai apropiat oraș nevizitat ca următoarea destinație. Acest algoritm dă rapid o rută destul de scurtă. Pentru N orașe distribuite aleator pe un plan, algoritmul pe randamentele dă în medie o cale cu 25% mai lungă decât cea mai scurtă cale posibilă. Cu toate acestea, există multe distribuții de orașe special aranjate în așa fel încât algoritmul NN dă cea mai lungă rută (Gutin, Yeo, și Zverovich, 2002). Acest lucru este valabil atât pentru PCV-uri asimetrice, cât și simetrice (Gutin și Yeo, 2007). Rosenkrantz et al. [1977] au arătat că algoritmul NN are factor de aproximare $\mathrm{\Theta }(\log |V|)$ pentru cazuri ce satisfac inegalitatea triunghiului. O variație a algoritmului NN, numită „operatorul cel mai apropiat fragment” (Nearest Fragment operator, NF), care conectează un grup (fragment) de orașe nevizitate nevizitate aflate la distanță minimă, poate găsi traseul cel mai scurt cu iterații succesive. Operatorul NF poate fi aplicat și la o soluție inițială obținută prin algoritmul NN pentru îmbunătățirea continuată într-un model elitist, în care sunt acceptate numai soluții mai bune.

Format:Ill-wd al unei mulțimi de puncte este poligonul monoton de perimetru minim care are punctele în nodurile sale; acesta poate fi calculat în mod eficient prin Format:Ill-wd.

O altă Format:Ill-wd, Match Twice and Stitch (MTS) (Kahng, Reda 2004 ), efectuează două Format:Ill-wd secvențiale, din care cel de-al doilea cuplaj este executat după ștergerea tuturor marginilor primului cuplaj, producând o mulțime de cicluri. Ciclurile sunt apoi conectate pentru a produce drumul final.

Algoritmul  lui Christofides pentru PCV

Format:Ill-wd urmează un profil similar, dar combină arborele minim de acoperire cu o soluție a unei alte probleme, Format:Ill-wd de pondere minimă. Aceasta oferă un drum PCV care este de cel mult 1,5 ori mai lung decât optimul. Algoritmul lui Christofides a fost unul dintre primii Format:Ill-wd, și are în parte meritul de a atrage atenția asupra algoritmilor de aproximare ca abordare practică la probleme greu de rezolvat. Ca o chestiune de fapt, termenul de „algoritm” nu a fost frecvent extins la algoritmi de aproximare până mai târziu; algorimtul lui Christofides a fost inițial denumit „euristica Christofides”.

Acest algoritm privește lucrurile altfel utilizând un rezultat din teoria grafurilor care ajută la îmbunătățirea limitării PCV care provine de la dublarea costului arborelui minim de acoperire. Dat fiind un graf eulerian se poate găsi un drum eulerian în timp O(n). Deci, dacă am avea un graf eulerian cu orașe dintr-o PCV ca noduri atunci am putea vedea cu ușurință că se poate utiliza o astfel de metodă de găsire a unui drum eulerian pentru a găsi o soluție la PCV. Prin inegalitatea triunghiului se știe că drumul PCV nu poate fi mai lung decât drumul eulerian și, ca atare, avem o limită minimă pentru PCV. O astfel de metodă este descrisă mai jos.

Utilizarea unei euristici de scurtare pe graful creat de cuplajul de mai jos

1. Se găsește un arbore minim de acoperire pentru problemă
2. Se creează duplicate pentru fiecare muchie pentru a crea un graf eulerian
3. Se găsește un drum eulerian pentru acest graf
4. Se convertește la PCV: dacă un oraș este vizitat de două ori, se creează o scurtătură de la orașul dinaintea lui din drum, până la cel de după el.

Pentru a îmbunătăți limita, prin urmare, este nevoie de o modalitate mai bună de a crea un graf eulerian. Dar, conform inegalității triunghiului, cel mai bun graf eulerian trebuie să aibă același cost ca cel mai bun drum al comis-voiajorului, prin urmare, găsirea de grafuri euleriene optime este cel puțin la fel de grea ca PCV. O propunere de modalitate de a face aceasta este conceptul cuplaj de pondere minimă pentru a cărui creare există algoritmi de $O(n^3)$.

Crearea unui cuplaj

Pentru a transforma un graf într-unul eulerian, se începe cu arborele minim de acoperire. Apoi, toate nodurile de ordin impar trebuie să fie făcute de ordin par. Deci trebuie adăugat un cuplaj pentru nodurile de grad impar, ceea ce crește ordinul fiecărui nod de grad impar cu unu. Aceasta produce un graf în care toate nodurile au grad par, și care este, deci, euleriane. Acum se poate adapta metoda de mai sus pentru a da algoritmul lui Christofides,

1. Se găsește un arbore minim de acoperire pentru problemă;
2. Se creează un cuplaj pentru problemă cu mulțimea orașelor de ordin impar;
3. Se găsește un drum eulerian pentru acest graf;
4. Se convertește la PCV folosind scurtături.

Îmbunătățire iterativă

Exemplu de iterație 2-opt

Schimbul pe perechi

Schimbul pe perechi, sau tehnica Format:Ill-wd,  presupune scoaterea iterativă a două muchii și înlocuirea acestora cu alte două muchii care reconectează fragmentele create de ștergerea muchiei într-un drum nou, mai scurt. Acesta este un caz special al metodei k-opt. Denumirea Lin–Kernighan este un nume frecvent, dar impropriu al tehnicii 2-opt. Lin–Kernighan este de fapt metoda k-opt, mai generală.

Pentru instanțele euclidiene, euristicile 2-opt dau, în medie, soluții care sunt cu aproximativ 5% mai bune decât algoritmul lui Christofides. Dacă se începe de la o primă soluție obținută printr-un algoritm greedy, numărul mediu de mișcări scade foarte mult din nou și este O(n). Pentru punct inițial aleatoriu însă, numărul mediu de mișcări este de O(n log(n)). Deși aceasta este o mică creștere de mărime, numărul inițial de mișcări pentru problemele mici este de 10 ori mai mare pentru un punct inițial aleatoriu, comparativ cu unul facut dintr-un greedy euristic. Acest lucru se datorează faptului că astfel de euristici 2-opt exploatează părțile „rele” dintr-o soluție, cum ar fi traversările. Aceste tipuri de euristici sunt adesea folosite în interiorul euristicilor de problema rutării vehiculelor pentru a reoptimiza soluțiile de traseu.

Euristica k-opt, sau euristica Lin–Kernighan

Se ia un drum dat și se șterg k muchii reciproc disjuncte. Se reasamblează fragmentele rămase într-un drum, nelăsând niciun subdrum neconectat. Aceasta practic simplifică PCV-ul luat în considerare într-o problemă mult mai simplă. Fiecare fragment final poate fi conectat la 2k − 2 alte posibilități: din cele 2k capete de fragmente disponibile în total, cele două capete ale fragmentului în cauză sunt nepermise. Un astfel de PCV cu 2k orașe poate fi apoi rezolvat cu metoda forței brute pentru a găsi cel mai mic cost de recombinare a fragmentelor inițiale. Tehnica k-opt este un caz special al tehnicii V-opt sau variable-opt. Cele mai populare metode k-opt sunt 3-opt, și acestea au fost introduse de către Shen Lin de la Laboratoarele Bell în anul 1965. Există un caz special de 3-opt unde muchiile nu sunt disjuncte (două muchii sunt adiacente). În practică, este adesea posibil să se realizeze o îmbunătățire substanțială față de 2-opt fără costul combinatoric al 3-optului general prin restrângerea 3-schimbărilor la această submulțime specială în care două dintre muchiile eliminate sunt adiacente. Acest așa-numit doi-și-jumătate-opt, de obicei, cade aproximativ la jumătatea distanței între 2-opt și a 3-opt, atât în ceea ce privește calitatea drumurilor realizate cât și în raport cu timpul necesar pentru a obține aceste drumuri.

Euristica V-opt

Metoda variable-opt este legată de metoda k-opt, pe care o generalizează. Întrucât metodele k-opt elimină un număr fix (k) de muchii din drumul inițial, metoda variable-opt nu repară dimensiunea muchiei setată pentru a fi eliminată. În schimb, ele cresc mulțimea pe măsură ce procesul de căutare continuă. Cea mai cunoscută metodă din această familie este metoda Lin–Kernighan (menționată mai sus ca un termen impropriu pentru 2-opt). Shen Lin și Format:Ill-wd și-au publicat pentru prima dată metoda în 1972, și a fost cea mai de încredere euristică pentru rezolvarea problemelor comis-voiajorului timp de aproape două decenii. Metode variabilă-opt mai avansate au fost dezvoltate la Bell Labs la sfârșitul anilor 1980 de către David Johnson și echipa sa de cercetare. Aceste metode (numite uneori Lin–Kernighan–Johnson) dezvoltă metoda Lin–Kernighan, adăugând idei de Format:Ill-wd și Format:Ill-wd. Tehnica Lin–Kernighan de bază dă rezultate, care sunt garantate a fie cel puțin 3-opt. Metodele Lin–Kernighan–Johnson calculează un drum Lin–Kernighan, și apoi perturbă drumul prin ceea ce a fost descris ca o mutație care elimină cel puțin patru muchii și reconectează drumul într-un mod diferit, V-optând apoi noul drum. Mutația este de multe ori suficientă pentru a deplasa drumul de la minimul local identificat prin Lin–Kernighan. Metodele V-opt sunt larg considerate cele mai puternice euristici pentru problemă, și sunt capabile de a aborda cazuri speciale, cum ar fi problema Hamilton a ciclului și alte PCV non-metrice unde alte euristici eșuează. Timp de mulți ani, Lin–Kernighan–Johnson a identificat soluții optime pentru toate PCV-urile atunci când era cunoscută o soluție optimă și a identificat cele mai bune soluții cunoscute pentru toate celelalte PCV-uri pe care a fost încercată.

Îmbunătățiri aleatoare

Algoritmi optimizați cu lanțuri Markov care folosesc subalgoritmi de căutare euristică locală pot găsi un traseu extrem de aproape de ruta optimă pentru un număr între 700 și 800 de orașe.

PCV este o piatră de încercare pentru multe euristici generale concepute pentru optimizare combinatorie, cum ar fi algoritmi genetici, Format:Ill-wd, Format:Ill-wd, Format:Ill-wd, dinamica formării râurilor (vezi inteligență de „roi”) și Format:Ill-wd.

Optimizarea cu colonie de furnici

Cercetătorul din domeniul inteligenței artificiale Marco Dorigo descria în 1993 o metodă de generare euristică de „soluții bune” la PCV, folosind o Format:Ill-wd numită ACS (Ant Colony System). Ea modelează comportamentul, observat la furnicile adevărate, de a găsi scurtături între sursele de hrană și cuibul lor, un comportament Format:Ill-wd care rezultă din faptul că fiecare furnică preferă să urmărească urmele de feromoni depuse de către alte furnici.

ACS trimite un număr mare de agenți inteligenți virtuali („furnici”) pentru a explora mai multe rute posibile pe hartă. Fiecare furnică alege probabilistic următorul oraș de vizitat după o euristică ce combină distanța până la acel oraș și cantitatea de feromoni virtuali lăsată pe muchia ce duce la oraș. Furnicile explorează, depozitează feromoni la fiecare muchie prin care trec, până când toți termină un drum. În acest moment, furnica care a finalizat cel mai scurt drum depune feromoni virtuali de-a lungul întregului său drum (global trail updating). Cantitatea de feromoni lăsată este invers proporțională cu lungimea drumului: cu cât mai scurt drumul, cu atât mai mult feromon depus.

Algoritm de optimizare al coloniei de furnici pentru o PCV cu 7 orașe: liniile roșii și groase în harta de feromoni indică prezența mai multor feromoni

Cazuri speciale de PCV

PCV metrică

În PCV metrică, denumită și delta-PCV sau Δ-PCV, distanțele între orașe satisfac inegalitatea triunghiului.

O restricție foarte naturală a PCV este de a impune ca distanțele între orașe să formeze o metrică ce satisface inegalitatea triunghiului; ca legătura directă dintre A și B să nu fie niciodată mai mare decât traseul printr-un oraș intermediar C:

$d_{AB}\le d_{AC}+d_{CB}$.

Lungimile muchiilor construiesc atunci o metrică pe mulțimea nodurilor. Când orașele sunt privite ca puncte în plan, multe funcții distanță naturale sunt metrici, și foarte multe cazuri naturale de PCV satisfac această constrângere.

Următoarele sunt câteva exemple de PCV metrice pentru diverse valori.

• În PCV euclidiană (a se vedea mai jos), distanța dintre două orașe este distanța euclidiană dintre punctele corespunzătoare.
• În PCV rectilinie, distanța dintre două orașe este suma diferențelor coordonatelor lor x și y. Această valoare este adesea numită distanță Manhattan sau metrica cvartalului.
• În metrica maximă, distanța dintre două puncte este maximul valorilor absolute ale diferențelor coordonatelor x și y.

Ultimele două valori apar de exemplu în rutarea unei mașini care execută o serie dată de găuri într-o placă de circuit imprimat. Metrica Manhattan corespunde unei mașini care reglează prima coordonată, și apoi pe cealaltă, astfel încât timpul pentru a trece la un nou punct este suma celor două mișcări. Metrica maximă corespunde unei mașini care reglează ambele coordonate simultan, astfel încât timpul de trecere la un punct nou este cea mai lentă dintre cele două mișcări.

În definiția sa, PCV nu permite ca orașele să fie vizitate de două ori, dar multe aplicații nu au nevoie de această constrângere. În astfel de cazuri, un exemplu simetric și nemetric poate fi redus la unul metric. Aceasta înlocuiește graful inițial cu un graf în care distanța între orașe $d_{AB}$ este înlocuită de cel mai scurt drum între A și B în graful inițial.

PCV euclidiană

Atunci când numerele de intrare pot fi numere reale arbitrare, PCV euclidiană este un caz particular al PCV metrice, deoarece distanțele într-un plan respectă inegalitatea triunghiului. Atunci când numerele de intrare trebuie să fie numere întregi, compararea lungimilor drumurilor implică compararea sumelor de radicali.

Ca și PCV generală, PCV euclidiană este NP-dură, în orice caz. Cu coordonate raționale și discretizată metric (distanțele rotunjite la un număr întreg), problema este NP-completă.Format:Sfnp Cu coordonate raționale și metrică euclidiană reală, PCV euclidiană este cunoscută a fi în Ierarhia de Numărare, o subclasă a PSPACE. Cu coordonate reale arbitrare, PCV euclidiană nu poate fi în astfel de clase, deoarece există un număr nenumărabil de intrări posibile. Cu toate acestea, PCV euclidiană este, probabil, cea mai simplă versiune pentru aproximare. De exemplu, arborele minim de acoperire al grafului asociat cu o instanță de PCV euclidiană este un Format:Ill-wd, și astfel poate fi calculat într-un timp așteptat de O (n log n) pentru n puncte (considerabil mai puțin decât numărul de muchii). Acest lucru permite unui algorim simplu cu 2-aproximare pentru OCV cu inegalitatea triunghiului de mai sus să funcționeze mai rapid.

În general, pentru orice c > 0, unde d este numărul de dimensiuni în spațiul euclidian, există un algoritm în timp polinomial care găsește un drum de lungime cel mult (1 + 1/c) înmulțit cu optimul pentru  cazuri geometrice de PCV în timp

$O(n(\log n{)}^{(O(c\sqrt{d}){)}^{d-1}}),$

Aceasta se numește Format:Ill-wd (PTAS).Format:Sfnp Format:Ill-wd și Format:Ill-wd au primit premiul Gödel în 2010 pentru descoperirea simultană a unui PTAS pentru PCV euclidiană.

În practică, euristici mai simple cu garanții mai slabe continuă să fie utilizate.

PCV asimetrică

În cele mai multe cazuri, distanța dintre două noduri în rețeaua PCV este aceeași în ambele direcții. În cazul în care distanța de la A la B nu este egală cu distanța de la B la A, PCV se numește asimetrică. O aplicație practică a unei PCV asimetrice este optimizarea rutelor, folosind rutare la nivel de stradă (care se face asimetric pe străzi cu sens unic, rampe de acces, autostrăzi, etc.).

Rezolvarea prin conversie la PCV simetrică

Rezolvarea unui graf de  PCV asimetrică poate fi destul de complexă. În cele ce urmează, se prezintă o matrice 3×3 care conține toate ponderile de drumuri între nodurile A, B și C. O opțiune este de a transforma o matricea asimetrică de dimensiune N într-o matrice simetrică de dimensiune 2N.

Ponderile asimetrice ale căilor

A	B	C
A	1	2
B	6	3
C	5	4

Pentru a dubla dimensiunea, fiecare dintre nodurile grafului este duplicat, creând un al doilea nod fantomă, legat de nodul inițial printr-o muchie „fantomă” de pondere foarte joasă (eventual negativă), notată aici cu −w. (Alternativ, muchiile fantomă au pondere 0, iar ponderea w este adăugată la toate celelalte muchii.) Matricea inițială 3×3 prezentată mai sus este vizibilă în partea de stânga-jos și transpusa celei inițiale, în partea de dreapta-sus. Ambele copii ale matricei au diagonalele principale înlocuite cu căi de cost minim, reprezentate prin −w. În noul graf, nicio muchie nu leagă direct noduri inițiale noduri și nicio muchie nu leagă direct noduri fantomă.

Ponderile căilor simetrice

A	B	C	A'	B'	C'
A	−w	6	5
B	1	−w	4
C	2	3	−w
A'	−w	1	2
B'	6	−w	3
C'	5	4	−w

Ponderea −w a muchiilor „fantomă” care leagă nodurile fantomă corespunzătoare nodurilor originare trebuie să fie suficient de scăzută pentru a se asigura că toate muchiile fantomă aparțin oricărei soluții a PCV simetrice din noul graf (w=0 nu este întotdeauna suficient de scăzut). Ca o consecință, în drumurile simetrice optime, fiecare nod inițial apare lângă nodul său fantomă (de exemplu, o posibilă cale este A -> A' -> C -> C' -> B -> B' -> A) și prin comasarea nodului inițial cu nodul său fantomă se obține o soluție (optimă) a problemei inițiale asimetrice (în exemplul nostru, A -> C -> B -> A).

Problema comis-voiajorului pentru analist

Există o problemă similară în Format:Ill-wd care cere următoarele: în ce condiții poate o submulțime E a spațiului euclidian să fie cuprinsă într-o Format:Ill-wd (adică: când există o curbă cu lungime finită care vizitează fiecare punct din E)? Această problemă este cunoscută ca Format:Ill-wd.

Lungimea căii PCV pentru mulțimi aleatoare de puncte într-un pătrat

Se presupune că $X_1,\dots ,X_n$ sunt $n$ variabile aleatoare independente cu distribuție uniformă în pătratul $[0,1{]}^2$ și fie $L_n^{\ast }$ lungimea căii celei mai scurte (adică soluția PCV) pentru această mulțime de puncte, conform distanței Euclidiene standard. Se știe că, aproape sigur,

$\frac{L_n^{*}}{\sqrt{n}}\to \beta \text{when }n\to \mathrm{\infty },$

unde $\beta$ este o constantă pozitivă care nu este cunoscută în mod explicit. Deoarece $L_n^{*}\le 2\sqrt{n}+2$ (a se vedea mai jos), rezultă din teorema convergenței dominate că $\beta =\underset{n\to \mathrm{\infty }}{\lim }𝔼[L_n^{*}]/\sqrt{n}$, prin urmare, limitele inferioară și superioară ale lui $\beta$ rezultă din limitele lui $𝔼[L_n^{*}]$.

Limita aproape sigură $\frac{L_n^{*}}{\sqrt{n}}\to \beta$ când $n\to \mathrm{\infty }$ nu poate exista dacă locațiile independente $X_1,\dots ,X_n$ sunt înlocuite cu observații dintr-un proces ergodic staționar cu marginali uniformi.

Limita superioară

• Avem $L^{*}\le 2\sqrt{n}+2$ și, prin urmare, $\beta \le 2$, prin utilizarea unei căi naive care vizitează monoton punctele din interiorul fiecăreia din cele $\sqrt{n}$ felii de lățime $1/\sqrt{n}$ din pătrat.
• Few  a demonstrat că $L_n^{*}\le \sqrt{2n}+1.75$, prin urmare, $\beta \le \sqrt{2}$, rezultat ulterior îmbunătățit de către Karloff (1987): $\beta \le 0.984\sqrt{2}$.
• În prezent cea mai bună limită superioară este $\beta \le 0.92\dots$.

Limita inferioară

• Observând că $𝔼[L_n^{*}]$ este mai mare decât de $n$ ori distanța între $X_0$ și cel mai apropiat punct $X_i\ne X_0$, se obține (după un scurt calcul)

$𝔼[L_n^{*}]\ge \frac{1}{2}\sqrt{n}.$

• O limită inferioară mai bună se obține observând că $𝔼[L_n^{*}]$ este mai mare decât $\frac{1}{2}n$ înmulțit cu suma distanțelor între $X_0$ și cel mai apropiat și al doilea cel mai apropiat punct $X_i,X_j\ne X_0$, care dă

$𝔼[L_n^{*}]\ge (\frac{1}{4}+\frac{3}{8})\sqrt{n}=\frac{5}{8}\sqrt{n},$

• Actualmente  cea mai bună limită inferioară este

$𝔼[L_n^{*}]\ge (\frac{5}{8}+\frac{19}{5184})\sqrt{n},$

• Held și Karp au dat un algoritm în timp polinomial care oferă limite inferioare numerice pentru $L_n^{*}$ și, astfel, pentru $\beta (\simeq L_n^{*}/\sqrt{n})$ care pare să fie bun până la circa 1%. În special, David S. Johnson a obținut o limită inferioară prin experiment rulat pe calculator:

$L_n^{*}\gtrsim 0.7080\sqrt{n}+0.522,$

unde numărul 0.522 vine de la punctele de lângă marginea pătratului, care au mai puțini vecini, și Christine L. Valenzuela și Antonia J. Jones  au obținut următoarea limită inferioară numerică:

$L_n^{*}\gtrsim 0.7078\sqrt{n}+0.551$.

Complexitatea

Problema a fost demonstrată a fi NP-dificilă (mai precis, este completă pentru clasa de complexitate FP^NP), și versiunea ca problemă de decizie („date fiind costurile și un număr x, să se decidă dacă există un ciclu mai ieftin decât x”) este NP-completă. Problema comis-voiajorului cu bottleneck este, de asemenea, NP-dură. Problema rămâne NP-dură chiar și pentru cazul când orașele sunt în plan cu distanțe euclidiene, precum și într-o serie de alte cazuri restrictive. Eliminarea condiției de a vizita fiecare oraș „doar o dată” nu elimină NP-duritatea, deoarece este ușor de văzut că, în cazul plan, există un ciclu optim care vizitează fiecare oraș o singură dată (în caz contrar, prin inegalitatea triunghiului, o scurtătură care sare o vizită care s-ar repeta nu ar crește lungimea drumului).

Complexitatea aproximării

În cazul general, găsirea celui mai scurt drum al comis-voiajorului este Format:Ill-wd-completă. Dacă măsura distanței de măsură este o metrică și simetrică, problema devine Format:Ill-wd-completă și Format:Ill-wd o aproximează într-o marjă de 1.5. Cea mai cunoscut limită de inaproximabilitate este 123/122 .

Dacă distanțele sunt limitate la 1 și 2 (dar încă metrice) raportul de aproximare devine 8/7.Format:Sfnp În cazul asimetric și metric, se cunosc numai garanții de performanță logaritmice, cel mai bun algoritm realizând raportul de performanță la 0.814 log(n); este o întrebare deschisă dacă există un factor constant de aproximare există.

Problema corespunzătoare de maximizare de a găsi cea mai lungă cale pentru comis-voiajor este aproximabilă în 63/38. Dacă funcția de distanță este simetrică, cel mai lung drum poate fi aproximat în 4/3 printr-un algoritm determinist și în $\frac{1}{25}(33+\epsilon )$ printr-un algoritm randomizat.

Performanța umană pe PCV

PCV, în special varianta euclidiană a problemei, a atras atenția cercetătorilor din psihologia cognitivă. S-a observat că oamenii sunt capabili să producă soluții de calitate rapid. Aceste rezultate sugerează că performanța calculatoarelor la PCV poate fi îmbunătățită prin înțelegerea și emularea metodelor folosite de oameni pentru aceste probleme, și au condus și la noi perspective privind mecanismele gândirii umane. Primul număr al Journal of Problem Solving a fost dedicat subiectului performanței umană pe PCV, și o revizuire din 2011 a enumerat zeci de lucrări pe această temă.

Calculul natural

Atunci când i se prezintă o configurație spațială a surselor de alimentare, Format:Ill-wd Format:Ill-wd își adaptează morfologia pentru a crea o cale eficientă între surse de alimentare, ceea ce poate fi văzut și ca o soluție aproximativă pentru PCV. Se consideră că prezintă posibilități interesante și a fost studiată în domeniul Format:Ill-wd.

Teste de referință

Pentru testarea algoritmilor PCV, TSPLIB este o bibliotecă de cazuri de test pentru PCV și problemele asociate. Multe dintre ele sunt liste de orașe reale și distribuții de circuite imprimate reale.

Cultura populară

• Romanul thriller The Steradian Trail de M. N. Krish folosește problema comis-voiajorului și prezintă pe matematicianul Srinivasa Ramanujan și o descoperire accidentală a acestuia, într-o acțiune ce împletește religia, matematica, finanțele și economia.
• Travelling Salesman, de regizorul Timothy Lanzone, este povestea a patru matematicieni angajați de către guvernul SUA să rezolve cea mai evazivă problemă din istoria informaticii: P versus NP.

Bibliografie

• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.

Lectură suplimentară

• Format:Citation
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.
• Format:Citation.

Legături externe

• Format:Webarchive la Universitatea din Waterloo
• TSPLIB Format:Webarchive la Universitatea din Heidelberg
• Problema Comis-Voiajorului de Jon McLoone la Wolfram Demonstrations Project