Problema vânzătorului ambulant

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 28 iunie 2022; verificările necesită 7 modificări .

Problema travelling salesman (sau TSP din engleza traveling salesman problem ) este una dintre cele mai cunoscute probleme de optimizare combinatorie , care constă în găsirea rutei celei mai profitabile trecând prin orașele specificate cel puțin o dată și apoi întoarcerea în orașul original. În condițiile problemei, sunt indicate criteriul de rentabilitate a rutei (cel mai scurt, cel mai ieftin, criteriul cumulativ etc.) și matricele corespunzătoare de distanțe, costuri și altele asemenea. De regulă, se indică faptul că traseul ar trebui să treacă prin fiecare oraș o singură dată - în acest caz, alegerea se face între ciclurile hamiltoniene . Există mai multe cazuri speciale de formulare generală a problemei, în special, problema vânzătorului călător geometric (numită și plană sau euclidiană, când matricea distanțelor reflectă distanțele dintre punctele din plan), problema vânzătorului călător metric (când inegalitatea triunghiulară este satisfăcută pe matricea costurilor ), probleme simetrice și asimetrice ale vânzătorului ambulant . Există, de asemenea, o generalizare a problemei, așa-numita problemă generalizată a vânzătorului ambulant .

Declarația problemei de optimizare aparține clasei de probleme NP-hard, totuși, ca majoritatea cazurilor sale particulare. Versiunea „problemei de decizie” (adică cea care întreabă dacă există o rută nu mai lungă de o valoare dată a lui k ) aparține clasei de probleme NP-complete . Problema vânzătorului ambulant este una dintre problemele de transcomputing : chiar și cu un număr relativ mic de orașe (> 66), nu poate fi rezolvată prin metoda enumerarii opțiunilor de către orice computere teoretic concepute într-un timp mai mic de câteva miliarde de ani.

Istorie

Legat de problema vânzătorului ambulant este problema găsirii unui ciclu hamiltonian . Un exemplu de astfel de problemă este problema mișcării cavalerului , cunoscută cel puțin încă din secolul al XVIII-lea [1] . Leonhard Euler i-a dedicat o mare lucrare „Soluția unei întrebări curioase, care pare să nu facă obiectul niciunei cercetări”, din 1759 [2] . Un alt exemplu de problemă pentru găsirea unui ciclu hamiltonian este icosianul : un puzzle matematic în care trebuie să parcurgeți un dodecaedru (un grafic cu 20 de noduri) vizitând fiecare vârf exact o dată. Această problemă a fost propusă de William Hamilton în secolul al XIX-lea, el a definit și o clasă de astfel de căi.

În 1832, a fost publicată o carte cu titlul „Vânzător călător - cum ar trebui să se comporte și ce ar trebui să facă pentru a livra mărfuri și a avea succes în treburile sale - sfat de la un vechi curier” ( germană: 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 ), care descrie problema, dar nu folosește aparatul matematic pentru a o rezolva. Dar oferă exemple de rute pentru unele regiuni din Germania și Elveția.

Primele mențiuni ca problemă de optimizare matematică îi aparțin lui Carl Menger , care a formulat-o la un colocviu matematic în 1930 astfel:

Numim problema mesagerului (deoarece această întrebare apare pentru fiecare poștaș, în special, mulți călători o rezolvă) problema găsirii celei mai scurte căi între un set finit de locuri, distanța dintre care este cunoscută.

Curând a apărut numele binecunoscut al problemei vânzătorului ambulant , care a fost propus de Hassler Whitney de la Universitatea Princeton .

Alături de ușurința de definire și relativă ușurință de a găsi soluții bune, problema vânzătorului ambulant este diferită prin aceea că găsirea unei căi cu adevărat optime este o sarcină destul de dificilă. Având în vedere aceste proprietăți, începând din a doua jumătate a secolului al XX-lea, studiul problemei vânzătorului ambulant are nu atât sens practic, cât teoretic, ci un model pentru dezvoltarea de noi algoritmi de optimizare.

Multe dintre metodele obișnuite de optimizare discretă de astăzi , cum ar fi cutoff , branch și bound , și diverse variante de algoritmi euristici, au fost dezvoltate folosind problema vânzătorului ambulant ca exemplu.

