Metoda Backtracking

-


Metoda Backtracking


Metoda Backtracking se poate folosi pentru problemele în care trebuie sa se genereze toate soluțiile, o soluție a problemei putând fi data de un vector S={x1, x2, ….., xn} ale cărui elemente aparțin, fiecare, unor mulțimi finite Ai , iar asupra elementelor unei soluții exista anumite restricții, specifice problemei care trebuie rezolvata, numite condiții interne.
Mulțimile A: sunt mulțimi ale căror elemente sunt în relații bine stabilite. Mulțimile A pot sa coincidă, sau nu.

Pentru a găsii toate soluțiile unei astfel de probleme folosim o metoda clasica de rezolvare ce executa următorul algoritm:
   Pasul 1: Se generează toate elementele produsului cartezian AAAAA
   Pasul 2: Se verifica fiecare element al produsului cartezian, dacă îndeplinește condițiile interne                         impuse ca sa fie soluție a problemei.  

Aplicarea metodei pentru rezolvarea unei probleme corecte presupune: 
  1. Codificarea soluțiilor, determinarea semnificației elementelor st[i] pentru problema particulara care se rezolva și stabilirea mulțimilor A[i].
  2. Determinarea condiției interne și apoi a condițiilor de continuare.
  3. Transcrierea funcției backtracking pentru condițiile de continuare determinate anterior.

Subprogram Backtracking









Comentarii

Trimiteți un comentariu

Postări populare de pe acest blog

Citire graf neorientat

-
Imagine
   Crearea matricei de adiacenta a unui graf prin citirea datelor din fisier text. Afisarea matricei de adiacenta. Program c++ în Code::Blocks.  #include <iostream> #include <fstream> using namespace std; void citire(int a[][10],int &n) {     int i,j;     ifstream f("date.txt");     f>>n;     for(i=1;i<=n;i++)         for(j=1;j<=n;j++) a[i][j]=0;     while(f>>i>>j) a[i][j]=a[j][i]=1;     f.close(); } void afisare(int a[][10],int n) {     int i,j;     for(i=1;i<=n;i++)     {         for(j=1;j<=n;j++)             cout<<a[i][j]<<" ";         cout<<endl;     } } int main() {     int a[10][10],n;     citire(a,n);     cout<<"Matricea de adiacenta a grafului este "<<endl;     afisare(a,n); }                                                                                                                                                                  
Citiți mai multe

Citirea si afisarea unui vector - Divide et Impera

-
Citirea si afisarea unui vector  Code blocks #include <iostream> #include <math.h> using namespace std; void citire(int li,int ls,int v[]) {     int m;     if(li==ls) {cout<<"\nElementul de pe pozitia "<<li<<" este ";                 cin>>v[li];                }     else {             m=(li+ls)/2;             citire(li,m,v);             citire(m+1,ls,v);          } } void afisare(int li,int ls,int v[]) {     int m;     if(li==ls) cout<<v[li]<<" ";         else {               m=(li+ls)/2;               afisare(li,m,v);               afisare(m+1,ls,v);              } } int main() {     int x[10],n,max,min;     cout<<"\nCate elemente are vectorul ";     cin>>n;     citire(0,n-1,x);     afisare(0,n-1,x); }
Citiți mai multe