curs13

Algoritmi si structuri de date Curs 13

Metode si tehnici de programare

Programarea Dinamica

Daca ın cazul tehnicii Backtracking, de exemplu, se pot identifica foarte simplu problemele ce sepot rezolva folosind aceasta metoda, nu acelasi lucru se poate spune si despre metoda programariidinamice. Acesta tehnica de proiectare a algoritmilor presupune rezolvarea unei probleme prindescompunerea ei ın subprobleme de dimensiune mai mica. Spre deosebire de metoda Divideet Impera, unde subproblemele rezultate trebuie sa fie independente, ın cadrul acestei metodesubproblemele care apar ın descompunere nu sunt independente. Acestea se suprapun, astfelca solutia unei subprobleme se utilizeaza ın construirea solutiilor altor subprobleme. In cazulın care subproblemele se suprapun si s-ar folosi metoda Divide et Impera, s-ar efectua calculeredundante, rezolvandu-se fiecare subproblema ca si cand aceasta nu ar mai fost ıntalnita panaatunci. Programarea dinamica ınsa, rezolva fiecare dintre subprobleme o singura data si memo-reaza solutia acesteia ıntr-o structura de date, evitand astfel rezolvarea redundanta a aceleiasiprobleme.

In denumirea metodei, cuvantul programare nu se refera la scrierea de cod ıntr-un anumit limbajinformatic, ci la programarea matematica care consta ın optimizarea unei functii obiectiv prinalegerea de valori dintr-o multime anume, iar cuvantul dinamic se refera la maniera ın care suntconstruite structurile ın care se stocheaza solutiile subproblemelor.

Metoda programarii dinamice se foloseste ın rezolvarea problemelor de optimizare. Desi o astfelde problema poate avea mai multe solutii optime, metoda furnizeaza doar una singura. Pen-tru a genera toate solutiile optime, trebuie sa o combinam cu tehnica Backtracking. Deoarcemetoda programarii dinamice gaseste o solutie fara a genera toate solutiile posibile, putem gasi oasemanare cu metoda Greedy, ambele metode exploatand proprietatea de substructura optima aproblemei (orice solutie optima a problemei initiale contine o solutie optima a unui subprobleme,deci solutia optima a problemei se obtine prin combinarea solutiilor optime ale subproblemelor).

Rezolvarea unei probleme folosind metoda programarii dinamice presupune urmatoarele etape:

1. se identifica subproblemele ın care poate fi ımpartita problema globala; se stabileste modulın care solutia problemei depinde de solutiile subproblemelor (aceasta etapa consta ınverificarea proprietatii de substructura optima);

2. se gasesc relatii de recurenta care leaga solutiile subproblemelor ıntre ele si de solutiaproblemei globale;

3. se dezvolta relatia de recurenta si se retin rezultatele partiale ıntr-o structura de date(tablou unidimensional, bidimensional etc.), daca acest lucru este necesar;

4. se reconstituie solutia pornind de la datele deja memorate.

Dupa determinarea solutiilor subproblemelor, se poate determina efectiv solutia problemei glob-ale. Reconstructia solutiei problemei se face de jos ın sus, mergand din subproblema ın subprob-lema, ıncepand de la problema cu valoarea optima si ajungand la subproblemele elementare.

1


Exista trei abordari ın dezvoltarea relatiilor de recurenta:

• descendenta, ın care valoarea de calculat se exprima prin valori calculate anterior. Aceastaabordare se implementeaza, de regula, recursiv si, de cele mai multe ori, este ineficienta;folosind aceasta abordare se rezolva doar subproblemele ce contribuie la solutia problemei,ınsa o subproblema este rezolvata de mai multe ori, de cate ori aceasta apare;

• ascendenta, se porneste de la cazul elementar si se genereaza noi valori pe baza celordeja calculate, conform formulei de recurenta; folosind aceasta abordare se rezolva toatesubproblemele, indiferent daca contribuie sau nu la solutia problemei, ınsa o subproblemaeste rezolvata o singura data;