În anii 1950 și 1960, problema vânzătorului ambulant a atras atenția oamenilor de știință din Statele Unite și Europa. O contribuție importantă la studiul problemei aparține lui George Danzig , Delbert Ray Fulkerson ( ing. Delbert Ray Fulkerson ) și Selmer Johnson ( ing. Selmer M. Johnson ), care în 1954 la institutul RAND Corporation au formulat problema sub forma a unei probleme de optimizare discretă și aplicată acesteia rezolvând metoda cut-off . Folosind această metodă, au construit calea unui vânzător ambulant pentru o anumită declarație de problemă cu 49 de orașe și au fundamentat optimitatea acesteia. În anii 1960 și 1970, problema a fost studiată de mulți oameni de știință atât teoretic, cât și în ceea ce privește aplicațiile sale în informatică, economie, chimie și biologie.

Richard Karp în 1972 a demonstrat completitatea NP a problemei găsirii căilor hamiltoniene, care, datorită reducebilității polinomiale, a implicat duritatea NP a problemei vânzătorului ambulant. Pe baza acestor proprietăți, el a dat o justificare teoretică a complexității de a găsi soluții la problemă în practică.

Mari succese au fost obținute la sfârșitul anilor 1970 și 1980, când Martin Grötschel ( german Martin Grötschel ), Manfred Padberg ( german Manfred Padberg ) și Giovanni Rinaldi ( italian Giovanni Rinaldi ) și alții, folosind noi metode de divizare plan, ramuri și limite au calculat soluția pentru un caz particular al problemei cu 2393 de orașe.

În anii 1990, David Applegate , Robert Bixby , Vašek Chvátal și William Cook au stabilit recorduri pentru programul Concorde . Gerhard Reinelt ( german Gerhard Reinelt ) a creat TSPLIB - un set de exemple standardizate ale problemei vânzătorului ambulant de diferite grade de complexitate pentru a compara rezultatele muncii diferitelor grupuri de cercetători. În martie 2005, o problemă cu 33.810 noduri a fost rezolvată prin programul Concord : a fost calculată o cale cu lungimea de 66.048.945 și s-a dovedit absența căilor mai scurte. În aprilie 2006 , a fost găsită o soluție pentru o instanță cu 85.900 de noduri. Folosind metode de descompunere , este posibil să se calculeze soluții pentru cazurile unei probleme cu milioane de noduri, a căror lungime este cu mai puțin de 1% mai mare decât cea optimă.

Definiție formală

Reprezentare grafică

Pentru a putea folosi aparatul matematic pentru a rezolva problema, aceasta ar trebui prezentată sub forma unui model matematic . Problema vânzătorului ambulant poate fi reprezentată ca model pe un grafic , adică folosind vârfuri și muchii dintre ele. Astfel, vârfurile graficului corespund orașelor, iar muchiile dintre vârfuri corespund căilor de comunicație dintre aceste orașe. Fiecare margine poate fi asociată cu un criteriu de rentabilitate a rutei , care poate fi înțeles ca, de exemplu, distanța dintre orașe, timpul sau costul călătoriei. $\left(i,j\dreapta)$ $i$ $j$ $\left(i,j\dreapta)$ $c_{ij}\geqslant 0$

Un ciclu hamiltonian este o cale care include exact o dată fiecare vârf al graficului.

Pentru a simplifica problema și a garanta existența unei rute, se presupune de obicei că graficul model al problemei este complet conectat , adică că există o muchie între o pereche arbitrară de vârfuri. În cazurile în care nu există comunicare între orașe individuale, acest lucru se poate realiza prin introducerea de margini cu o lungime maximă. Datorită lungimii mari, o astfel de margine nu va cădea niciodată în traseul optim, dacă există.

Astfel, soluția problemei vânzătorului ambulant este de a găsi ciclul hamiltonian al greutății minime într-un grafic ponderat complet .

În funcție de criteriul de rentabilitate al traseului comparat cu dimensiunea muchiilor, există diferite versiuni ale problemei, dintre care cele mai importante sunt problemele simetrice și metrice.

Probleme asimetrice și simetrice

În general, problema vânzătorului călător asimetric diferă prin faptul că este modelată printr-un grafic direcționat. Astfel, ar trebui să luați în considerare și direcția în care se află marginile.

În cazul unei probleme simetrice, toate perechile de muchii dintre aceleași vârfuri au aceeași lungime, adică lungimile muchiei sunt aceleași . În cazul simetric, numărul de rute posibile este jumătate din cel al cazului asimetric. Problema simetrică este modelată printr-un grafic nedirecționat (vezi figura). $\left(i,j\dreapta)$ $c_{ij}=c_{ji}$

