![Programul
Programul:
#include <iostream>
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]<n)
{v[k]=v[k]+1; return 1; } //daca mai sunt elemente neselectate
inca, il adaugam la
else return 0;}
int valid(int k)
{ for(int i=1;i<k;i++)](https://image.slidesharecdn.com/metodaback-150507145722-lva1-app6892/85/Metoda-back-9-320.jpg)
![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<=k;i++) //afisare vector
cout<<v[i]<<" ";
cout<<endl;
}
void bk(int k){
init(k);
while(succesor(k))
if(valid(k))
{if(solutie(k)) tipar(k);
else bk(k+1);}
}
int main()
{
cout << "n="; cin>>n;
cout<<" permutari de "<<n<<endl;
bk(1);
return 0;}](https://image.slidesharecdn.com/metodaback-150507145722-lva1-app6892/85/Metoda-back-10-320.jpg)
Metoda back
- 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 solu釘iei,pornind de la primul element si adaug樽nd 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 solu釘ii posibile. De cele mai multe ori 樽ns, nu ne intereseaz toate solu釘iile, ci numai o parte dintre ele, care 樽ndeplinesc anumite condi釘ii specifice problemei. Pentru astfel de probleme este indicat folosirea metodei backtracking care evit generarea solu釘ilor 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 sf但ritul 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 <iostream> 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]<n) {v[k]=v[k]+1; return 1; } //daca mai sunt elemente neselectate inca, il adaugam la else return 0;} int valid(int k) { for(int i=1;i<k;i++)
- 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<=k;i++) //afisare vector cout<<v[i]<<" "; cout<<endl; } void bk(int k){ init(k); while(succesor(k)) if(valid(k)) {if(solutie(k)) tipar(k); else bk(k+1);} } int main() { cout << "n="; cin>>n; cout<<" permutari de "<<n<<endl; bk(1); return 0;}