Curs 8
Metoda Backtracking
(continuare)
1
Conţinutul cursului
1. Exemple de probleme rezolvate cu
ajutorul metodei backtracking
2. Metoda backtracking – varianta recursiva
2
Problema 1
Sa se genereze toate aranjamentele multimii {1, 2,
…, n}, cu cate p elemente.
Exemplu:
Pentru n = 5 si p = 3 se vor afisa multimile:
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1);
(1,2,4), (1,4,2), (2,1,4), (2,4,1), (4,1,2), (4,2,1);
(1,2,5), (1,5,2), (2,1,5), (2,5,1), (5,1,2), (5,2,1);
(1,3,4), (1,4,3), (3,1,4), (3,4,1), (4,1,3), (4,3,1);
(1,3,5), (1,5,3), (3,1,5), (3,5,1), (5,1,3), (5,3,1);
(1,4,5), (1,5,4), (4,1,5), (4,5,1), (5,1,4), (5,4,1),
s.a.m.d.
3
Implementarea programului pentru generarea aranjamentelor:
#include<iostream.h>
int st[20],k,p,as,ev;
void init(int k,int st[ ])
{
st[k]=0;
}
int succesor(int k,int st[ ])
{
if ( st[k]<n )
{
st[k]=st[k]+1;
as=1;
}
else as=0;
return as;
}
4
10
o
int valid(int k,int st[ ])
{
ev=1;
for (i=1;i<=k-1;i++)
if (st[i]==st[k]) ev=0;
return ev;
}
5
10
int solutie(int k) Sigura modificare fata
{ de algoritmul generarii
permutarilor!
if ( k==p ) return 1;
else return 0;
}
void tipar(void)
{
for(i=1;i<=k;i++)
cout<<" "<<st[i];
cout<<"\n";
}
6
int main(void)
10
{
cout<<“Dati n = “; cin>>n;
cout<<“Dati p = “; cin>>p;
k=1; init(k,st);
while (k>0)
{
do{
as=succesor(k,st); if
(as) ev=valid(k,st);
}while (!( !as || (as && ev)));
if (as)
if (solutie(k)) tipar();
else
{
k++;
init(k,st);
}
else
k--;
}
}
Proiectarea Algoritmilor - curs 7
10
Problema 2
Sa se genereze toate combinarile multimii
{1, 2, …, n}, cu cate p elemente.
Exemplu:
Pentru n = 5 si p = 3 se vor afisa multimile:
(1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5),
(2,3,4), (2,3,5), (3,4,5).
8
10
int valid(int k,int st[ ])
{
Modificare fata de algoritmul
generarii permutarilor:
• Elementele trebuie sa fie in ordine
crescatoare
9
10
int solutie(int k)
{
Generam p combinari !
comparam k cu p
10
10
14
10
Problema 3
Se considera un numar n natural nenul si se
cere sa se afiseze toate descompunerile numarului
n in suma de numere naturale.
Exemplu:
Pentru n=5 se vor afisa valorile:
1+1+1+1+1
1+1+1+2; 1+1+2+1; 1+2+1+1; 2+1+1+1
1+2+2; 2+1+2; 2+2+1
1+1+3; 1+3+1; 3+1+1
1+4; 4+1
2+3; 3+2
5 12
10
int valid(int k,int st[ ])
{
• Trebuie calculata suma
elementelor aflate la un
moment dat in stiva
• Daca suma depaseste
pe n, atunci ev=0!
s+=st[i];
if( s > n ) ev=0;
return ev;
}
13
10
int solutie(int k)
0
{
• Trebuie calculata suma
elementelor aflate la un
moment dat in stiva
• Daca suma este egala
cu n, atunci am gasit o
solutie!
}
14
10
Problema 4
Să se descompună un număr natural n, în
toate modurile posibile, ca sumă de p numere
naturale (p<=n).
Exemplu:
Pentru n=5 si p=3 se obtin solutiile:
1+1+3; 1+3+1; 3+1+1;
1+2+2; 2+1+2; 2+2+1;
15
int solutie(int k)
{
elementelor aflate la
un moment dat in stiva
• Daca suma este egala
cu n, atunci am gasit o
solutie!
• In plus trebuie sa avem
fix p elemente in stiva!
…
s+=st[i]
if( s == n && k == p ) …
}
16
10
17
10
Problema 5
Problema colorării hărților
Fiind dată o hartă cu n țări se cere o soluție de
colorare a hărții utilizând cel mult 4 culori, astfel încât
două cu frontiera comună să fie colorate diferit.
O soluție este:
Țara 1 – culoarea 1
4
܉Țara 2 – culoarea 2 1
܉Țara 3 – culoarea 1 3
5
܉Țara 4 – culoarea 3 2
܉Țara 5 – culoarea 4
18
10
Pentru a specifica harta utilizam o matrice patratica cu
valori binare:
1, daca ܊țara i are frontieră comună cu țara ܊j
A(i,j) =
0, altfel
• Se va utiliza stiva st, unde nivelul k al stivei simbolizează
ţara k, iar st[k] culoarea ataşată ţării k.
• Stiva are înălţimea n şi pe fiecare nivel ia valori intre 1 şi
4, adică numărul culorilor este maxim 4.
• Condiţia ca două ţări vecine sa aibă aceeaşi culoare este:
(st[k]==st[i]) && (a[i][k])==1)
19
#include<iostream.h> 10
#include<stdlib.h>
int st[20],k,as,ev,n,i,j,a[20][20];
void init(int k,int st[ ])
{
st[k]=0;
}
int succesor(int k,int st[ ])
{
if ( st[k]<4 )
{
st[k]=st[k]+1;
as=1;
}
else as=0;
return as;
}
20
10
int valid(int k,int st[ ])
{
ev=1;
for(i=1;i<=k-1;i++)
if(st[k] == st[i] && a[i][k] == 1) ev=0;
return ev;
}
30
10
int solutie(int k)
{
if( k == n ) return 1;
else return 0;
}
void tipar(void)
{
for(i=1;i<=k;i++)
cout<<"tara "<<i<<" are culoarea "<<st[i]<<"\n";
exit(1);
}
31
10
23
10
Conţinutul cursului
1. Exemple de probleme rezolvate cu
ajutorul metodei backtracking
2. Metoda backtracking – varianta recursiva
24
10
11.2. Backtracking recursiv
Functiile folosite sunt in general aceleasi, cu doua mici exceptii:
1. In functia SOLUTIE conditia este n+1;
2. rutina backtracking se transforma in functie, care se apeleaza
prin BACK(1)
Principiul de functionare al functiei BACK, corespunzator unui
nivel k este urmatorul:
• in situatia in care avem o solutie, o tiparim si revenim pe nivelul
anterior
• in caz contrar se initializeaza nivelul si se cauta un succesor
• cand am gasit unul verificam daca este valid; functia se
autoapeleaza pentru (k+1), in caz contrar urmand a se
continua cautarea succesorului;
• daca nu avem succesor, se trece pe nivel inferior (k-1) prin
iesirea din functia BACK
25
10
Implementarea algoritmului pentru generarea permutarilor –
varianta recursiva:
#include<iostream.h>
int st[20],k,p,as,ev,n;
void init(int k,int st[ ])
{
st[k]=0;
}
int succesor(int k,int st[ ])
{
if ( st[k]<n )
{
st[k]=st[k]+1;
as=1;
}
else as=0;
return as;
}
26
10
int valid(int k,int st[ ])
{
ev=1;
for (int i=1;i<=k-1;i++)
if (st[i]==st[k]) ev=0;
return ev;
}
int solutie(int k)
{
if ( k==n+1 ) return 1;
else return 0;
}
void tipar(void)
{
for(int i=1;i<=n;i++)
cout<<" "<<st[i];
cout<<"\n";
}
27
10
void back(int k)
{
if(solutie(k)) tipar();
else{
init(k,st);
while(succesor(k,st))
{
ev=valid(k,st);
if(ev) back(k+1);
}
}
}
int main(void)
{
cout<<"Dati n = "; cin>>n;
back(1);
}
40