Metoda programării dinamice

Prof. Deac Paula - Cristina

Descrierea metodei:Metoda programării dinamice este o tehnică, care conduce la

o soluţie optimă, într-un timp de calcul de ordin polinomial. Cu toate acestea, această metodă nu se poate aplica la toate problemele, ci numai acelora care îndeplinesc anumite condiţii.

Metoda programării dinamice este aplicabilă problemelor de optim în care soluţia este privită ca rezultat al unui şir de decizii d1, d2, ..., dn. Fiecare decizie depinde de deciziile deja luate şi nu este unic determinată.

Pentru aplicarea metodei este necesară satisfacerea principiului optimalităţii:→ dacă d1,d2,...,dn este un şir optim de decizii care

transformă starea iniţială S0 în starea finală Sn trecând prin stările intermediare S1...Sn-1, atunci şirul de decizii d2,...,dn este optim pentru S1 ca stare iniţială şi Sn ca stare finlă.

→ General: Pentru orice şir de decizii d1,d2,...,dn pentru perechea (S0,Sn) şi pentru , să rezulte că d1,d2,...,di este un şir optim pentru perechea (S0,Si) sau di+1,...,dn este şir optim pentru perechea (Si, Sn). Mai general, principiul cere ca ambele şiruri să fie optime.

ClasificareDupă ce principiul optimalităţii a fost verificat, metoda

constă în a scrie relaţiile de recurenţă corespunzătoare şi a le rezolva.

Aceste relaţii sunt de 2 tipuri:Fiecare decizie di depinde de di+1,...,dn, aici aplicându-se

metoda înainte, iar deciziile se iau în ordinea dn, dn-1,..., d1.

Fiecare decizie di depinde de d1,d2...,di-1, aici aplicându-se metoda înapoi, iar deciziile se iau în ordinea d1, d2, ... , dn.

OBS: În programarea dinamică se rezolvă problema combinând soluţiile problemelor ca şi la Divide et Impera. Când subproblemele conţin subprobleme comune, în locul metodei DEI este mai avantajos să folosim metoda programării dinamice.

function c (n,k:integer): integer;Begin IF (k=0) or (k=n) THEN c := 1

ELSE c := c(n-1,k)+ c(n-1,k-1);end;

111 kn

kn

kn CCCExemplu:

Folosind această metodă, o mare parte din valori sunt calculate în mod

repetat. De exemplu, pentru c(12,7), funcţia c(1,1) este invocată de 210

ori. Memorăm rezultatele intermediare într-un tablou de forma:

0 1 2 3 ... k-1 k

0 1

1 1 1

2 1 2 1

3 1 3 3 1

... ... ... ... ... ...

n-1

n

11knC

knC 1

knC

Algoritm care foloseşte metoda programării dinamice

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,i]:=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;

Principiile programării dinamice1. Evitarea calculării de mai multe ori a aceloraşi subcazuri prin

memorarea rezultatelor intermediare

2. Metoda programării dinamice operează de jos în sus

( Se porneşte de la cele mai mici subcazuri, se combină rezultatele lor şi se obţin soluţii pentru cazuri din ce in ce mai mari, până se ajunge la soluţia cazului iniţial)

3. Metoda programării dinamice este folosită pentru optimizarea problemelor care satisfac principiul optimalităţii (adică într-o secvenţă optimă de decizii, fiecare subsecvenţă trebuie de asemenea să fie optimă)