Programare dinamica Descriere Probleme clasice Probleme propuse Descriere

 Programare dinamica

1. Descriere

2. Probleme clasice
3. Probleme propuse

Descriere

Programare dinamica presupune rezolvarea unei probleme prin descompunerea ei in subprobleme si rezolvarea acestora. Spre deosebire de divide-et-impera, subproblemele nu sunt disjuncte, ci se suprapun.

Pentru a evita recalcularea portiunilor care se suprapun, rezolvarea se face pornind de la cele mai mici subprobleme si folosindu-ne de rezultatul acestora calculam subproblema imediat mai mare. Cele mai mici subprobleme sunt numite subprobleme unitare. Acestea pot fi rezolvate intr-o complexitate constanta, ex: cea mai mare subsecventa dintr-o multime de un singur element.
Pentru a nu recalcula solutiile subproblemelor ce ar trebui rezolvate de mai multe ori, pe ramuri diferite, se retine solutia subproblemelor folosind o tabela (matrice uni, bi sau multi- dimensionala in functie de problema) cu rezultatul fiecarei subprobleme. Aceasta tehnica se numeste memorizare.
Aceasta tehnica afla „valoarea” solutiei optime pentru fiecare din subprobleme. Mergand de la subprobleme mici la subprobleme din ce in ce mai mari ajungem sa gasim „valoarea” problemei intregi. Motivul pentru care aceasta tehnica se numeste Programare Dinamica este datorat flexibilitatii ei, „valoarea” schimbandu-si intelesul logic de la o problema la alta. In probleme de minimizarea costului, „valoarea” este acest cost minim. In probleme de aflarea unei componente maxime,

„valoarea” este dimensiunea componentei.

Dupa calcularea valorii pentru toate subproblemele se pot afla efectiv elementele ce alcatuiesc solutia.

„Reconstructia” solutiei se face mergand din subproblema in subproblema incepand de la problema cu

valoarea optima si ajungand in subprobleme unitare. Metoda admite nuante in cazuri particulare, o sa

se inteleaga mai bine din exemple.

Aplicand aceasta tehnica determinam una din solutiile optime, problema putand avea mai multe solutii optime. In cazul in care se doreste determinarea tuturor solutiilor optime, algoritmul trebuie combinat cu unul de backtracking in reconstructia solutiilor.
Dupa cum probabil ati intuit deja, diferenta majora dintre cele doua metode prezentate este ca algoritmul greedy mentine doar solutiile partiale de la pasul curent pentru a le folosi la pasul urmator, in timp ce programarea dinamica poate utiliza la un pas subsolutii generate la oricare alt pas anterior.
Exemple de probleme:
Programarea Dinamica este cea mai flexibila tehnica din programare. Cel mai usor mod de a o intelege este parcurgerea cat mai multor exemple.
O problema clasica de Programare Dinamica este determinarea celui mai lung subsir strict crescator dintr-un sir de numere. Un subsir al unui sir este format din caractere (nu neaparat consecutive) ale sirului respectiv, in ordinea in care acestea apar in sir.

Exemplu: pentru sirul 24 12 15 15 8 19 raspunsul este sirul 12 15 19

Se observa ca daca incercam o abordare greedy nu putem stabili nici macar elementul de inceput intr- un mod corect.
Se poate rezolva si cu un algoritm care alege toate combinatiile de numere din sir, valideaza ca sirul obtinut este strict crescator si il retine pe cel de lungime maxima, dar aceasta abordare are complexitatea temporala O(2N). Cu optimizari este posibil sa se ajunga la O(N!).
O metoda de rezolvare mai eficienta foloseste Programarea Dinamica.

Incepem prin a stabili pentru fiecare element lungimea celui mai lung subsir strict crescator care incepe cu primul element si se termina in elementul respectiv.

Numim aceasta valoare besti si aplicam formula recursiva besti = 1