De altfel, problema vânzătorului ambulant în cazul orașelor reale poate fi atât simetrică, cât și asimetrică, în funcție de durata sau lungimea traseelor și de direcția de mișcare.

Problemă metrică

O problemă simetrică de vânzător ambulant se numește metrică dacă inegalitatea triunghiului este satisfăcută în raport cu lungimile muchiilor . Relativ vorbind, în astfel de probleme, ocolirile sunt mai lungi decât liniile drepte, adică muchia de la vârf la vârf nu este niciodată mai lungă decât calea prin vârful intermediar : $i$ $j$ $k$

c_{ij}\leqslant c_{ik}+c_{kj}

Această proprietate a lungimii marginii definește un spațiu măsurabil pe setul de margini și o măsură a distanței care satisface înțelegerea intuitivă a distanței.

Funcțiile de distanță comune în practică sunt, de asemenea, metrici și satisfac inegalitatea triunghiului:

Distanța euclidiană în problema vânzătorului ambulant euclidian,
Metrica Manhattan (de asemenea metrica trimestrială) a problemei vânzătorului ambulant dreptunghiular, în care distanța dintre vârfurile de pe rețea este egală cu suma distanțelor de-a lungul axei y și a abscisei,
Metrica maximă care definește distanța dintre vârfurile unui grafic reticulat ca fiind valoarea maximă a distanței de-a lungul ordonatei și abscisei.

Ultimele două metrici sunt utilizate, de exemplu, la găuri în plăcile cu circuite imprimate, când mașina trebuie să facă mai multe găuri în cel mai scurt timp și poate deplasa burghiul în ambele direcții pentru a trece de la o gaură la alta. Metrica Manhattan corespunde cazului în care mișcarea în ambele direcții are loc secvențial, iar maximul corespunde cazului în care mișcarea în ambele direcții are loc sincron, iar timpul total este egal cu timpul maxim al mișcării de-a lungul axei ordonatelor sau absciselor.

Problema nemetrică a vânzătorului ambulant poate apărea, de exemplu, în cazul minimizării duratei de ședere în prezența unei alegeri de vehicule în direcții diferite. Într-un astfel de caz, ocolul pe calea aerului poate fi mai scurt decât legătura directă cu mașina.

Dacă în practică, în condițiile problemei, este permisă vizitarea orașelor de mai multe ori, atunci problema simetrică poate fi redusă la una metrică. Pentru aceasta, problema este luată în considerare pe așa-numitul grafic de distanță. Acest grafic are același set de vârfuri ca și cel original și este complet conectat. Lungimea muchiilor dintre vârfuri și pe graficul distanțelor corespunde cu lungimea celei mai scurte distanțe dintre vârfuri și în graficul original. Pentru lungimile definite în acest fel , inegalitatea triunghiului este valabilă și fiecare rută de pe graficul distanței corespunde întotdeauna unei rute cu posibile repetiții de vârfuri în graficul original. $c_{ij}$ $i$ $j$ $i$ $j$ $c_{ij}$

Formularea ca problemă de optimizare discretă

Una dintre abordările de rezolvare a problemei este formularea acesteia ca o problemă de optimizare discretă, cu soluțiile reprezentate ca variabile, iar conexiunile ca relații de inegalitate între ele. Astfel, sunt posibile mai multe opțiuni. De exemplu, o problemă simetrică poate fi reprezentată ca un set de muchii . Fiecărei muchii i se atribuie o variabilă binară , egală cu 1 dacă muchia aparține traseului și 0 în caz contrar. O rută arbitrară poate fi reprezentată ca valori ale unui set de variabile de membru, dar nu fiecare astfel de set definește o rută. Condiția ca valorile setului de variabile să determină traseul sunt inegalitățile liniare descrise mai jos. $V$ $\{i,j\}$ $x_{ij}\in \{0,1\}$

Fiecare vârf trebuie să comunice printr-o pereche de muchii cu restul vârfurilor, adică prin muchiile de intrare și de ieșire:

\forall i\in V,\;\sum _{j\in V\setminus \{i\}}x_{ij}=2\qquad (1)

În total, fiecare termen este egal fie cu 1 (aparține rutei), fie cu 0 (nu aparține). Adică, suma rezultată este egală cu numărul de muchii din traseu care au un vârf la unul dintre capete. Este egal cu 2, deoarece fiecare vârf are o muchie de intrare și de ieșire. În figura alăturată, vârful este afișat cu muchii de intrare și de ieșire, iar muchiile de traseu sunt afișate ca linii groase. Lângă coaste sunt lungimile aplicate la cantitatea de mai sus. $x_{ij}$ $i$ $i$ $x_{ij}$

