METODA

BACKTRACKING
 Backtracking este o tehnică generală de elaborare a algoritmilor și se
folosește în rezolvarea problemelor care îndeplinesc simultan următoarele
condiții :

• soluția poate fi scrisă sub forma unui vector S=x1 x2 xn ; x1 e A1 etc.

• mulțimile A1,A2..An sunt finite, se află într-o relație de ordine bine
stabilită; mulțimea soluțiilor posibile, verifică condițiile interne pentru
fiecare problemă și generează toate soluțiile rezultat;

• nu se cunoaște o metodă de rezolvare mai rapidă.

 În general tehnica utilizează o rutină unică, elaborată folosind noțiunea de
stivă, ce poate fi aplicată tuturor problemelor ce permit o rezolvare Backtracking.

Rutina aplează funcții și proceduri ce au întotdeauna același nume și

parametri și care realizează același lucru. Pe măsură ce soluțiile sunt generate,
acestea se depun în stivă.

Tehnica Backtracking are ca rezultat obținerea tuturor soluțiilor problemei.

Pentru o singură soluție se poate forța oprirea.

Tehnica se bazează pe structura tip stivă.

Stiva este forma de organizare a datelor cu proprietatea că operațiile de

introducere și scoatere a datelor se fac în vârf.
Principiul Backtracking
se construiește soluția pas cu pas;
dacă se consideră că pentru o valoare aleasă nu avem cum să ajungem la
soluție, se renunță la acea valoare și se reia căutarea din punctul în care am
rămas.
 PERMUTĂRI

PERMUTAREA se referă la numărul de posibilități de rearanjare al

unei liste ordonate de valori.

Numărul de permutări ale unei mulțimi de elemente este dat de

produsul numerelor (de ordine ale elementelor) de la 1 la n, cunoscut
ca factorial n!

EX. N=3
123
132
213
231
312
321
 PERMUTĂRI
#include<iostream> void back(int k)
Să se genereze using namespace std; {
toate permutările for(int i=1;i<=n;i++)
primelor n numere int st[20],n; {st[k]=i;
naturale. if (valid(k))
void tipar() if(k==n)
Ex. n=3 { tipar();
for(int i=1;i<=n;i++) else
123 cout<<st[i]<<' '; back(k+1);
132 cout<<endl; }
213 } }
231
312 int main()
321 int valid(int k) {
{ cin>>n;
for(int i=1;i<k;i++) back(1);
if (st[i]==st[k]) }
return 0;
return 1;
}
PERMUTĂRI
 ARANJAMENTE

Se numește aranjament de n elemente luate câte k orice combinație

alcătuită din k elemente ale mulțimii A formată din n elemente.

EX. N=3 K=2

12
13
21
23
31
32
 ARANJAMENTE
#include<iostream> void back (int k)
Să se genereze using namespace std; {for(int i=1;i<=n;i++)
toate aranjamentele int st[20],n,k,p; {st[k]=i;
de n luate câte p. if (valid(k))
void tipar() if(k==p)
{for(int i=1;i<=p;i++) tipar();
Ex. n=3 p=2 cout<<st[i]<<' '; else
cout<<endl; back(k+1);
12 } }
13 }
21 int valid(int k)
23 { for(int i=1;i<k;i++) int main()
31 if (st[i]==st[k]) {
32 return 0; cin>>n>>p;
return 1; back(1);
} }
ARANJAMENTE
 COMBINĂRI

COMBINĂRILE se referă la combinarea de n elemente luate

câte k odată fără a se repeta.

EX. N=3 K=2

12
13
23
 COMBINĂRI
#include<iostream> void back(int k)
Să se genereze using namespace std; {
toate combinările int i;
de n luate câte p. int st[20],n,k,p; for(i=st[k-1]+1;i<=n;i++)
{st[k]=i;
if(k==p)
Ex. n=3 p=2 void tipar() tipar();
{for(int i=1;i<=p;i++) else
12 cout<<st[i]<<' '; back(k+1);
13 cout<<endl;} }
23 }

int main()
{
cin>>n>>p;
back(1);
}
COMBINĂRI
 PRODUS CARTEZIAN

PRODUSUL CARTEZIAN a n mulțimi este o mulțime (numită

și mulțimea-produs) formată din ansamblul tuturor perechilor a căror
componente aparțin mulțimilor.

SE DAU N MULȚIMI
S1={1,2,3…V1} S2={1,2,3…V2} PRODUSUL CARTEZIAN
.... SN={1,2,3…VN} ESTE:
S1XS2XS3={(1,1,1) (1,1,2) (1,2,1)
EXEMPLU : N=3
(1,2,2) (1,3,1) (1,3,2) (2,1,1)
AVEM URMĂTOARELE MULȚIMI
(2,1,2) (2,2,1) (2,2,2) (2,3,1)
S1={1,2} V1=2 (2,3,2) }
S2={1,2,3} V2=3
S3={1,2} V3=2
 PRODUS CARTEZIAN
Se dau n mulțimi #include <iostream> void BK(int k)
using namespace std; {
S1={1,2,3…v1}
int n,k,v[20],w[20]; int i;
S2={1,2,3…v2} for(i=1;i<=w[k];i++)
. int solutie(int k){ //parcurgem elementele mulțimii
if(k==n) {
Sn={1,2,3…vn}
//verificăm dacă am obținut o soluție v[k]=i;
//selectăm un element din mulțime
return 1; //nu avem validare, condiție de continuare
Exemplu : n=3 //am obținut o permutare dacă am
avem următoarele reușit să depunem în v, n elemente
if(solutie(k))
mulțimi return 0; //verificăm dacă am obținut o soluție - if(k==n)
} afisare(k);
S1={1,2} v1=2
//se afișează soluția obținută
S2={1,2,3} v2=3 void citire() { else
S3={1,2} v3=2 int i; BK(k+1);
cin>>n; //reapelăm funcția pentru k+1
for(i=1;i<=n;i++) }
Produsul cartezian este:
cin>>w[i]; }
S1xS2xS3={(1,1,1)
}
(1,1,2) (1,2,1) (1,2,2) int main()
(1,3,1) (1,3,2) (2,1,1) void afisare(int k) { {
int i; citire();
(2,1,2) (2,2,1) (2,2,2)
for(i=1;i<=k;i++) BK(1);
(2,3,1) (2,3,2) } return 0;
cout<<v[i]<<' ';
cout<<endl; } }
PRODUS CARTEZIAN
 SUBMULȚIMI

