Problema comis-voiajorului în C++ [Backtracking]

Problema comis-voiajorului în C++ [Backtracking]

Problema comis-voiajorului (Travelling Salesman Problem, prescurtat TSP) este o problemă clasică de backtracking elementar. Totodată, aceasta este o celebră problemă NP-completă, fiind foarte importantă în studiul informaticii teoretice. În acest articol voi prezenta abordarea problemei prin backtracking și optimizarea soluției utilizând branch and bound. Voi folosi câteva noțiuni din teoria grafurilor, dar nu este obligatoriu să le cunoașteți pentru a înțelege rezolvarea problemei.

Enunț

Se dau nn orașe, numerotate de la 11 la nn și o listă cu mm străzi bidirecționale (pe care se poate circula în ambele sensuri), identificate prin cele două orașe-extremități și prin lungime. Un comis-voiajor are misiunea de a livra colete în toate aceste orașe, cu condiția să se întoarcă în orașul din care a plecat. El poate realiza asta în multe moduri, însă îl interesează un drum de lungime minimă. Așadar, se cere determinarea unui drum de lungime minimă, care să treacă prin fiecare oraș exact o singură dată, iar din ultimul oraș vizitat să revină în primul.

Exemplu

De pe prima linie a fișierului tsp.in se citesc nn și mm numărul de orașe și respectiv numărul de străzi. Pe fiecare dintre următoarele mm linii se găsesc câte trei numere xx yy și zz cu semnificația că strada dintre orașele xx și yy are lungimea zz

5 8
1 2 20
1 5 60
1 4 30
2 4 30
4 3 70
2 3 40
4 5 30
5 3 30

În fișierul tsp.out se va afișa pe prima linie lungimea minimă a unui traseu optim, iar pe a doua linie un astfel de traseu.

150
1 2 3 5 4

Iată cum arată harta orașului descris, precum și un drum optim pentru comisul-voiajor:

Problema comis-voiajorului (exemplu)

Legătura cu teoria grafurilor

Practic, ni se dă un graf neorientat cu costuri pe muchii, și trebuie să determinăm un ciclu hamiltonian (un drum care trece prin toate nodurile grafului și se întoarce în nodul inițial) de cost minim. Desigur, prin costul ciclului mă refer la suma costurilor muchiilor din care acesta este format.

Soluție prin backtracking

Folosind metoda backtracking, vom genera toate ciclurile hamiltoniene ale grafului dat, și îl vom reține pe parcurs pe cel de cost minim.

Vom reprezenta graful printr-o matrice de adiacență, adică o matrice ad\mathrm{ad} în care pe ad[i][j]\mathrm{ad}[i][j] reținem 00 dacă nu există stradă între orașele ii și jj sau lungimea străzii respective în caz contrar. De asemenea, în variabila lg\mathrm{lg} vom reține lungimea traseului curent, iar în vectorul tr\mathrm{tr} orașele din care este compus acesta. În plus, vom avea nevoie de o variabilă lgMin\mathrm{lgMin} și de un vector trMin\mathrm{trMin} pentru stocarea traseului minim și a lungimii acestuia.