• combinata (se combina abordarea ascendenta cu cea descendenta – tehnica memoizarii).Prin aceasta abordare se rezolva doar subproblemele care contribuie la solutia problemeisi doar o singura data .

Aplicatia 1. Calculul coeficientilor binomiali C(n, k). Pentru rezolvarea problemei, amintimformula de recurenta:

C(n, k) =

0 , daca n < k,

1 , daca k = 0 sau k = n,

C(n− 1, k) + C(n− 1, k − 1) , altfel.

Varianta de implementare a formulei folosind o functie recursiva nu este recomandata, fiind unaredundanta, aceeasi valoare fiind calculata de mai multe ori (complexitate exponentiala). Alegemsa folosim metoda programarii dinamice, valorile coeficientilor binomiali calculandu-se progresiv.Aceste valori vor fi salvate ıntr-o matrice patratica de ordin n + 1, C. Doar partea inferioaraa matricei ımpreuna cu diagonala sa principala vor fi ıncarcate. Vom construi triunghiului luiPascal pana la o pereche data (n, k). Complexitatea algoritmului este de ordinul O(nk). Dacase cere sa se calculeze doar valoarea C(n, k) se poate folosi ca spatiu de stocare un tablouunidimensional de dimensiune k.

#include<iostream>#include<f stream>#define dim 100using namespace std ;

int main ( ){

unsigned n , k ;unsigned C[ dim ] [ dim ] ;cout<<”n : ” ;c in>>n ;cout<<”k , k <= n : ” ;c in>>k ;while ( k > n){

2


cout<<”k , k <= n : ” ;c in>>k ;

}ofstream o u t f i l e ( ” combinari . txt ” ) ;C [ 0 ] [ 0 ] = 1 ;o u t f i l e <<C[0] [0] << endl ;for (unsigned i = 1 ; i <= n ; i++){

for (unsigned j = 0 ; j <= i ; j++){

i f ( j = = 0 | | j = = i )C[ i ] [ j ] = 1 ;

elseC[ i ] [ j ] = C[ i −1] [ j −1] + C[ i −1] [ j ] ;

o u t f i l e <<C[ i ] [ j ]<<” ” ;}o u t f i l e <<endl ;

}o u t f i l e <<endl<<”Am generat t r i u n g h i u l l u i Pasca l pana l a ”

<<” perechea data ( ”<<n<<” , ”<<k<<” ) ”<<endl ;o u t f i l e <<”C( ”<<n<<” , ”<<k<<” ) = ”<<C[ n ] [ k]<<endl ;o u t f i l e . c l o s e ( ) ;return 0 ;

}

Astfel, pentru n = 10 si k = 6, obtinem

combinari.txt

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

1 10 45 120 210 252 210 120 45 10 1

Am generat triunghiul lui Pascal pana la pereche data (10,6)

C(10,6) = 210

Aplicatia 2. O cladire este formata din camere dispuse ıntr-un grid cu m × n elemente. Intredoua camere se poate trece doar daca acestea sunt alaturate pe linie sau pe coloana. La iesireadin camera (m,n) se afla o comoara. Un cautator de comori intra ın cladire prin camera (1, 1).

3


Pentru fiecare camera ın care intra i se cere sa plateasca o taxa (numar natural). Determinatisuma minima pe care trebuie sa o plateasca cautatorul de comori pentru a ajunge la comoaramult dorita.

Vom pastra ıntr-o matrice A = (aij), i = 1,m, j = 1, n, taxele care trebuie platite la trecerea

prin fiecare camera (i, j). In matricea S = (sij), i = 1,m, j = 1, n, vom calcula sumele partialede plata prin parcurgerea drumului de la camera (1, 1) la camera (i, j). Astfel, obtinem formulade recurenta:

si,j =

ai,j , daca i = 1 si j = 1,

