Programare dinamică

Programarea dinamica face parte dintr-o categorie de metode matematice numite metode de scufundare.O problemã de programare dinamicã contine subprobleme comune (care nu sunt independente) din a cãror rezolvare si combinare se obtine solutia unei (sub)probleme mai mari.Deci rezolvarea unei (sub)probleme se poate face doar dupã solutionarea (sub)problemelor, care alcãtuiesc problema respectivã.Spunem cã programarea dinamica actioneaza de jos in sus,prelucrând si combinând subcazuri mici,obtinând astfel solutia pentru subcazuri tot mai mari.

Totodatã programarea dinamicã evitã rezolvarea de mai multor ori a aceleiasi subprobleme(rezolvându-se doar problemele independente ),prin memorarea rezultatelor partiale.

Sã presupunem cã avem de rezolvat urmãtoarea problemã :

Sã se calculeze valoarea C(n,k)(combinãri de n luate câte k).

Folosim functia recursivã :

function comb(n,k;integer):integer;

begin

if (k=0)or (k=n)then comb:=1

else comb:=comb(n-1,k-1)+comb(n-1,k)

end;

Din punct de vedere al timpului de executie aceastã metodã este ineficientã ,deoarece sunt calculate se mai multe ori aceleasi valori .

Vom elimina acest dezavantaj prin evitarea recursivitatii,pãstrând într-un tabel rezultatele intermediare si luându-le de acolo ori de câte ori este necesar.Argumentele functiei ne sugereazã forma tabelului(folosindu-le ca indice de linie,respectiv coloanã),iar formula ne precizezã modul de completare al tabelului:

1, I=jÚj=0

C(I,j)=

C(I-1,j-1)+c(I-1,j) 0<j<I

Pentru exemplul precedent avem:

Function comb(n,k;integer):integer;

Var i,j:integer;

c:array[0..20,0..20]of integer;

begin

for i:=0 to n do

begin c[i,0]:=1;

c[i,1]:=1;

for j:=1 to i-1 do

c[i,j]:=c[i-1,j-1]+c[i-1,j];

end;

comb:=c[n,k];

end;

Orice algoritm de programare dinamicã poate fi descris prin urmãtorii pasi:

1)Caracterizarea structurii unei solutii optime:se defineste un vector,o matrice ,...,în care fiecare componentã va contine o solutie optimã a unei subprobleme.

2)Definirea recursivã a valorii unei solutii optime .Totodatã se defineste valoarea celei mai mici subprobleme(celor mai mici subprobleme).

Ex: c[i,0]:=1;

c[i,1]:=1;

3)Calcularea de jos în sus a valorii unei solutii optime ,tinând seama de definirea recursivã a acestei valori.

4)Dacã pe lângã valoare se mai doreste afisarea solutiei care a generat rezultatul optim ,atunci se construieste de sus în jos solutia propriu-zisã.