Programare dinamică

Programarea dinamică (PD; engl. dynamic programming, DP) — este o metodă de rezolvare a problemelor complexe de optimizare, bazată pe descompunerea problemei inițiale într-o secvență de subprobleme mai simple. Metoda se aplică proceselor de luare a deciziilor în mai mulți pași, unde soluția optimă a întregii probleme poate fi construită din soluțiile optime ale subproblemelor sale.

Termenul a fost introdus de matematicianul american Richard Bellman în anii 1950. În acest context, cuvântul „programare" este folosit cu sensul de „planificare" sau „elaborarea unui plan optim de acțiune", și nu de scriere a unui cod de calculator.

Proprietăți cheie și teoreme

Aplicabilitatea programării dinamice la o problemă este determinată de prezența a două proprietăți fundamentale ale acesteia.

Principiul optimalității Bellman

Conceptul central al metodei este principiul optimalității Bellman (engl. Bellman's principle of optimality). Acesta afirmă: indiferent de starea inițială și de decizia inițială, deciziile ulterioare trebuie să constituie o strategie optimă în raport cu starea obținută ca urmare a primei decizii.

Cu alte cuvinte, orice porțiune a traiectoriei optime este, prin ea însăși, optimă. Această proprietate permite descompunerea problemei generale într-o secvență de subprobleme mai simple și rezolvarea lor recursivă.

Subprobleme suprapuse

O problemă posedă proprietatea subproblemelor suprapuse (engl. overlapping subproblems) dacă, în cursul rezolvării sale recursive, aceleași subprobleme apar în mod repetat. PD permite evitarea calculelor redundante prin stocarea soluțiilor subproblemelor deja întâlnite (această tehnică se numește memoizare sau tabulare), ceea ce crește semnificativ eficiența față de căutarea recursivă naivă.

Ecuația Bellman

Din principiul optimalității decurge relația de recurență fundamentală a metodei — ecuația Bellman. Aceasta leagă „valoarea" (câștigul optim sau costul) stării curente de valorile stărilor ulterioare. În forma sa generală, pentru un proces determinist în mai mulți pași cu funcție obiectiv aditivă, ea are forma:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

unde:

• $k$ — numărul pasului (de la $m$ la 1);
• $x$ — starea sistemului la pasul $k-1$;
• $y$ — decizia controlabilă luată la pasul $k$;
• ${\phi }_k(x,y)$ — câștigul (sau costul) la pasul k;
• $f_k(x,y)$ — funcția care determină noua stare a sistemului;
• $V_k(s)$ — valoarea optimă a funcției obiectiv pentru subproblema care începe la pasul $k$ în starea $s$.

Ecuația se rezolvă secvențial, de regulă „de la sfârșit", deplasându-se de la ultimul pas către primul.

Exemple de aplicare

• Problema drumului cel mai scurt într-un graf: Această problemă posedă proprietatea substructurii optime, deoarece orice porțiune a drumului cel mai scurt este ea însăși cel mai scurt drum. Algoritmii Bellman-Ford și Floyd-Warshall sunt exemple clasice de aplicare a PD pentru rezolvarea acestei probleme.
• Problema rucsacului: Problema umplerii optime a unui rucsac cu capacitate limitată cu obiecte de valori și greutăți diferite. PD permite rezolvarea acestei probleme prin examinarea secvențială a obiectelor și calcularea, la fiecare pas, a valorii maxime pentru toate valorile posibile ale capacității rămase.
• Problema alocării resurselor: Distribuirea unei resurse limitate (de exemplu, investiții) între mai multe proiecte în vederea maximizării efectului total.

Limitări

Principala limitare a metodei este blestemul dimensionalității (engl. curse of dimensionality) — termen introdus de Bellman pentru a desemna creșterea exponențială a numărului de stări și, implicit, a complexității computaționale, odată cu creșterea numărului de variabile care descriu starea sistemului. Aceasta limitează aplicarea practică a PD exacte pentru probleme de dimensiuni foarte mari.

Noțiuni conexe

• Cercetarea operațională
• Teoria controlului optim
• Procesul de decizie Markov (generalizare stochastică)
• Ecuația Hamilton — Jacobi — Bellman (analogul pentru timp continuu)