Condițiile de multiplicitate descrise mai devreme sunt îndeplinite nu numai de rute, ci și de valorile variabilelor corespunzătoare ciclurilor individuale, în care fiecare vârf aparține unui singur ciclu (vezi figura). Pentru a evita astfel de cazuri, așa-numitele inegalități de buclă (sau condiții de eliminare a subrutei), care au fost definite de Danzig, Fulkerson și Johnson în 1954 sub numele de condiții de buclă , trebuie îndeplinite . Aceste inegalități au definit o condiție suplimentară ca fiecare set de vârfuri fie să fie gol, fie să conțină toate vârfurile, combinate cu restul vârfurilor prin cel puțin două muchii: $S\subset V$

\sum _{i\in S,\;j\notin S}x_{ij}\geqslant 2\qquad (2)

pentru toate seturile de vârfuri , unde . Această sumă este egală cu suma lungimilor marginilor căii dintre vârf și vârf . Pentru a elimina inegalitățile inutile, ne putem restrânge la seturi de vârfuri cu un minim de două și un maxim de vârfuri. În figura de lângă ea, marginile cu lungimi sunt marcate cu linii groase, marginile rămase au lungimea . Introducerea unor condiții suplimentare (2) pentru mulțimea de vârfuri , constând din trei vârfuri din stânga, va asigura că acesta este combinat prin cel puțin două muchii de drum cu trei vârfuri în dreapta pentru a elimina ambele cicluri. Numărul de inegalități care elimină ciclul conform lui Danzig, Fulkerson și Johnson este . $S$ $1\leqslant |S|\leqslant |V|-1$ $i\în S$ $j\notin S$ $S$ $|V|-2$ $\{i,j\}$ $x_{ij}=1$ $x_{ij}=0$ $S$ $S$ $2^{n}-2(n-1)$

În 1960, Miller, Tucker și Zemlin au conceput condiții alternative pentru eliminarea subrutelor prin introducerea de noi variabile care specifică ordinea orașelor vizitate, necesitând doar inegalități suplimentare. Mai mult decât atât, datorită dualității din formulările lui Miller, Tucker și Zemlin, problema vânzătorului ambulant rămâne NP-grea. $n$ $n^{2}-n+1$ $x_{ij}$

Astfel, fiecare vector cu elemente egale cu 0 și 1 care satisface toate inegalitățile definește un traseu corect, care este o soluție la problema reformulată a vânzătorului ambulant: calculează

\min \;\left\{\sum _{i\in V}\sum _{j\in V\setminus \{i\}}c_{ij}x_{ij}\;|\;x{\mbox { valid (1) (2),}}\;x_{ij}\in \{0,1\}\right\}.\qquad (3)

Deoarece variabilele au doar valori 0 și 1, suma este egală cu lungimea totală a marginilor aparținând traseului. $x_{ij}$ $c_{ij}$ $\{i,j\}$

Numărul de inegalități de tip (2) crește exponențial pe măsură ce numărul de orașe crește, deoarece aproape fiecare subset de noduri definește o inegalitate. Această problemă poate fi rezolvată prin aplicarea metodei planului de tăiere , datorită căreia inegalitățile sunt adăugate doar atunci când aceste inegalități sunt cu adevărat necesare. Din punct de vedere geometric, inegalitățile liniare pot fi reprezentate ca hiperplane în spațiul variabilelor. Mulțimea vectorilor care satisfac aceste inegalități formează un politop (poliedru multidimensional), sau poligon multidimensional, într-un astfel de spațiu, forma exactă este determinată de lungimi și este în mare parte necunoscută. Cu toate acestea, se poate demonstra că condițiile (1) și (2) determină fețele (fațeta) politopului, adică suprafețele laterale ale politopului cu cea mai mare dimensiune. Prin urmare, ele sunt printre cele mai puternice inegalități liniare care pot descrie o rută. Există, de asemenea, multe fațete diferite definite de inegalități cunoscute doar în câteva cazuri. Deși (1) și (2) împreună cu constrângerile modelează complet problema doar pentru vectorii binari, aceste inegalități pot fi utilizate în metoda ramurilor și legate pentru a elimina soluțiile prin metode de optimizare liniară cu coordonate non-întregi (vezi secțiunea metode exacte de mai jos). $2^{|V|}$ $c_{ij}$

