Problema comis-voiajorului

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
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-dură în optimizarea combinatorie⁠(d), cu importanță în cercetarea operațională⁠(d) și în informatica teoretică⁠(d).

PCV este un caz special al problemei cumpărătorului ambulant⁠(d) și a problemei rutării vehiculelor⁠(d).

În teoria complexității, versiunea de decizie a PCV (unde, dată fiind o lungime L, sarcina este de a decide dacă graful are un ciclu complet mai scurt decât L) aparține clasei problemelor NP-complete. Astfel, este posibil ca timpul de rulare în cel mai rău caz⁠(d) pentru orice algoritm pentru PCV să crească superpolinomial (dar nu mai mult decât exponențial⁠(d)) 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 benchmark⁠(d) pentru multe metode de optimizare. Chiar dacă problema este dificilă computațional, se cunosc numeroși algoritmi euristici⁠(d) și exacți⁠(d), 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%.[1]

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, ș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[modificare | modificare sursă]

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ă.[2]

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 Thomas Kirkman⁠(d). Jocul icosian⁠(d) al lui Hamilton era un puzzle bazat pe găsirea unui ciclu hamiltonian.[3] 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 Karl Menger⁠(d), care a definit problema, a considerat algoritmul evident al forței brute, și a observat neoptimalitatea euristicii bazate pe vecinul cel mai apropiat:

„Prin problema curierului (întrucât în practică această întrebare și-o pune fiecare poștaș, dar și numeroși alți calători) notăm găsirea, pentru un număr finit de puncte între care știm distanțele două câte două, a rutei celei mai scurte care leagă toate punctele. Desigur, această problemă poate fi rezolvată printr-un număr finit de încercări. Nu se cunosc reguli care să aducă numărul de încercări sub numărul de permutări al punctelor date. Regula care duce curierul din primul punct în cel mai apropiat, apoi în cel mai apropiat de acesta etc., în general nu produce ruta cea mai scurtă.[4]

Prima dată a fost analizată matematic în anii 1930 de către Merrill Flood, care încerca să rezolve problema rutării unui autobuz școlar.[5] Hassler Whitney⁠(d) de la Universitatea Princeton a introdus numele de problema comis-voiajorului puțin după aceea.[6]