+ max(bestj), cu j
elem 24 12 15 15 8 19 best 1 1 2 2 1 3
Pentru 24 sau 12 nu exista nici un alt element in stanga lor strict mai mici decat ele, de aceea au best egal cu 1. Pentru elementele 15 se poate gasi in stanga lor 12 strict mai mic decat ele. Pentru 19 se gaseste elementul 15 strict mai mic decat el. Cum 15 deja este capat pentru un subsir-solutie de 2 elemente, putem spune ca 19 este capatul pentru un subsir-solutie de 3 elemente.
Cum pentru fiecare element din multime trebuie sa gasim un element mai mic decat el si cu best maxim, avem o complexitate O(N) pentru fiecare element. In total rezulta o complexitate O(N2). Se pot obtine si rezolvari cu o complexitate mai mica folosind structuri de date avansate. Atat solutia in O(N2), cat si o solutie in O(NlogN) poate fi gasita la [5]. Tot acolo se poate gasi si o lista de probleme mai dificile ce folosesc tehnica Programarii Dinamice, adaptata in diferite forme.
Pentru a gasi care sunt elementele ce alcatuiesc subsirul strict crescator putem sa retinem si o „cale de intoarcere”. Reconstructia astfel are complexitatea O(N). Exemplu: subproblema care se termina in elementul 19 are subsirul de lungime maxima 3 si a fost calculata folosind subproblema care se termina cu elementul 15 (oricare din ele). Subsirul de lungime maxima care se termina in 15 a fost calculat folosindu-ne de elementul 12. 12 fiind cel mai mic element din subsir marcheaza sfarsitul reconstructiei.
O alta problema cu o aplicare clasica a Programarii Dinamice este si determinarea celui mai lung subsir comun a doua siruri de caractere. Descrierea problemei, indicatii de rezolvare si o modalitate de evaluare a solutiilor voastre poate fi gasita la [6].
O problema care admite o varietate mare de soltii este cea a subsecventei de sume maxime. Enuntul poate fi gasita la [7]. Daca se studiaza rezolvariile la aceasta problema se poate observa ca cea cu Programare Dinamica este printe cele mai usoare de implementat.
Programarea Dinamica poate fi descompusa in urmatoarea secventa de pasi:

1. Descoperirea structurii si "masurii" pe care o are o solutie optima.

2. Determinarea unei metode de calcul recursive pentru a afla valoarea fiecarei subprobleme.

3. Calcularea "de jos in sus" a acestei valori (de la subproblemele cele mai mici la cele mai mari)

4. Reconstructia solutiei optime pornind de la rezultatele obtinute anterior

Programarea dinamică este o metodă de elaborare a algoritmilor, care se aplică de regulă problemelor în care se cere determinarea unui optim referitor la un anumit criteriu (cel mai lung subşir, cea mai mare sumă, cel mai scurt drum etc). Termenul a fost introdus în 1940 de către matematicianul american Richard Bellman. O problemă ar putea fi rezolvată prin programare dinamică dacă poate fi descompusă în subprobleme asemănătoare de dimensiuni mai mici şi soluţia optimă a problemei depinde de soluţiile optime ale subproblemelor sale.

Dar acest lucru nu garantează că programarea dinamică e soluţia, sunt situaţii în care se poate aplica cu succes metoda Greedy sau Divide et Impera. Dacă însă subproblemele nu sunt independente, ci se suprapun (Overlapping subproblems), un algoritm Divide et Impera ar duce la un timp mare de execuţie, pe motiv că o aceeaşi subproblemă se rezolvă de mai multe ori.
Să analizăm calculul coeficientului binomial

O funcţie recursivă ar arăta astfel:

int comb(int n, int k){

if (k==0 || k==n) return 1;
else return comb(n-1,k)+comb(n-1,k-1);
}

Multe din valorile comb(n,k) sunt calculate în mod repetat, ceea ce face această abordare neeficientă. În astfel de situaţii în care există un număr relativ mic de subprobleme independente, restul suprapunându-se, soluțiile subproblemelor nu vor fi calculate decât o singură dată şi vor fi reţinute într-o structură de date internă (de obicei un tablou). În acest caz, funcţia se poate scrie:

int c[100][100],k,n;
void comb(){
for(int i=0;i<=n;i++)
   c[i][0]=c[i][i]=1;
for(i=1;i<=n;i++)
   for(int j=1;j      c[i][j]=c[i-1][j]+c[i-1][j-1];
}

c[n][k] este elementul căutat. Am completat astfel triunghiul lui Pascal:

Acelaşi lucru se poate spune despre calculul termenilor şirului lui Fibonacci: o funcţie recursivă ar calcula în mod repetat aceiaşi termeni, pe când un vector poate reţine termenii calculaţi o singură dată:

int f[100],n;

f[0]=f[1]=1;

for(int i=2;i<=n;i++)
   f[i]=f[i-1]+f[i-2];

Putem spune că metoda Divide et Impera operează de sus în jos (top-down), descompunând problema în subprobleme din ce în ce mai mici, pe care le rezolvă apoi separat. Programarea dinamică operează de jos în sus (bottom-up). Se porneşte de obicei de la cele mai mici subprobleme. Combinând soluţiile lor, se obţin soluţii pentru subprobleme din ce in ce mai mari, până se ajunge, în final, la soluţia problemei iniţiale.

Rezolvarea unei probleme prin programare dinamică presupune următorii paşi:
• Se identifică subproblemele problemei date;
• Se alege o structură de date suplimentară, care să reţină soluţiile subproblemelor;
• Se caracterizează substructura optimală a problemei printr-o relaţie de recurenţă;
• Pentru a determina soluţia optimă, se rezolvă relaţia de recurenţă în mod bottom-up (se rezolvă subproblemele în ordinea crescătoare a dimensiunii lor).

Probleme clasice care se rezolvă prin programare dinamică

1. Cel mai lung subsir crescator
Fie un şir de n numere naturale. Se cere să se găsească cel mai lung subşir crescător al său.
Exemplu: şirul {2, 4, 3, 5, 3, 6} are cel mai lung subsir crescator de lungime 4: {2, 4, 5, 6} sau {2, 3, 5, 6}.

Rezolvare:

Soluţia problemei nu este unică, dar lungimea maximă a subşirului crescător, da.
Vom nota cu L[k] lungimea celui mai lung subşir crescător care începe de la poziţia k şi până la sfârşitul şirului iniţial. Calculăm, pe rând, L[n], L[n-1], L[n-2] … L[2], L[1]. Lungimea celui mai lung subşir crescător va fi dată de cea mai mare valoare a lui L.

L[n] = 1
L[k] = 1+ max {L[i ], unde k

#include
int v[10000],n,i,L[1000],max,mx,k,t;

int main(){

fstream f("subsir.txt",ios::in);
for(i=1;i<=n;i++) f>>v[i];
L[n]=1; //subsir maxim de lung 1
for(k=n-1;k>0;k--)
   {mx=0;
   for(i=k+1;i<=n;i++)
      if(v[i]>=v[k] && L[i]>mx)
         mx=L[i];
   L[k]=mx+1; 
   if(L[k]>max)
      {max=L[k];
      t=k;}
   }
cout<<"lungimea maxima:"<//afisarea subsirului
cout<for(i=t+1;i<=n;i++)
  if ((v[i]>=v[t]) && (L[i]==max-1))
     {cout<}

2. Subşir comun maximal

Fie X=(x1, x2, ..., xn) şi Y=(y1, y2, ..., ym) două şiruri de n, respectiv m numere întregi. Determinaţi un subşir comun de lungime maximă.

Exemplu:
Pentru X=(2,5,5,6,2,8,4,0,1,3,5,8) şi Y=(6,2,5,6,5,5,4,3,5,8) o soluţie posibilă este: Z=(2,5,5,4,3,5,8)

Rezolvare:
Notăm cu Xk=(x1, x2, ..., xk) (prefixul lui X de lungime k) şi cu Yh=(y1, y2, ..., yh) prefixul lui Y de lungime h. O subproblemă a problemei date constă în determinarea celui mai lung subşir comun al lui Xk, Yh. Notăm cu LCS(k,h) lungimea celui mai lung subşir comun al lui Xk, Yh. Utilizând aceste notaţii, problema cere determinarea LCS(n,m), precum şi un astfel de subşir.
Pentru a reţine soluţiile subproblemelor vom utiliza o matrice cu n+1 linii şi m+1 coloane, denumită LCS. Linia şi coloana 0 sunt iniţializate cu 0, iar elementul LCS[k][h] va fi lungimea celui mai lung subşir comun al şirurilor Xk şi Yh. Vom caracteriza substructura optimală a problemei prin următoarea relaţie de recurenţă:

h din {1,2,..,m}k din {1,2,..,n}, lcs[k][0]=lcs[0][h]=0,

lcs[k][h]=1+lcs[k-1][h-1], dacă x[k]=y[h]
max{lcs[k][h-1], lcs[k-1][h]}, dacă x[k]<>y[h]

#include

int x[100],y[100],n,m;
int lcs[100][100],max;

void rezolva(){

for(int k=1;k<=n;k++)
   for(int h=1;h<=m;h++)
      if(x[k]==y[h]) lcs[k][h]=1+lcs[k-1][h-1];
      else
      if (lcs[k-1][h]>lcs[k][h-1]) lcs[k][h]=lcs[k-1][h];
      else lcs[k][h]=lcs[k][h-1];
}
      
void afiseaza_solutie_max(int k,int h)

{
if(lcs[k][h])

     if(x[k]==y[h])
       {afiseaza_solutie_max(k-1,h-1);
       cout<     else
        {if (lcs[k][h]==lcs[k-1][h])
         afiseaza_solutie_max(k-1,h);
         else if (lcs[k][h]==lcs[k][h-1])
         afiseaza_solutie_max(k,h-1);    

}

}

int main()

{
ifstream f("lcs.txt",ios::in);

f>>n>>m;
for(int i=1;i<=n;i++) f>>x[i];
for(i=1;i<=m;i++) f>>y[i];
rezolva();
afiseaza_solutie_max(n,m);
return 0;
}

3. Sumă maximă în triunghi

Fie triunghiul format din n linii (1

Determinaţi cea mai mare sumă de numere aflate pe un drum între numărul de pe prima linie şi un număr de pe ultima linie. Fiecare număr din acest drum este situat sub precedentul, la stânga sau la dreapta acestuia.

Rezolvare
1. Vom reţine triunghiul într-o matrice pătratică T, de ordin n, sub diagonala principală. Subproblemele problemei date constau în determinarea sumei maxime care se poate obţine din numere aflate pe un drum între numărul T[i ][j], până la un număr de pe ultima linie, fiecare număr din acest drum fiind situat sub precedentul, la stânga sau la dreapta sa. Evident, subproblemele nu sunt independente: pentru a calcula suma maximă a numerelor de pe un drum de la T[i ][j] la ultima linie, trebuie să calculăm suma maximă a numerelor de pe un drum de la T[i+1][j] la ultima linie şi suma maximă a numerelor de pe un drum de la T[i+1][j+1] la ultima linie.
2. Pentru a reţine soluţiile subproblemelor, vom utiliza o matrice suplimentară S, pătratică de ordin n, cu semnificaţia
S[i ][j]= suma maximă ce se poate obţine pe un drum de la T[i ][j] la un element de pe ultima linie, respectând condiţiile problemei.
Soluţia problemei va fi S[1][1].
3. Relaţia de recurenţă care caracterizează substructura optimală a problemei este:
i din {1,2,...,n}S[n][ i]=T[n][i ],
S[i ][j]=T[i ][j]+max{S[i+1][j], S[i+1][j+1]}

Secvenţa de program este:

for (i=1; i<=n; i++) S[n][i]=T[n][i];
for (i=n-1; i>=1; i--)
    for (j=1; j<=i; j++)
        {if (S[i+1][j]               S[i][j]=T[i][j]+S[i+1][j+1]);
else
S[i][j]=T[i][j]+S[i+1][j];}

Probleme propuse:

1. Împărţirea unei mulţimi în 2 submulţimi de sume cât mai apropiate

La sfarsitul noptii de Craciun, Mosul a poposit la bradul a doi frati, unde si-a golit sacul. Cand s-au trezit, fratii au intrat intr-o mare dilema: cum isi vor imparti ei cadourile mosului? Stiind ca fiecare cadou are o valoare (cuprinsa intre 1 si 100 inclusiv) si ca sunt maxim 100 de cadouri scrieti un program care sa determine sumele cadourilor fratilor, precum si modul de impartire, astfel incat sumele obtinute sa fie cele mai apropiate posibil.

Date de intrare:
In fisierul CADOURI.IN se gasesc informaţiile referitoare la cadouri: pe prima linie numarul total de cadouri, pe urmatoarea linie valorile lor.

Date de iesire: In fişierul CADOURI.OUT trebuie scrise doua sume care sunt cele mai apropiate corespunzătoare unei impartiri a cadourilor, pe a doua linie valorile corespunzătoare cadourilor care însumează prima suma găsită, pe a treia linie, valorile corespunzătoare cadourilor care însumează a doua suma găsită.

Exemplu:
CADOURI.IN CADOURI.OUT
7 48 49
28 7 11 8 9 7 27 28 11 9
7 8 7 27

2. Sumă maximă

Se consideră un şir de N (N£1000) numere naturale cuprinse între 1 şi 10.000. Să se determine o sumă maximă de componente ale şirului astfel încât în sumă să nu intre două numere care se află pe poziţii consecutive în şir.
Exemplu: pentru şirul 1 10 2 40 100, suma maximă este 110 (10+100)