Complexitate algoritmică

Întrucât vânzătorul ambulant din fiecare oraș se confruntă cu alegerea următorului oraș dintre cele pe care nu le-a vizitat încă, există rute pentru problema asimetrică și rute pentru problema vânzător ambulant simetric. Astfel, dimensiunea spațiului de căutare depinde factorial de numărul de orașe. $(n-1)!$ $(n-1)!/2$

Diverse versiuni ale problemei vânzătorului ambulant (metrică, simetrică și asimetrică) sunt echivalente în NP. Conform conjecturii comune, dar nedovedite, despre inegalitatea claselor de complexitate P și NP, nu există o mașină Turing deterministă care să fie capabilă să rezolve instanțe de problemă în timp polinomial în funcție de numărul de orașe.

De asemenea, se știe că în condiția nu există un algoritm care, pentru un polinom, să calculeze astfel de soluții la problema vânzătorului ambulant care să difere de maximul optim cu un factor . $P\neq NP$ $p$ $2^{p(n)}$

În practică, căutarea unui traseu strict optim nu este întotdeauna necesară. Există algoritmi pentru a găsi soluții aproximative la o problemă metrică în timp polinomial și pentru a găsi o rută care este de cel mult de două ori mai lungă decât cea optimă. Până acum nu se cunoaște un algoritm de timp polinomial care să garanteze o precizie mai bună de 1,5 din cea optimă. Prin presupunerea , există o constantă (necunoscută) astfel încât niciun algoritm de timp polinomial nu poate garanta acuratețea . După cum a arătat Arora, pentru problema euclidiană a vânzătorului ambulant, există o schemă PTAS în timp polinomial pentru găsirea unei soluții aproximative. $P\neq NP$ $c>0$ $1+c$

În plus, datele pot avea caracteristici care pot ajuta la rezolvarea problemei. De exemplu, orașele sunt situate nu întâmplător, ci în funcție de teren, sau chiar de-a lungul rutei comerciale optime care a fost găsită de mult. Informațiile suplimentare și euristicile ne permit să găsim soluții acceptabile într-un timp rezonabil.

Variante închise și deschise ale problemei

În versiunea închisă a problemei vânzătorului ambulant, este necesar să vizitați toate vârfurile graficului și apoi să reveniți la vârful original. Varianta deschisă diferă de cea închisă prin faptul că nu necesită revenirea la vârful de pornire.

O versiune deschisă a problemei este redusă la una închisă prin înlocuirea greutăților arcurilor incluse în vârful de pornire cu numărul 0. Ruta optimă închisă de vânzător călători într-un astfel de grafic corespunde rutei deschise optime din graficul original.

Pentru a reduce o variantă închisă la una neînchisă, este necesar să determinați un număr care depășește cu strictețe greutatea oricărui traseu de vânzător ambulant într-un grafic dat (de exemplu, puteți lua suma arcurilor de greutate maxime care ies de la fiecare vârf). , majorat cu 1). Apoi trebuie să adăugați un nou vârf la grafic (presupunem că vârfurile graficului original sunt numerotate de la 0 la , în timp ce vârful de început are numărul 0). Costurile arcurilor care părăsesc și intră în vârf sunt definite după cum urmează: $K$ $K$ $v_{n}$ $n-1$ $v_{n}$

$c_{n,i}=3K$
$c_{0,n}=3K$
$c_{i,n}=c_{i,0}+2K$ la de la până la $i$ $unu$ $n-1$

Ruta optimă de vânzător călători neînchis într-un astfel de grafic corespunde rutei optime de vânzător călători închis din graficul original și are un cost mai mare. $2K$

Metode de rezolvare

Protozoare

căutare exhaustivă
enumerare aleatorie
algoritmi lacomi
- metoda celui mai apropiat vecin
- cea mai apropiată metodă de includere a orașului
- metoda cu cel mai mic cost
metoda arborelui de întindere minim
metoda de recoacere simulata

Toate metodele eficiente (reducerea numărului complet) pentru rezolvarea problemei vânzătorului ambulant sunt metode euristice . Majoritatea metodelor euristice nu găsesc cea mai eficientă rută, ci o soluție aproximativă . Așa-numiții algoritmi oricând sunt adesea solicitați .[ clarifica ] , adică îmbunătățirea treptată a unei soluții aproximative curente.

Un exemplu de cea mai simplă metodă de rezolvare a versiunii metrice a problemei este utilizarea arborilor de acoperire minimă, care oferă o soluție cu un factor de aproximare și are complexitate în timp . Ideea este că fiecare graf conectat conține un prag de cost mai mic pentru subgraful său, arborele de acoperire minim și că orice ciclu care vizitează fiecare vârf de graf cel puțin o dată poate fi transformat într-o rută optimă din punct de vedere al costurilor folosind metrica: $2$ $O(n^{2}\log n)$

Găsiți arborele de acoperire minim al graficului . $T$ $G$
Creați un grafic dublând toate muchiile în . Deci toate vârfurile din au un număr par de muchii. $T'$ $T$ $T'$
Găsiți ciclul Euler . $T'$ $C'$
Reduceți , sărind marginile dublate, obținând un ciclu . $C'$ $C$
Scoate afară . $C$

Valoarea factorului de aproximare se demonstrează astfel: Fie - arborele de întindere minim, - același arbore, dar cu muchii dublate, - ciclul Euler pe grafic , - rezultatul algoritmului, - traseul minim. Rețineți că , la fel și . Atunci factorul de aproximare este . $T$ $T'$ $C'$ $T'$ $C$ $C^{*}$ $c(T)\leqslant c(C^{*}-e)\leqslant c(C^{*})$ $c(C)\leqslant c(C')=2\cdot c(T)$ ${\frac {C}{C^{*}}}\leqslant {\frac {2\cdot c(T)}{c(C^{*})))\leqslant {\frac {2\\ cdot c(C^{*})}{c(C^{*})}}=2$

Cu toate acestea, metoda de mai sus poate fi optimizată prin creșterea numărului de muchii la vârfuri cu un număr impar de vecini cu 1, ceea ce corespunde cu potrivirea vârfurilor „impare”. Este important de reținut că numărul de vârfuri „impare” este întotdeauna par, pe baza lemei strângerii de mână . Într-un astfel de caz, algoritmul optimizat are un factor de aproximare și complexitate de timp . Înainte de demonstrație, să arătăm că , unde este o potrivire și este o rută optimă: Fie mulțimea de vârfuri „impare” ale arborelui de acoperire minim , și să fie un ciclu obținut din sărind vârfuri . Evident, are o lungime uniformă, precum și două potriviri maxime neintersectate și , pentru care și . De aici rezultă că , și deci . Pe baza acesteia, găsim factorul de aproximare al algoritmului: . $3/2$ $O(n^{3})$ $c(M)\leqslant c(C^{*})/2$ $M$ $C^{*}$ $U$ $T$ $C''$ $C^{*}$ $V\setminus U$ $C''$ $M_{1}$ $M_{2}$ $c(M)\leqslant c(M_{1})$ $c(M)\leqslant c(M_{2})$ $2\cdot c(M)\leqslant c(M_{1})+c(M_{2})=c(C'')\leqslant c(C^{*})$ $c(M)\leqslant c(C^{*})/2$ ${\frac {c(C)}{c(C^{*})}}\leqslant {\frac {c(T)+c(M)}{c(C^{*})}} \leqslant {\frac {c(C^{*})+c(C^{*})/2}{c(C^{*})}}\leqslant {\frac {1,5\cdot c(C^ {*})}{c(C^{*})}}=1,5$

Există, de asemenea, setări în care problema vânzătorului ambulant devine NP-completă . De obicei, astfel de afirmații arată astfel: există un astfel de tur pe un anumit grafic G încât costul său să nu depășească x . Adesea, sunt testate noi abordări ale reducerii euristice a căutării exhaustive .

În practică, sunt utilizate diverse modificări ale metodelor mai eficiente: metoda ramurilor și legate și metoda algoritmilor genetici , precum și algoritmul coloniei de furnici .

Branch and Bound Method

Este posibil să găsiți o soluție exactă la problema vânzătorului ambulant, adică să calculați „manual” lungimile tuturor rutelor posibile și să alegeți traseul cu lungimea cea mai mică. Cu toate acestea, chiar și pentru un număr mic de orașe, este practic imposibil să rezolvi problema în acest fel. Pentru o variantă simplă, o problemă simetrică cu orașele, există rute posibile, adică pentru 15 orașe sunt 43 de miliarde de rute și pentru 18 orașe sunt deja 177 de trilioane. Cât de rapid crește durata calculelor poate fi arătat prin următorul exemplu. Dacă ar exista un dispozitiv care ar putea găsi o soluție pentru 30 de orașe într-o oră, atunci două orașe suplimentare ar dura de o mie de ori mai mult; adică mai mult de 40 de zile. $n$ $(n-1)!/2$