si−1,j + ai,j , daca i ≥ 2 si j = 1,

si,j−1 + ai,j , daca j ≥ 2 si i = 1,

minim(si−1,j ; si,j−1) + ai,j , altfel.

Solutia optimala a problemei va fi calculata ın sm,n.

Datele de intrare se citesc din fisierul comoara.txt astfel: pe prima linie sunt numerele naturalem si n, separate prin spatii. Apoi pe fiecare din cele m linii, sunt n numere naturale, separateprin spatii, corespunzatoare taxelor aferente fiecarei camere.Data de iesire, solutia optimala a problemei, se va scrie ın acelasi fisier, la sfarsit.

#include<iostream>#include<f stream>using namespace std ;

int a [ 1 0 0 ] [ 1 0 0 ] , s [ 1 0 0 ] [ 1 0 0 ] , m, n ;o f s t ream o u t f i l e ( ”comoara . txt ” , i o s : : app ) ;

int min( int a , int b){

i f ( a < b) return a ;else return b ;

}

void comoara ( ){

int i , j ;s [ 0 ] [ 0 ] = a [ 0 ] [ 0 ] ;for ( j = 1 ; j < n ; j++)

s [ 0 ] [ j ] = s [ 0 ] [ j −1] + a [ 0 ] [ j ] ;for ( i = 1 ; i < m; i++)

s [ i ] [ 0 ] = s [ i −1 ] [ 0 ] + a [ i ] [ 0 ] ;for ( i = 1 ; i < m; i++)

for ( j = 1 ; j < n ; j++)s [ i ] [ j ] = min ( s [ i −1] [ j ] , s [ i ] [ j −1]) + a [ i ] [ j ] ;

o u t f i l e <<”Suma minima de p la ta : ”<<s [m−1] [n−1]<<endl ;}

int main ( )

4


{i f s t r e a m i n f i l e ( ”comoara . txt ” ) ;i f ( ! i n f i l e ){

cer r<<” Eroare l a de s ch ide r ea f i s i e r u l u i ”<<endl ;e x i t ( 1 ) ;

}int i , j ;i n f i l e >>m>>n ;for ( i = 0 ; i < m; i++)

for ( j = 0 ; j < n ; j++)i n f i l e >>a [ i ] [ j ] ;

i n f i l e . c l o s e ( ) ;comoara ( ) ;o u t f i l e . c l o s e ( ) ;return 0 ;

}

De exemplu,

4 3

5 7 4

7 9 3

2 6 1

3 2 8

Suma minima de plata: 27

Aplicatia 3. Problema rucsacului, varianta ın care nu se permite fractionarea obiectelor. Avemla dispozitie n obiecte, fiecare cu o anumita greutate gi si un anumit castig ci, i = 1, n, cares-ar obtine prin transportul obiectului i ın ıntregime. Se pune problema ce obiecte sa selectampentru a le transporta cu un rucsac care permite o greutate maxima G, astfel ıncat sa obtinemun castig maxim.

Am vazut ca, ın acest caz, ın care nu este permisa fractionarea obiectelor, metoda Greedy nu nefurnizeaza ıntotdeauna solutia optima.

Presupunem ca macar un obiect are greutatea mai mica decat G. Vom folosi tabloul bidimen-sional D, cu n + 1 linii si G + 1 coloane, ın care vom pastra solutiile subproblemelor: D[i][j]este cel mai bun castig obtinut pentru primele i obiecte, avand greutatea ınsumata j. Solutiase construieste astfel: daca D[n][G] este castigul maxim obtinut prin selectarea unei submultimide obiecte din cele n disponibile, care nu depasesc greutatea totala care poate fi transportata ınrucsac, G, atunci relatia de recurenta este:

D[n][G] = maxim(D[n− 1][G], D[n− 1][G− gn] + cn).

Astfel, castigul maxim se obtine fie fara a adauga obiectul n, ramanand la castigul obtinut pentrun − 1 obiecte, fie prin adaugarea obiectului n, caz ın care se adauga la castigul obtinut pentru

