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

Teste propuse pentru Bacalaureat, Informatica, 2020

-
Problema 2 din Subiectul al treilea din Testul 1 - Teste propuse pentru Bacalaureat, Informatica, Profil real, specializare matematică-informatică / matematică-informatică intensiv informatică Scrieţi un program C/C++ care citeşte de la tastatură două numere naturale din intervalul [2,20], n și k, şi construieşte în memorie un tablou bidimensional cu n linii şi n∙k coloane, numerotate începând cu 1, astfel încât fiecare linie i (i∈[1,n]) memorează un şir crescător de termeni cu proprietatea că primul termen este i, fiecare valoare apare în şir de exact k ori și oricare doi termeni alăturați au valori egale sau consecutive. Programul afişează pe ecran tabloul construit, fiecare linie a tabloului pe câte o linie a ecranului, cu valorile aflate pe aceeaşi  linie separate prin câte un spaţiu. Exemplu: dacă n=4 și k=3, se afişează pe ecran tabloul alăturat. 1 1 1 2 2 2 3 3 3 4 4 4 2 2 2 3 3 3 4 4 4 5 5 5 3 3 3 4 4 4 5 5 5 6 6 6 4 4 4 5 5 5 6 6 6 7 7 7 R
Citiți mai multe