Problema comis-voiajorului implementare C

este acea formă de organizare a datelor (structură de date) cu proprietatea că operaţiile de introducere şi scoatere a datelor se fac în vârful ei.¬

Stivele se pot simula utilizând vectori.

Tehnica Backtracking are ca rezultat obţinerea tuturor soluţiilor problemei. În cazul în care se cere o sigură soluţie se poate forţa oprirea, atunci când a fost găsită

Tehnica Backtracking are la bază un principiu extrem de simplu:

- se construieşte soluţia pas cu pas: x1, x2 …,xn

- dacă se constată că, pentru o valoare aleasă, nu avem cum să ajungem la soluţie, se renunţă la acea valoare şi se reia căutarea din punctul în care am rămas.

Această tehnică se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoarele condiţii:

• soluţia lor poate fi pusă sub forma unui vector S=x1,x2,….xn, cu x1 A1,….,An;

• mulţimile A1,A2,….,An sunt mulţimi finite, iar elementele lor se consideră că se află într-o relaţie că se află într-o relaţie de ordine bine stabilită ;

• nu se dispune de o altă metodă mai rapidă ;

Observaţii :

• nu pentru toate problemele n este cunoscut de la început ;

• x1,x2,….,xn pot fi la rândul lor vectori ;

• în multe probleme mulţimile A1,A2,….,An coincid.

La întâlnirea unei astfel de probleme, dacă nu cunoaştem această tehnică, suntem tentaţi să generăm toate elementele produsului cartezian A1XA2X….XAn şi fiecare element să fie testat dacă este soluţie. Rezolvând problema în acest mod, timpul de execuţie este atât de mare,încât poate fi considerat infinit, algoritmul neavând nicio valoare practică.

Exemplu: Un comis-voiajor trebuie să viziteze un număr de n oraşe. Iniţial, acesta se află într-unul din ele, notat 1. Comis voiajorul doreşte să nu treacă de două ori prin acelaşi oraş, iar la întoarcere să revină în oraşul 1. Cunoscând legăturile existente între oraşe, se cere să se tipărească toate drumurile posibile pe care le poate efectua comis-voiajorul.

Fie simbolizate 6 oraşe, precum si drumurile existente între ele.

Comis-voiajorul are următoarele posibilităţi de parcurgere :

• 1,2,3,4,5,6,1 ;

• 1,2,5,4,3,6,1 ;

• 1,6,3,4,5,2,1 ;

• 1,6,5,4,3,2,1 ;

Legăturile existente între oraşe sunt date de matricea An,n. Elementele matricei A[i][j] pot fi 0 sau 1 (matricea este binară).

Matricea retine daca exista un drum intre orasul i si orasul j.

- daca da, atunci A[i][j] = 1

- daca nu, atunci A[i][j] = 0

Se observă că A(i,j)=A(j,i), oricare ar fi i şi j aparţinând mulţimii {1,2,...,n}

– matricea este simetrică.

Pentru rezolvare problemei folosim un vector cu 10 elemente. La bază vectorului (nivelul 1) se încarcă numărul 1. Prezentăm în continuare modul de rezolvare al problemei :

2

1

De la oraşul 1 la oraşul 2 există drum deci se va urca în stivă.