Metodele de optimizare discrete, în special metodele ramificate și legate, fac posibilă găsirea de soluții optime sau aproximative pentru probleme suficient de mari.

Într-o interpretare geometrică, aceste metode tratează problema ca un politop convex, adică un poligon multidimensional într-un cub unitar -dimensional , unde este egal cu numărul de muchii din grafic. Fiecare vârf al acestui cub unitate corespunde unui traseu, adică unui vector cu elemente 0/1, care satisface inegalitățile liniare descrise mai sus. Hiperplanurile descrise de aceste inegalități decupează acele muchii ale cubului unității care nu corespund nici unei rute. $m$ $[0,1]^{m}$ $m$

Figura alăturată arată aplicarea metodei pentru o problemă cu trei noduri. În conformitate cu cele trei muchii posibile dintre vârfuri, variabilele binare și sunt comparate . În acest caz, există un singur traseu posibil și anume cel care trece prin trei vârfuri. Această rută satisface inegalitatea , care afirmă că o rută trebuie să treacă prin cel puțin două vârfuri. Pe lângă această cale, care corespunde vectorului (1,1,1), toate punctele din partea marcată cu roșu a acestei inegalități satisfac și inegalitatea. Planurile care trec prin liniile roșii decupează toate colțurile corespunzătoare căilor inexistente cu cel mult o muchie, și anume vector zero (0, 0, 0), vectori unitari (1, 0, 0), (0, 1, 0) și (0, 0, 1). O inegalitate puternică va tăia totul din cubul unității, cu excepția singurului punct valid (1, 1, 1). În acest caz particular, același efect poate fi obținut prin trei inegalități de tip (1). $x_{1},\,x_{2}$ $x_{3}$ $x_{1}+x_{2}+x_{3}\geqslant 2$ $x_{1}+x_{2}+x_{3}\geqslant 3$

Pentru a determina muchia admisibilă cu cea mai mică lungime, ar trebui să se rezolve seturi de probleme de optimizare liniară care decupează părți inutile ale cubului unitar prin planuri de tăiere și să încerce să împartă cubul unității în politopi mai mici folosind metoda ramurilor și legate.

Cu toate acestea, această metodă nu este de obicei suficientă pentru a găsi rapid rute. Principalul avantaj al metodelor exacte este că, având suficient timp, calculează cel mai scurt traseu. Având o limită inferioară pentru soluții optime, se poate estima cât de mult diferă ruta găsită de cea optimă. De exemplu, având o limită inferioară de 100 și după găsirea unui traseu cu lungimea 102, traseul optim poate fi între 100 și 102. Așa-numitul interval de optimitate , sau distanța relativă maximă dintre lungimea traseului optim și cel mai scurt traseu cunoscut, va fi (102 - 100) /100 = 2%, adică lungimea traseului găsit 102 diferă cu maxim 2% de cea optimă. Când lungimea traseului calculat este egală cu lungimea celui precedent, se consideră că soluția găsită este optimă. Pentru a găsi rute de lungime acceptabilă, metodele exacte pot fi combinate cu cele euristice.

Metoda ramurilor și legate pentru rezolvarea problemei vânzătorului ambulant a fost propusă în 1963 de un grup de autori (J. Little, K. Murty, D. Sweeney, K. Carol) [3] .

Metoda rețelei elastice

Istorie

În 1987, a fost folosit de Durbin și Willshaw, care au subliniat o analogie cu mecanismele de stabilire a conexiunilor neuronale ordonate [4] .

Fiecare dintre rutele vânzătorului ambulant a fost considerată ca o cartografiere a unui cerc pe un avion (un punct din acest cerc este mapat la fiecare oraș din avion). Punctele învecinate de pe cerc ar trebui să fie mapate la punctele, dacă este posibil, cele mai apropiate și de pe plan.

Algoritm

Începe cu instalarea unui mic cerc în avion. Se extinde neuniform, devenind un inel care trece prin aproape toate orașele și stabilește astfel traseul dorit. Fiecare punct de mișcare al inelului este afectat de două componente: deplasarea punctului spre cel mai apropiat oraș și deplasarea către vecinii punctului de pe inel pentru a reduce lungimea acestuia. Orașul se conectează în cele din urmă la o anumită secțiune a inelului pe măsură ce se extinde. Pe măsură ce o astfel de rețea elastică se extinde, fiecare oraș este asociat cu o anumită secțiune a inelului.