5


n−1 obiecte si greutate G−gn, cel rezultat prin transportul obiectului n. Ideea algoritmului estedeci urmatoarea: la fiecare pas, la solutia curenta ori nu adaugam deloc obiectul i, si ramanemla castigul obtinut pentru i − 1 obiecte, ori adaugam obiectul i, caz ın care adaugam castigulrezultat prin transportul lui la cel obtinut pentru primele i−1 obiecte si greutate j−gi. Obtinemformula de recurenta:

D[i][j] =

0 , daca i = 0 sau j = 0,

D[i− 1][j] , daca i > 0 si j < gi,

maxim(D[i− 1][j], D[i− 1][j − gi] + ci) , daca i > 0 si j ≥ gi.


int D[ dim ] [ dim ] , g [ dim ] , c [ dim ] , n , G, s o l [ dim ] , S [ dim ] [ dim ] ;o f s t ream fout ( ” rucsac . txt ” , i o s : : app ) ;

int max( int a , int b){

i f ( a > b) return a ;else return b ;

}

// var ian ta ascendentavoid rucsac1 ( ){

int i , j ;// t a b l o u l D are n+1 l i n i i s i G+1 co loanefor ( i = 0 ; i < n ; i++){

for ( j = 0 ; j <= G; j++)i f ( j < g [ i ] )

D[ i +1] [ j ] = D[ i ] [ j ] ;else

D[ i +1] [ j ] = max(D[ i ] [ j ] , D[ i ] [ j−g [ i ] ]+ c [ i ] ) ;}fout<<” Cas t i gu l t o t a l : ”<<D[ n ] [G]<<endl ;

}

// t ehn i ca memoizari iint rucsac2 ( int i , int j ){

// implementare r e cu r s i v a// v a l o r i l e in termed iare necesare o b t i n e r i i s o l u t i e i se s tocheazai f ( i = = 0 | | j = = 0)

6


{S [ i ] [ j ] = 0 ;return S [ i ] [ j ] ;

}else

i f (S [ i ] [ j ] != −1)return S [ i ] [ j ] ;

else{

i f ( j < g [ i ] )S [ i ] [ j ] = rucsac2 ( i −1, j ) ;

elseS [ i ] [ j ] = max( rucsac2 ( i −1, j ) ,rucsac2 ( i −1, j−g [ i ] ) + c [ i ] ) ;

return S [ i ] [ j ] ;}

}

void con s t ru c tSo l ( ){

int i = n , j = G;while (D[ i ] [ j ]>0){

i f (D[ i ] [ j ] = = D[ i −1] [ j ] )i = i − 1 ;

else{

s o l [ i −1] = 1 ;j = j − g [ i −1] ;i = i − 1 ;

}}

}

int main ( ){

i f s t r e a m f i n ( ” rucsac . txt ” ) ;i f ( ! f i n ){

cout<<” Eroare l a de s ch ide r ea f i s i e r u l u i . ”<<endl ;e x i t ( 1 ) ;

}f i n>>n ;f i n>>G ;for ( int i = 0 ; i < n ; i++ )

f in>>g [ i ] ;

7


for ( int i = 0 ; i < n ; i++ )f in>>c [ i ] ;

f i n . c l o s e ( ) ;

fout<<” 1 . Varianta ascendenta . ”<<endl ;rucsac1 ( ) ;fout<<” Ob i e c t e l e s e l e c t a t e : ” ;c on s t ru c tSo l ( ) ;for ( int i = 0 ; i < n ; i++)

i f ( s o l [ i ] )fout<<i+1<<” ” ;

fout<<endl ;

fout<<endl<<” 2 . Tehnica memoizar i i . ”<<endl ;// i n i t i a l i z a r e a mat r i c e i cu o va l oare v i r t u a l afor ( int i = 0 ; i <= n ; i++ )

for ( int j = 0 ; j <= G; j++)S [ i ] [ j ] = −1;

int optim = rucsac2 (n , G) ;fout<<” Cas t i gu l t o t a l : ”<<optim<<endl ;fout<<endl ;f out . c l o s e ( ) ;return 0 ;

}

