1. 1. Metoda backtracking
2. 2. Scop indentificarea problemelor pentru care trebuie enumerate toate soluiile ,fiecare soluie fiind format din n elemente,care aparine unei mulimi finite A i care trebuie s respecte anumite condiii interne. Acest metoda construieste progresiv vectorul soluiei,pornind de la primul element si adaugnd la vector urmatoarele elemente,cu revenire la elementul anterior din vector,in caz de insucces.
3. 3. Metoda de programare BACKTRACKING Deseori n practic trebuie s rezolvm probleme care au un numr foarte mare de soluii posibile. De cele mai multe ori ns, nu ne intereseaz toate soluiile, ci numai o parte dintre ele, care ndeplinesc anumite condiii specifice problemei. Pentru astfel de probleme este indicat folosirea metodei backtracking care evit generarea soluilor inutile.
4. 4. Definitie Backtracking este o metoda de parcurgere sistematica a spatiului solutiilor unei probleme. Se poate folosi pentru probleme in care trebuie sa se genereze toate solutiile, o solutie a problemei putand fi data de un vector (stiva alocata static) v={x1, x2, .. , xn} ale carui elemente apartin fiecare unei multimi finite Sk(xkSk), iar asupra elementelor uneo solutii exista anumite restrictii specifice problemei care trebuie rezolvata numite conditii interne. Multimile Si pot sa coincida sau nu. Pentru a gasi toate solutiile unei astfel de probleme folosind metoda Backtracking, procedam dupa algoritmul urmator:
5. 5. Pentru a gasi toate solutiile unei astfel de probleme folosind metoda Backtracking, procedam dupa algoritmul urmator: 1. La fieacare pas k pornim de la o soluie partiala v=( x1, x2, .. , xk-1) determinata pana in acel moment si incercam sa extindem aceasta solutie adaugand un nou element la sfritul vectorului. 2. Cutm in multimea Sk , un nou element.
6. 6. Forma generala a unei functii BACKTRACKING Vom utiliza implementarea recursiva a algoritmului furnizat de metoda backtraking este mai naturala, deci mai usoara. Segmentul de stiva pus la dispozitie prin apelul functiei este gestionat automat de sistem. Revenirea la pasul precedent se realizeaza in mod natural prin inchiderea nivelului de stiva.
7. 7. 7. Daca nu mai exista niciun element neverificat in multimea Sk inseamna ca nu mai avem nicio pozibilitate din acest moment, sa construim solutia finala, asa ca trebuie sa modificam alegerile facute in prealabil, astfel kk-1 si algoritmul se reia de la pasul 1.
8. 8. Exemplu 1. Generarea permutarilor primelor n numere naturale. -vom genera solutia intr-un vector v={x1, x2, .. , xn} unde (xkSk), -pentru aceasta problema multimile Sk sunt identice Sk ={1,2,3..., n} La pasul k, selectam un element din multimea Sk. -elementele nu au voie sa se repete, (conditia de continuare) Pentru n=3 S1=S2=S3={1,2,3} (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)
9. 9. Programul Programul: #include using namespace std; int v[100],n; void init(int k) { v[k]=0;} // initializare valoare pasul k, cu o valoare mai mica // decat toate elementele multimii Sk int succesor(int k) {if (v[k]
10. 10. Continuare program if(v[i]==v[k]) //daca exista 2 elemente identice return 0; //elementul selectat nu este valid return 1; } // daca trece de verificare, elementul este valid. int solutie(int k) {return k==n;} void tipar(int k){ for(int i=1;i