La început, toate orașele au aproximativ aceeași influență asupra fiecărui punct de referință. Ulterior, distanțele mai mari devin mai puțin influente și fiecare oraș devine mai specific punctelor inelului cele mai apropiate de el. Această creștere treptată a specificității, care amintește de metoda de învățare a rețelei Kohonen, este controlată de valoarea unei anumite raze efective.

Durbin și Willshaw au arătat că pentru problema celor 30 de orașe luată în considerare de Hopfield și Tank, metoda rețelei elastice generează cel mai scurt traseu în aproximativ 1000 de iterații. Pentru 100 de orașe, traseul găsit prin această metodă a fost cu doar 1% mai mare decât cel optim.

Algoritmul furnicilor

Algoritm genetic

Algoritm de programare dinamică

Ideea principală este de a calcula și stoca calea de la orașul inițial la fiecare dintre celelalte orașe, apoi însumăm această valoare cu calea de la fiecare dintre celelalte orașe la orașele rămase etc. Avantajul acestei metode față de brute- metoda forței este o reducere semnificativă a calculelor de volum total datorită creșterii vizibile a cantității de memorie [5] . $D$ $F$ ${\displaystyle P_{D}=(6n-1)-n2^{n-1}+4n(n-1)2^{n-2}, P_{F}=n!\aprox n^{n} e^{-n}{\sqrt {2\pi n)),P_{D}\ll P_{F))$ $Q_{D}\sim 2^{n}{\sqrt {\frac {2n}{\pi }}},Q_{F}=2,Q_{D}\gg Q_{F}$

Vezi și

Note

↑ Gross JL, Yellen J. Teoria grafurilor și aplicațiile sale, 2006 , p. 275.
↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analyze Arhivat la 19 august 2021 la Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, p. 310-337.
↑ Kostevich L. S. Programare matematică: Informare. tehnologia solutiilor optime: Proc. indemnizaţie / L. S. Kostevici. - Minsk: Cunoștințe noi, 2003. ill., p. 150, ISBN 985-6516-83-8
↑ Richard Durbin, David Willshaw. O abordare analogică a problemei vânzătorului ambulant folosind o metodă de plasă elastică // Natura . — 22-04-1987. — Vol. 326 , iss. 6114 . — P. 689–691 . - doi : 10.1038/326689a0 . Arhivat din original pe 23 aprilie 2016.
↑ Korbut A. A., Finkelstein Yu. Yu. Programare discretă. - M., Nauka, 1969. - C. 258-264

Literatură

Levitin A. V. Capitolul 3. Metoda forței brute: problema vânzătorului ambulant // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 159-160. — 576 p. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: constructie si analiza = Introduction to Algorithms. - Ed. a II-a. - M .: „Williams” , 2006. - S. 1296. - ISBN 0-07-013151-1 .
IN SI. Înţelept. Problema vânzătorului ambulant . - M . : „Cunoașterea” , 1969. - S. 62.
Ezhov A., Shumsky S. Neurocomputing și aplicațiile sale în economie și afaceri . - M .: MEPhI , 1998. - S. 216.
Gross JL, Yellen J. Teoria grafurilor și aplicațiile sale. a doua editie. Boca Raton—Londra—New York: Chapman & Hall/CRC, 2006.

Probleme NP-complete
Problema de maximizare a stivuirii (ambalării)	Ambalare in containere ambalare bidimensională ambalare liniară ambalare după greutate ambalare după valoare Problema rucsacului
teoria grafurilor teoria multimelor	Problemă de acoperire a vârfurilor Faceți clic pe problemă Problema unei multimi (multimi) independente Setați problema acoperirii Problema lui Steiner Problema vânzătorului ambulant Problemă generalizată a vânzătorului ambulant
Probleme algoritmice	Problemă de satisfacție pentru formulele booleene (în formă normală conjunctivă)
Jocuri de logică și puzzle-uri	Etichete generalizate (joc în N 2 -1) cea mai scurta solutie problema Probleme ale căror soluții sunt aplicate în Tetris Problemă generalizată de Sudoku Problemă de umplere a pătratului latin Sarcina lui Kakuro
Clasele de dificultate Cercetare operațională Optimizare Optimizare combinatorie Matematică aplicată Teoria algoritmilor Programare dinamică 21 Problemă Karp NP-completă