Transcript of Metoda back
- 1. Metoda backtracking
- 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. 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. 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. 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. 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. 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. 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. 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. 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