Î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, D. R. Fulkerson⁠(d) și Selmer M. Johnson⁠(d) de la Corporația RAND, care au exprimat problema în termeni de programare liniară întreagă și a dezvoltat planul secant⁠(d) 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 Branch and bound⁠(d) (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⁠(d) al grafului și apoi dublare tuturor marginilor 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.[7]

Richard M. Karp a arătat în 1972 că problema ciclului hamiltonian este NP-completă, ceea ec 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 Branch and bound⁠(d).

Î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.[8]

Descriere[modificare | modificare sursă]

Ca problemă de grafuri[modificare | modificare sursă]

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ă[modificare | modificare sursă]

Î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⁠(d), străzile cu sens unic⁠(d), ș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[modificare | modificare sursă]

  • 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 problema comis-voiajorului cu bottleneck⁠(d) (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.[9]
  • Problema comis-voiajorului generalizată⁠(d) 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 Cutting stock problem⁠(d) cu scopul de a minimiza schimbările de cuțit. O alta implică operația de găurire la fabricarea semiconductorilor, vezi și U.S. Patent 7054798. 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 matricii de distanțe⁠(d).
  • 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[modificare | modificare sursă]

PCV poate fi formulată ca o problemă de programare liniară⁠(d).[10][11][12] 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:

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  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  pentru orice subdrum de k pași care nu trece prin orașul 1, obținem:

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 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  dacă orașul i este vizitat în pasul t (i, t = 1, 2, ..., n). Atunci

deoarece poate fi mai mare decât n și poate fi nu mai mic decât 1; prin urmare, constrângerile sunt îndeplinite ori de câte ori Pentru , avem:

care satisface constrângerile.

Calculul unei soluții[modificare | modificare sursă]

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

  • Elaborarea de algoritmi exacți⁠(d), care lucrează destul de repede doar pentru probleme de mici dimensiuni.
  • Elaborarea de algoritmi euristici⁠(d) (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[modificare | modificare sursă]

Cea mai directă soluție ar încercarea tuturor permutărilor (combinații ordonate) și a vedea care cea este mai ieftină (folosind metoda de căutare cu forța brută⁠(d)). Timpul de rulare pentru această abordare este într-un factor polinomial de , 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 programării dinamice⁠(d) este algoritmul Held-Karp⁠(d), care rezolvă problema în timp .[13]

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 .[14]

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 branch-and-bound⁠(d) și branch-and-cut⁠(d)[15]; 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 Applegate et al. (2006).

O soluție exactă pentru 15.112 de localități germane din TSPLIB a fost găsită în 2001 cu ajutorul metodei planului secant⁠(d) propusă de George Dantzig, Ray Fulkerson⁠(d) și Selmer M. Johnson⁠(d) î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 Princeton[necesită citare] Timpul total de calcul a fost echivalent cu 22,6 ani pe un singur procesor Alpha⁠(d) 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.[16] În martie 2005, problema comis-voiajorului de vizitare a tuturor celor 33.810 de puncte dintr-un circuit a fost rezolvată cu ajutorul Concorde TSP Solver⁠(d): 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 Applegate et al. (2006).

Algoritmi euristici și aproximativi[modificare | modificare sursă]

S-au conceput diverse euristici⁠(d) și algoritmi de aproximare⁠(d), 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[modificare | modificare sursă]

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

Algoritmul „cel mai apropiat vecin⁠(d)” (Nearest Neighbor, NN; un algoritm greedy⁠(d)) 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 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.[17] 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.

rDrumul bitonic⁠(d) al unei mulțimi de puncte este poligonul monoton⁠(d) de perimetru minim care are punctele în nodurile sale; acesta poate fi calculat în mod eficient prin programare dinamică⁠(d).

O altă euristică constructivă⁠(d), Match Twice and Stitch (MTS) (Kahng, Reda 2004 [18]), efectuează două cuplaje⁠(d) 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[modificare | modificare sursă]

Algoritmul lui Christofides⁠(d) urmează un profil similar, dar combină arborele minim de acoperire cu o soluție a unei alte probleme, cuplajul perfect⁠(d) 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 algoritmi de aproximare⁠(d), ș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 .

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ă[modificare | modificare sursă]

Schimbul pe perechi
Schimbul pe perechi, sau tehnica 2-opt⁠(d),  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⁠(d), 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⁠(d) pentru a reoptimiza soluțiile de traseu.[19]

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 2oraș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 Brian Kernighan⁠(d) ș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 căutare tabu⁠(d) și calcul evoluționist⁠(d). 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⁠(d) 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[modificare | modificare sursă]

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, recoacerea simulată⁠(d), căutarea tabu⁠(d), algoritmul optimizat al coloniei de furnici⁠(d), dinamica formării râurilor (vezi inteligență de „roi”) și metoda entropiei încrucișate⁠(d).

Optimizarea cu colonie de furnici[modificare | modificare sursă]

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 simulare a unei colonii de furnici⁠(d) numită ACS (Ant Colony System).[20] Ea modelează comportamentul, observat la furnicile adevărate, de a găsi scurtături între sursele de hrană și cuibul lor, un comportament emergent⁠(d) 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.

Aco TSP.svg
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[modificare | modificare sursă]

PCV metrică[modificare | modificare sursă]

Î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ă⁠(d) 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:

.

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⁠(d) sau metrica cvartalului.
  • În metrica maximă⁠(d), 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  este înlocuită de cel mai scurt drum între A și B în graful inițial.

PCV euclidiană[modificare | modificare sursă]

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ă.[21] Cu coordonate raționale și metrică euclidiană reală, PCV euclidiană este cunoscută a fi în Ierarhia de Numărare,[22] 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.[23] De exemplu, arborele minim de acoperire al grafului asociat cu o instanță de PCV euclidiană este un arbore minim de acoperire euclidian⁠(d), ș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

Aceasta se numește schema de aproximare în timp polinomial⁠(d) (PTAS).[24] Sanjeev Arora⁠(d) și Joseph S. B. Mitchell⁠(d) 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ă[modificare | modificare sursă]

Î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ă[modificare | modificare sursă]

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.[25]

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[modificare | modificare sursă]

Există o problemă similară în teoria geometrică a măsurii⁠(d) care cere următoarele: în ce condiții poate o submulțime E a spațiului euclidian să fie cuprinsă într-o curbă rectificabilă⁠(d) (adică: când există o curbă cu lungime finită care vizitează fiecare punct din E)? Această problemă este cunoscută ca problema comis-voiajorului pentru analist⁠(d).

Lungimea căii PCV pentru mulțimi aleatoare de puncte într-un pătrat[modificare | modificare sursă]

Se presupune că sunt  variabile aleatoare independente cu distribuție uniformă în pătratul  și fie  lungimea căii celei mai scurte (adică soluția PCV) pentru această mulțime de puncte, conform distanței Euclidiene standard. Se știe[26] că, aproape sigur,

unde  este o constantă pozitivă care nu este cunoscută în mod explicit. Deoarece (a se vedea mai jos), rezultă din teorema convergenței dominate că , prin urmare, limitele inferioară și superioară ale lui  rezultă din limitele lui .

Limita aproape sigură când  nu poate exista dacă locațiile independente  sunt înlocuite cu observații dintr-un proces ergodic staționar cu marginali uniformi.[27]

Limita superioară[modificare | modificare sursă]

  • Avem  și, prin urmare, , prin utilizarea unei căi naive care vizitează monoton punctele din interiorul fiecăreia din cele  felii de lățime  din pătrat.
  • Few [28] a demonstrat că , prin urmare, , rezultat ulterior îmbunătățit de către Karloff (1987): .
  • În prezent [29] cea mai bună limită superioară este .

Limita inferioară[modificare | modificare sursă]

  • Observând că este mai mare decât de  ori distanța între și cel mai apropiat punct , se obține (după un scurt calcul)
  • O limită inferioară mai bună se obține[26] observând că este mai mare decât înmulțit cu suma distanțelor între și cel mai apropiat și al doilea cel mai apropiat punct , care dă
  • Actualmente  cea mai bună limită inferioară este
  • Held și Karp[30] au dat un algoritm în timp polinomial care oferă limite inferioare numerice pentru și, astfel, pentru care pare să fie bun până la circa 1%.[31] În special, David S. Johnson[32] a obținut o limită inferioară prin experiment rulat pe calculator:

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 [33] au obținut următoarea limită inferioară numerică:

.

Complexitatea[modificare | modificare sursă]

Problema a fost demonstrată a fi NP-dificilă (mai precis, este completă pentru clasa de complexitate FPNP), ș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[modificare | modificare sursă]

În cazul general, găsirea celui mai scurt drum al comis-voiajorului este NPO⁠(d)-completă.[34] Dacă măsura distanței de măsură este o metrică și simetrică, problema devine APX⁠(d)-completă[35] și algoritmul lui Christofides⁠(d) o aproximează într-o marjă de 1.5.[36] Cea mai cunoscut limită de inaproximabilitate este 123/122 .[37]

Dacă distanțele sunt limitate la 1 și 2 (dar încă metrice) raportul de aproximare devine 8/7.[38] Î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);[39] 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.[40] Dacă funcția de distanță este simetrică, cel mai lung drum poate fi aproximat în 4/3 printr-un algoritm determinist[41] și în printr-un algoritm randomizat.[42]

Performanța umană pe PCV[modificare | modificare sursă]

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.[43] 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.[44] Primul număr al Journal of Problem Solving a fost dedicat subiectului performanței umană pe PCV,[45] și o revizuire din 2011 a enumerat zeci de lucrări pe această temă.

Calculul natural[modificare | modificare sursă]

Atunci când i se prezintă o configurație spațială a surselor de alimentare, amoeboidul⁠(d) Physarum polycephalum⁠(d) îș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.[46] Se consideră că prezintă posibilități interesante și a fost studiată în domeniul calculului natural⁠(d).

Teste de referință[modificare | modificare sursă]

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ă[modificare | modificare sursă]

  • 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.[47][48]
  • 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.[49]

Note[modificare | modificare sursă]

  1. ^ Vezi PCV cu turul mondial deja rezolvată cu o aproximație de 0,05% de soluția optimă. [1]
  2. ^ "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)
  3. ^ O discuție despre primele lucrări ale lui Hamilton și Kirkman se poate găsi în Graph Theory 1736–1936
  4. ^ După varianta în limba engleză din Schrijver (2005). Originalul în germană: „Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."
  5. ^ editat de E.L. Lawler ... [et al.] (1985). The Traveling salesman problem: a guided tour of combinatorial optimization (ed. Repr. cu corecturi.). Chichester [West Sussex]: Wiley. ISBN 0471904139 
  6. ^ 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 Alexander Schrijver⁠(d) din 2005 „On the history of combinatorial optimization (till 1960)”.
  7. ^ Klarreich, Erica. „Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem”. Simons Science News. https://www.wired.com/2013/01/traveling-salesman-problem/. Accesat la 14 iunie 2015. 
  8. ^ Rego, César; Gamboa, Dorabela; Glover, Fred; Osterman, Colin (2011), „Traveling salesman problem heuristics: leading methods, implementations and latest advances”, European Journal of Operational Research 211 (3): 427–441, doi:10.1016/j.ejor.2010.09.010 .
  9. ^ Behzad, Arash; Modarres, Mohammad (2002), „New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem”, Proceedings of the 15th International Conference of Systems Engineering (Las Vegas) 
  10. ^ Papadimitriou, C.H.; Steiglitz, K. (1998), Combinatorial optimization: algorithms and complexity, Mineola, NY: Dover , pp.308-309.
  11. ^ Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)
  12. ^ Dantzig, George B. (1963), Linear Programming and Extensions, Princeton, NJ: PrincetonUP, pp. 545–7, ISBN 0-691-08000-3, a șasea tipărire, 1974.
  13. ^ Bellman (1960), Bellman (1962), Held & Karp (1962)
  14. ^ Woeginger (2003)
  15. ^ Padberg & Rinaldi (1991)
  16. ^ Lucrare de David Applegate, AT&T Labs – Research, Robert Bixby, ILOG⁠(d) și Rice University, Vašek Chvátal, Concordia University, William Cook, Universitatea din Waterloo, și Keld Helsgaun, Roskilde University discutată pe pagina web a proiectului lor găzduit la Universitatea din Waterloo și actualizată ultima oară în iunie 2004, aici
  17. ^ Ray, S. S.; Bandyopadhyay, S.; Pal, S. K. (2007). „Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering”. Applied Intelligence 26 (3): 183–195. doi:10.1007/s10489-006-0018-y. 
  18. ^ Kahng, A. B.; Reda, S. (2004). „Match Twice and Stitch: A New TSP Tour Construction Heuristic”. Operations Research Letters 32 (6): 499–509. doi:10.1016/j.orl.2004.04.001. 
  19. ^ Johnson, D. S.; McGeoch, L. A. (1997). „The Traveling Salesman Problem: A Case Study in Local Optimization”. în Aarts, E. H. L.; Lenstra, J. K.. Local Search in Combinatorial Optimisation. London: John Wiley and Sons Ltd. pp. 215–310. https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf 
  20. ^ Marco Dorigo. "Ant Colonies for the Traveling Salesman Problem. IRIDIA, Université Libre de Bruxelles. IEEE Transactions on Evolutionary Computation, 1(1):53–66. 1997. http://citeseer.ist.psu.edu/86357.html
  21. ^ Papadimitriou (1977).
  22. ^ Allender et al. (2007)
  23. ^ Larson & Odoni (1981)
  24. ^ Arora (1998).
  25. ^ Jonker, Roy; Volgenant, Ton. „Transforming asymmetric into symmetric traveling salesman problems”. Operations Research Letters 2 (161–163): 1983. doi:10.1016/0167-6377(83)90048-2. 
  26. ^ a b Beardwood, Halton & Hammersley (1959)
  27. ^ Arlotto, Alessandro; Steele, J. Michael (2016), „Beardwood–Halton–Hammersley theorem for stationary ergodic sequences: a counterexample”, The Annals of Applied Probability 26 (4): 2141–2168, doi:10.1214/15-AAP1142 
  28. ^ Few, L. (1955). „The shortest path and the shortest road through n points”. Mathematika 2 (02): 141–144. doi:10.1112/s0025579300000784. 
  29. ^ Steinerberger, S. (2015). „New bounds for the traveling salesman constant”. Advances in Applied Probability 47.1. 
  30. ^ Held, M.; Karp, R.M. (1970). „The Traveling Salesman Problem and Minimum Spanning Trees”. Operations Research 18: 1138–1162. doi:10.1287/opre.18.6.1138. 
  31. ^ Goemans, M.; Bertsimas, D. (1991). „Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem”. Mathematics of operation research 16 (1): 72–89. doi:10.1287/moor.16.1.72. 
  32. ^ David S. Johnson
  33. ^ Christine L. Valenzuela and Antonia J. Jones
  34. ^ Orponen (1987)
  35. ^ Papadimitriou (1983)
  36. ^ Christofides (1976)
  37. ^ Karpinski, Lampis & Schmied (2015)
  38. ^ Berman & Karpinski (2006).
  39. ^ Kaplan (2004)
  40. ^ Kosaraju (1994)
  41. ^ Serdyukov (1984)
  42. ^ Hassin (2000)
  43. ^ Macgregor, J. N.; Ormerod, T. (1 iunie 1996), „Human performance on the traveling salesman problem”, Perception & Psychophysics 58 (4): 527–539, doi:10.3758/BF03213088 .
  44. ^ MacGregor, James N.; Chu, Yun (2011), „Human performance on the traveling salesman and related problems: A review”, Journal of Problem Solving 3 (2), https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1090&context=jps .
  45. ^ Journal of Problem Solving 1(1), 2006, retrieved 2014-06-06.
  46. ^ Jones, Jeff; Adamatzky, Andrew (2014), „Computation of the travelling salesman problem by a shrinking blob”, Natural Computing: 2, 13, http://www.phychip.eu/wp-content/uploads/2013/03/Computation-of-the-travelling-salesman-problem-by-a-shrinking-blob.pdf 
  47. ^ Racy read”. 7 decembrie 2014. http://www.thehindu.com/books/literary-review/racy-read/article6667634.ece. Accesat la 30 aprilie 2016. 
  48. ^ Crime in a World of High Science”. 16 septembrie 2014. http://www.newindianexpress.com/cities/bengaluru/Crime-in-a-World-of-High-Science/2014/09/16/article2432584.ece. Accesat la 30 aprilie 2016. 
  49. ^ Geere, Duncan. „'Travelling Salesman' movie considers the repercussions if P equals NP”. Wired. http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman. Accesat la 26 aprilie 2012. 

Bibliografie[modificare | modificare sursă]

  • Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J. (2006), The Traveling Salesman Problem, ISBN 0-691-12993-2 .
  • Allender, Eric; Bürgisser, Peter; Kjeldgaard-Pedersen, Johan; Mitersen, Peter Bro (2007), „On the Complexity of Numerical Analysis”, SIAM J. Comput. 38 (5), doi:10.1137/070697926, http://www-math.uni-paderborn.de/agpb//work/submitted.july.pdf .
  • Arora, Sanjeev (1998), „Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, Journal of the ACM 45 (5): 753–782, doi:10.1145/290179.290180 .
  • Beardwood, J.; Halton, J.H.; Hammersley, J.M. (1959), „The Shortest Path Through Many Points”, Proceedings of the Cambridge Philosophical Society 55: 299–327, doi:10.1017/s0305004100034095 .
  • Bellman, R. (1960), „Combinatorial Processes and Dynamic Programming”, în Bellman, R.; Hall, M. Jr., Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10,, American Mathematical Society, pp. 217–249 .
  • Bellman, R. (1962), „Dynamic Programming Treatment of the Travelling Salesman Problem”, J. Assoc. Comput. Mach. 9: 61–63, doi:10.1145/321105.321111 .
  • Berman, Piotr; Karpinski, Marek (2006), „8/7-approximation algorithm for (1,2)-TSP”, Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA '06), pp. 641–648, doi:10.1145/1109557.1109627, Format:ECCC, ISBN 0898716055 .
  • Christofides, N. (1976), Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh .
  • Hassin, R.; Rubinstein, S. (2000), „Better approximations for max TSP”, Information Processing Letters 75 (4): 181–186, doi:10.1016/S0020-0190(00)00097-1 .
  • Held, M.; Karp, R. M. (1962), „A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial and Applied Mathematics 10 (1): 196–210, doi:10.1137/0110015 .
  • Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), „Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs”, In Proc. 44th IEEE Symp. on Foundations of Comput. Sci, pp. 56–65 .
  • Karpinski, M.; Lampis, M.; Schmied, R. (2015), „New Inapproximability bounds for TSP”, Journal of Computer and System Sciences 81 (8): 1665–1677, doi:10.1016/j.jcss.2015.06.003 
  • Kosaraju, S. R.; Park, J. K.; Stein, C. (1994), „Long tours and short superstrings'”, Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci, IEEE Computer Society, pp. 166–177 .
  • Orponen, P.; Mannila, H. (1987), „On approximation preserving reductions: Complete problems and robust measures'”, Technical Report C-1987–28, Department of Computer Science, University of Helsinki .
  • Larson, Richard C.; Odoni, Amedeo R. (1981), „6.4.7: Applications of Network Models § Routing Problems §§ Euclidean TSP”, Urban Operations Research, Prentice-Hall, ISBN 9780139394478, OCLC 6331426, http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.7.html .
  • Padberg, M.; Rinaldi, G. (1991), „A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems”, Siam Review: 60–100, doi:10.1137/1033004 .
  • Papadimitriou, Christos H. (1977), „The Euclidean traveling salesman problem is NP-complete”, Theoretical Computer Science 4 (3): 237–244, doi:10.1016/0304-3975(77)90012-3 .
  • Papadimitriou, C. H.; Yannakakis, M. (1993), „The traveling salesman problem with distances one and two”, Math. Oper. Res. 18: 1–11, doi:10.1287/moor.18.1.1 .
  • Serdyukov, A. I. (1984), „An algorithm with an estimate for the traveling salesman problem of the maximum'”, Upravlyaemye Sistemy 25: 80–86 .
  • Steinerberger, Stefan (2015), „New Bounds for the Traveling Salesman Constant”, Advances in Applied Probability 47 .
  • Woeginger, G.J. (2003), „Exact Algorithms for NP-Hard Problems: A Survey”, Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570, Springer, pp. 185–207 .

Lectură suplimentară[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]