Pentru datele de intrare: n = 3, G = 7, g1 = 5, g2 = 3, g3 = 4, c1 = 6, c2 = 3, c3 = 4, am vazutca metoda Greedy nu ofera solutia optima. Algoritmul implementat prin tehnica programariidinamice ne conduce la solutia optima a problemei.

rucsac.txt

3 7

5 3 4

6 3 4

1. Varianta ascendenta:

Castigul total: 7

Obiectele selectate: 2 3

2. Tehnica memoizarii:

Castigul total: 7

Aplicatia 4. Plata restului cu un numar minim de bancnote. Un vanzator trebuie sa dearest unui client o suma de bani S, avand la dispozitie bancnote de valori b1, b2, ..., bn ın numarnelimitat. Stiind ca vanzatorul intentioneaza sa foloseasca un numar cat mai mic de bancnote sica are la dispozitie ıntotdeauna bancnote de valoare 1, sa se afiseze modalitatea optima de plataa restului.

8


Vom folosi tabloul unidimensional C cu S+1 componente pentru a salva solutiile subproblemelor:C[j] reprezinta numarul minim de bancnote de tipul b1, b2, ..., bn folosite pentru plata sumei j.Numarul minim de bancnote necesar platii sumei S (solutia optimala a problemei) va fi calculatın C[S]. Daca pentru plata optima a sumei j se foloseste o bancnota de tipul bi, atunci numarulde bancnote creste cu o unitate si se reduce corespunzator suma de plata. Astfel vom avea

C[j] = 1 + C[j − bi].

Pentru fiecare suma ramasa de plata j, j = 0, S, alegem acea bancnota bi din cele n tipuri debancnote, care satisface restrictia bi ≤ j si care minimizeaza 1 + C[j − bi]. Evident, daca sumade plata este 0, atunci solutia optima a problemei este 0.

Obtinem astfel formula recursiva de calcul:

C[j] =

{0 , daca j = 0,

minimi:bi≤j(1 + C[j − bi]) , daca j ≥ 1.

Pe masura ce se completeaza solutia optima, tipul bancnotei folosite este pastrat ıntr-un tablousuplimentar. Complexitatea algoritmului este de ordinul lui O(nS).


int C[ dim ] , b [ dim ] , n , S , s [ dim ] ;o f s t ream fout ( ” r e s t . txt ” , i o s : : app ) ;

int min( int a , int b){

i f ( a < b) return a ;else return b ;

}

void plataS ( ){

int i , j ;// t a b l o u l C are S+1 elementeC[ 0 ] = 0 ;for ( j = 1 ; j <= S ; j++){

C[ j ] = INT MAX;for ( i = 0 ; i < n ; i++)

i f (b [ i ] <= j && 1 + C[ j−b [ i ] ] < C[ j ] ){

C[ j ] = 1 + C[ j−b [ i ] ] ;s [ j ] = b [ i ] ;

}

9


}fout<<”Numarul minim de bancnote : ”<<C[ S]<<endl ;

}

void con s t ru c tSo l ( int j ){

i f ( j > 0){

con s t ru c tSo l ( j − s [ j ] ) ;fout<<s [ j ]<<” ” ;

}}

int main ( ){

i f s t r e a m f i n ( ” r e s t . txt ” ) ;i f ( ! f i n ){

cout<<” Eroare l a de s ch ide r ea f i s i e r u l u i . ”<<endl ;e x i t ( 1 ) ;

}f i n>>n ;f i n>>S ;for ( int i = 0 ; i < n ; i++ )

f in>>b [ i ] ;f i n . c l o s e ( ) ;p lataS ( ) ;fout<<” Bancnotele s e l e c t a t e : ” ;c on s t ru c tSo l (S ) ;f out . c l o s e ( ) ;return 0 ;

}

Daca vrem sa platim suma S = 129, cu un numar minim de bancnote de tipul b1 = 12, b2 = 5,b3 = 1 si b4 = 25, algoritmul Greedy corespunzator nu ne furnizeaza solutia optima. In schimb,algoritmul proiectat folosind programarea dinamica construieste solutia optima a problemei.

rest.txt

4 129

12 5 1 25

Numarul minim de bancnote: 7

Bancnotele selectate: 25 25 25 25 5 12 12

Aplicatia 5. Cel mai lung subsir ordonat crescator (CMLSC) al unui sir oarecare. Se consideraun sir v oarecare de n elemente numere ıntregi, v1, v2, ..., vn. Se cere sa se determine CMLSC al

10


sirului.

Pentru a calcula lungimea CMLSC vom calcula mai ıntai lungimile celor mai lungi subsiruricrescatoare care ıncep cu fiecare element al vectorului. Vom memora ın L[k] lungimea CMLSCcare ıncepe de la pozitia k si pana la sfarsitul sirului initial. Tabloul unidimensional L are nelemente. Pentru ultimul element, L[n− 1] = 1. Calculam apoi pe rand L[n− 2], ..., L[1], L[0].Lungimea CMLSC va fi data de cea mai mare valoare a vectorului L.

Vrem sa calculam L[k]. Pentru aceasta, trebuie mai ıntai sa calculam lungimea CMLSC dindreapta lui k, subsir al carui prim element este mai mare sau egal cu elementul de pe pozitiak. Dar aceasta lungime o putem determina ın acelasi mod. Obtinem urmatoarea formula derecurenta:

L[k] =

{1 , k = n− 1,

1 + maximi:k<i<n,v[k]≤v[i]L[i] , k = 0, 1, ..., n− 2.

Pentru a afisa si elementele CMLSC, folosim un vector suplimentar, next, ın care retinem pepozitia k indexul primului element al subsirului folosit pentru calcularea lui L[k].

#include<iostream>using namespace std ;

void CMLSC( int ∗v , int n){

int Lmax , s ta r t , i , k ;int ∗L = new int [ n ] ;int ∗next = new int [ n ] ;L [ n−1] = 1 ;Lmax = 1 ;s t a r t = n−1;next [ n−1] = n−1;for ( k = n − 2 ; k >= 0 ; k−−){

L [ k ] = 1 ;next [ k ] = k ;for ( i = k + 1 ; i < n ; i++)

i f ( v [ k ] <= v [ i ] && L [ k ] <= L [ i ] ){

L [ k ] = L [ i ] + 1 ;next [ k ] = i ;

}i f (L [ k ] > Lmax){

Lmax = L [ k ] ;s t a r t = k ; // p o z i t i a de incepu t a s u b s i r u l u i

}}cout<<”Lungimea CMLSC: ”<<Lmax<<endl ;cout<<” Acesta e s t e : ”<<v [ s t a r t ]<<” ” ;

11


for ( i = 1 ; i < Lmax ; i++){

s t a r t = next [ s t a r t ] ;cout<<v [ s t a r t ]<<” ” ;

}cout<<endl ;delete L ;delete next ;

}

int main ( ){

int n , ∗v ;cout<<”Lungimea s i r u l u i : ” ;c in>>n ;v = new int [ n ] ;cout<<” Elemente le s i r u l u i : ” ;for ( int i = 0 ; i < n ; i++ )

cin>>v [ i ] ;CMLSC(v , n ) ;return 0 ;

}

De exemplu, pentru n = 15 si v[ ] = {34, 1, 3, 5, 45, 23, 0,−5, 39, 40, 234,−7,−10, 56, 45}, obtinemLmax = 7 si CMLSC: {1, 3, 5, 23, 39, 40, 234}.

12

curs13

Documents