Acum urmează partea de backtracking. În primul rând, se observă ușor că nu contează din ce oraș pornim, pentru că oricum trebuie să ne întoarcem de unde am plecat; de exemplu, traseul [3,2,5,1][3, 2, 5, 1] este tot una cu [5,1,3,2][5, 1, 3, 2] Prin urmare, vom fixa pe tr[1]\mathrm{tr}[1] valoarea 11 (adică vom porni mereu din orașul 11 și vom începe generarea prin backtracking de la poziția 22 Această idee va reduce de nn ori numărul de trasee generate!

Vom defini funcția de backtracking cu antetul void bkt(int pos), unde pospos reprezintă poziția curentă din traseul pe care îl generăm. Dacă nu am ajuns pe poziția n+1n + 1 înseamnă că nu am terminat generarea. În cazul acesta, vom pune pe poziția tr[pos]\mathrm{tr}[pos] pe rând, fiecare oraș care încă nu a fost vizitat, dar pentru care există stradă de la el la tr[pos1]\mathrm{tr}[pos - 1] Ca să ținem evidența orașelor vizitate, vom mai lua un vector caracteristic vis\mathrm{vis} unde vis[i]\mathrm{vis}[i] este true dacă orașul ii a fost vizitat, sau false în caz contrar.

for (int i = 2; i <= n; i++)
if (!vis[i] && ad[tr[pos - 1]][i]) {
vis[tr[pos] = i] = true; // Adăugăm i la traseu și îl marcăm ca vizitat.
lg += ad[tr[pos - 1]][i]; // Actualizăm lungimea traseului curent.
bkt(pos + 1); // Continuăm generarea.
vis[i] = false; // Restaurăm vis[i].
lg -= ad[tr[pos - 1]][i]; // // Restaurăm lg.
}

Dacă am ajuns în schimb la poziția n+1n + 1 înseamnă că am terminat generarea unui traseu. Acum trebuie să ne întoarcem în orașul inițial. Deci, vom verifica dacă există stradă de la 11 la tr[n]\mathrm{tr}[n] Dacă nu, traseul nu este valid. Dacă da, mai rămâne să adăugăm la lungime costul ultimei muchii a ciclului, adică ad[tr[n]][1]\mathrm{ad}[\mathrm{tr}[n]][1] Apoi comparăm lg\mathrm{lg} cu lgMin\mathrm{lgMin} și actualizăm soluția dacă este cazul.

if (pos == n + 1) {
if (!ad[tr[n]][1])
return;
lg += ad[tr[n]][1];
if (lg < lgMin) { // Actualizăm soluția:
lgMin = lg;
for (int i = 1; i <= n; i++)
trMin[i] = tr[i];
}
lg -= ad[tr[n]][1];
return;
}

Optimizare prin branch and bound

Se observă ușor că, dacă la un apel al funcției bkt lungimea curentă este mai mare sau egală cu lungimea minimă obținută până atunci, sigur acel început de traseu nu va duce la o soluție mai bună decât cea pe care o avem deja. În acest caz, putem ieși din apel printr-un simplu return.

if (lg >= lgMin)
return;

Acest procedeu de optimizare se numește branch and bound, și se aplică adesea problemelor de backtracking în care trebuie să determinăm un cost minim. El reduce crucial timpul de execuție a programului, deoarece sare peste o grămadă de trasee nefolositoare.

Mai jos este o animație făcută de mine, care ilustrează modul în care funcționează backtracking-ul în această problemă:

Sursă C++

Iată o sursă în C++ ce rezolvă problema comis-voiajorului prin backtracking.

Problema comis-voiajorului
#include <fstream>
using namespace std;
const int DMAX = 100;
ifstream fin("tsp.in");
ofstream fout("tsp.out");
int n, m;
int ad[DMAX][DMAX];
int lgMin = 1e9;
int trMin[DMAX];
int lg;
int tr[DMAX];
bool vis[DMAX];
void bkt(int pos) {
if (lg >= lgMin)
return;
if (pos == n + 1) {
if (!ad[tr[n]][1])
return;
lg += ad[tr[n]][1];
if (lg < lgMin) {
lgMin = lg;
for (int i = 1; i <= n; i++)
trMin[i] = tr[i];
}
lg -= ad[tr[n]][1];
return;
}
for (int i = 2; i <= n; i++)
if (!vis[i] && ad[tr[pos - 1]][i]) {
vis[tr[pos] = i] = true;
lg += ad[tr[pos - 1]][i];
bkt(pos + 1);
vis[i] = false;
lg -= ad[tr[pos - 1]][i];
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z; fin >> x >> y >> z;
ad[x][y] = ad[y][x] = z;
}
vis[tr[1] = 1] = true;
bkt(2);
fout << lgMin << '\n';
for (int i = 1; i <= n; i++)
fout << trMin[i] << ' ';
fout << '\n';
return 0;
}

Complexitate

În cel mai nefavorabil caz, numărul total de cicluri hamiltoniene ale grafului dat este (n1)!/2(n - 1)! / 2 asta se întâmplă atunci când graful este complet. Există cazuri în care, chiar și cu optimizarea făcută prin branch and bound, vom fi nevoiți să generăm toate aceste cicluri; de exemplu atunci când graful este complet și toate muchiile au același cost.

Prin urmare, complexitatea algoritmului este O(n!)O(n!) Teoretic, este o complexitate foarte proastă, însă în practică (pe teste obișnuite, cu nn până în 2020 - 3030 algoritmul se comportă destul de bine. Există și o soluție ce folosește programare dinamică, de complexitate exponențială, însă nu este foarte practică din cauza cantității mare de spațiu necesară. Voi analiza această abordare într-un articol viitor.


Problema comis-voiajorului se găsește în arhiva educațională de pe InfoArena, sub numele de Ciclu hamiltonian de cost minim. Acolo este gândită pentru grafuri orientate, indexate de la 00 Deci, sursa de mai sus trebuie modificată un pic ca să funcționeze pe InfoArena. Oricum, va obține doar 70 de puncte; pentru restul trebuie folosită programare dinamică.

Dacă aveți vreo întrebare legată de problema comis-voiajorului, nu ezitați să o adresați într-un comentariu, mai jos

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii