![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/11/GLPK_solution_of_a_travelling_salesman_problem.svg/langro-640px-GLPK_solution_of_a_travelling_salesman_problem.svg.png&w=640&q=50)
Problema comis-voiajorului
From Wikipedia, the free encyclopedia
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 optimizarea combinatorie(d), cu importanță în cercetarea operațională(d) și în informatica teoretică(d).
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/GLPK_solution_of_a_travelling_salesman_problem.svg/320px-GLPK_solution_of_a_travelling_salesman_problem.svg.png)
PCV este un caz special al problemei cumpărătorului ambulant(d) ș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 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 test 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] 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.