Mulțimea poate fi descrisă în limbaj matematic în următorul mod: o totalitate de elemente bine
determinate și distincte, numite și elementele mulțimii. Mulțimile se notează cu literele mari
ale alfabetului latin: a, b, c, d, etc. Elementele unei mulțimi se scriu între acolade:

A = {0,1,2,3,4,5,6,7,8,9,10}

Mulțimea fără nici un element se numește mulțime vidă și se notează cu zero tăiat „ø”.

Se spune că mulțimea b este submulțimea mulțimii a dacă b „este conținută” de a.

echivalent, putem scrie B A,citit b include a, sau b conține a.

EX. N=3 S={1,2,3}

SUBMULȚIMILE SUNT :
Mulțimea vidă
{1} {1,2} {1,2,3}
{1,3} {2} {2,3} {3}
 SUBMULȚIMI I
Să se genereze toate #include <iostream> void BK(int k)
using namespace std; {
submulțimile
int i;
mulțimii int n,p,v[20]; for(i=v[k-1]+1;i<=n;i++)
S={1,2,3…n} {
int solutie(int k) v[k]=i;
Ex. n=3 S={1,2,3} { if(solutie(k))
submulțimile sunt : if(k==p) afisare(k);
return 1; else
mulțimea vidă return 0; BK(k+1);
{1} {1,2} {1,2,3} } }
{2} {1,3} }
{3} {2,3} void afisare(int k)
{ int main()
Să observăm că pentru int i; {
a obține toate submulțimile
cout<<'{'; cin>>n;
unei mulțimi este suficient să
generăm pe rând Cn1 Cn2 for(i=1;i<=k;i++) cout<<"multimea vida"<<endl;
....Cnn-1 la care trebuie să cout<<v[i]<<','; for(p=1;p<n;p++)
adăugăm mulțimea vidă și cout<<'}'<<endl; BK(1);
mulțimea S. } cout<<'{';
În aceste condiții este for(int i=1;i<n;i++)
suficient să modificăm cout<<i<<',';
funcția pricipală pentru a
cout<<n<<'}';
genera toate submulțimile și
afișarea datelor ca mulțimi de return 0;
elemente. }
 SUBMULȚIMI II
Să se genereze toate #include <iostream> void BK(int k)
submulțimile using namespace std; {
mulțimii int n,p,v[20]; int i;
S={1,2,3…n} for(i=v[k-1]+1;i<=n;i++)
void afisare(int k) {
Ex. n=3 S={1,2,3} { v[k]=i;
submulțimile sunt : int i; afisare(k);
mulțimea vidă cout<<'{'; BK(k+1);
{1} for(i=1;i<=k;i++) }
{1,2} cout<<v[i]<<','; }
{1,2,3} cout<<'}'<<endl;
{1,3} } int main()
{2} {
{2,3} cin>>n;
{3} cout<<"multimea vida"<<endl;
Putem construi un BK(1);
algoritm mai eficient pentru
generarea submulțimilor.
Ex. dacă generăm în această return 0;
ordine {1} {1,2}{1,2,3} {1,3}
{2} {2,3} {3}
}
 GENERAREA PARTIȚIILOR UNEI MULȚIMI

Prin partiție se înțelege o descompunere a mulțimii inițiale într-

o reuniune de mulțimi nevide și disjuncte.
Pentru o mulțime cu n elemente vor exista maxim n mulțimi în
cadrul unei partiții.
Soluția v[1]..v[n]. Fiecare mulțime din cadrul partiției va fi
codificată cu numere de la 1 la n.
Elementul v[i] va avea ca valoare numărul asociat mulțimii din
care face parte.
v[k] poate avea orice valoare din intervalul [1,k]
Doar cele mai mari două elemente din cadrul codificării
unei partiții nu poate să difere decât printr-o unitate.
 GENERAREA PARTIȚIILOR UNEI MULȚIMI
Să se genereze toate #include <iostream> void BK(int k)
using namespace std; {
partițiile unei
int n,v[20],nrsol,maxi[20]; int i;
mulțimi for(i=1;i<=Detmax(k-1)+1;i++)
S={1,2,3…n} int Detmax(int k) {
{ v[k]=i;
Ex. n=3 va genera int maxim=0,i; if(k==n)
for(i=1;i<=k;i++) afisare();
if(v[i]>maxim) else
Soluția
maxim=v[i]; BK(k+1);
{1, 2, 3} { 1, 2 } { 3 } return maxim; }
{ 1, 3 } { 2 } } }
{ 1 } { 2, 3}
{1}{2}{3} void afisare() int main()
{ int i,j; {
Codificarea int maxim=Detmax(n); cin>>n;
for(j=1;j<=maxim;j++){ cout<<"multimea vida"<<endl;
111
cout<<'{'; BK(1);
112 for(i=1;i<=n;i++)
121 if(v[i]==j) return 0;
122 cout<<i<<','; }
12 3 cout<<'}';}
cout<<endl;
nrsol++;
}