Călătorind problemă agent de vânzări (angl.Travellingsalesmanproblem, FTS) (agent de vânzări - comis-voiajor) - una dintre cele mai cunoscute probleme de optimizare combinatorie, este de a găsi cea mai profitabilă rută care trece prin oras a spus cel puțin o dată și apoi să se întoarcă în oraș originală. În contextul problemei indică rentabilitatea criteriilor de traseu (cel mai scurt, mai ieftine, set de criterii, și altele asemenea) și matricea distanță corespunzătoare, costul și altele asemenea. De regulă, se indică faptul că traseul trebuie să treacă prin fiecare oraș o singură dată - în acest caz alegerea se face între ciclurile Hamiltonian.
Există mai multe cazuri speciale de formularea generală a problemei, în special, o problemă geometrică de deplasare agent de vânzări (de asemenea, numit planar sau euclidiană când matricea distanța reflectă distanța dintre punctele pe plan), problema metric de deplasare agent de vânzări (atunci când matricea valori inegalitatea triunghiului), simetrică și asimetrică problemă de deplasare vânzător. Există, de asemenea, o generalizare a problemei, așa-numita problemă generalizată a vânzătorilor de călătorii.
Formularea optimizării problemei aparține clasei problemelor NP-hard, totuși, ca majoritatea cazurilor sale particulare. Versiunea «problemă de decizie» (adică, una în care întrebarea este dacă există o cale nu este mai mică decât o valoare predeterminată k) aparține clasei de probleme NP-complete. Călătorind problemă agent de vânzări este unul transvychislitelnyh: deja la un număr relativ mic de orașe (66 sau mai mult), nu poate fi rezolvată prin forță brută orice variante teoretic imaginabile ale calculatoarelor, în mai puțin de câteva miliarde de ani.
O condiție indispensabilă și singura semnificație a problemei vânzătorului care călătorește este găsirea celui mai profitabil mod. Pentru a face acest lucru, este necesar să găsim și să descriem toate căile posibile în oricare dintre variantele căilor de găsire a unei soluții. Dacă nu calculam toate căile din varianta de soluție aleasă, atunci nu putem spune că soluția găsită este cea mai profitabilă. Ce este o verificare a soluției? - aceasta este o căutare a unei erori în procesul decizional sau o reconciliere a rezultatului cu ceea ce se știe a fi corect. A doua opțiune este abandonată temporar, deoarece nu există nici un sens practic în rezolvarea problemei, în cazul în care există deja o decizie (la rândul său, utilizarea anterior a luat decizia corectă pentru partea a problemei existente - o modalitate de a reduce decizia). Ca parte a acestei lucrări nu vizează să compare diferitele metode și modalități de soluții, astfel încât să presupunem că examinatorul consideră, de asemenea, calea aleasă de soluții optime și verifică-l pentru corectitudine. Ce ar trebui să facă inspectorul? - Repetați lucrul efectuat în timpul deciziei, în volum maxim, pentru a găsi eroarea la fiecare etapă de decizie. Dacă se găsește o eroare, inspectorul va trebui să continue procesul decizional pentru a găsi un traseu mai profitabil. Astfel, obținem că testul soluției problemei vânzătorului călător este egal sau mai mare decât soluția însăși.
Reprezentare sub forma unui grafic.
Problemă simetrică pentru patru orașe.
Pentru posibilitatea utilizării unui aparat matematic pentru a rezolva o problemă, el trebuie prezentat sub forma unui model matematic. Problema unui vânzător poate fi prezentată sub forma unui model pe grafic, adică folosind vârfuri și muchii între ele. Astfel, vârfurile graficului corespund orașelor, iar marginile (i, j) între vârfurile i și j sunt căile de comunicație dintre aceste orașe. Fiecare margine (i, j)> = 0 poate fi comparată cu criteriul avantajului rutei, care poate fi înțeleasă ca, de exemplu, distanța dintre orașe, timpul sau costul călătoriei. O rută (și o rută Hamiltoniană) este o rută pe un astfel de grafic, în care fiecare vârf al graficului intră o dată. Sarcina este de a găsi cel mai scurt traseu.
Pentru a simplifica sarcina și a garanta existența unei rute, se presupune de obicei că graficul model al problemei este complet conectat, adică există o margine între o pereche arbitrară de vârfuri. În cazurile în care nu există un mesaj între orașele individuale, acest lucru se poate realiza prin introducerea marginilor cu lungimea maximă. Din cauza lungimii mari, o astfel de margine nu va ajunge niciodată pe traseul optim, dacă există.
În funcție de criteriul de avantaj al rutei, marimea marginii este comparată, se disting diferite versiuni ale problemei, dintre care cele mai importante sunt probleme simetrice și metrice.
Un exemplu de rezolvare a unei probleme de vânzător care călătorește în Python pe un grafic dat (Figura 3.2).
Lista 2 prezintă un script pentru rezolvarea acestei probleme.
Acest script găsește calea cea mai "profitabilă" de la vârful 1 la punctul 4.
