Programare Dinamica

Programarea dinamică este atât o metodă de optimizare matematică, cât și o metodă de programare a computerului. Această metodă a fost dezvoltată de Richard Bellman în anii 1950 și a găsit aplicații în numeroase domenii, de la inginerie aerospațială la economie.

În ambele contexte, aceasta se referă la simplificarea unui probleme complicate prin descompunerea acesteia în sub-probleme mai simple într-un mod recursiv. Chiar dacă unele probleme de decizie nu pot fi descompuse în acest fel, deciziile care acoperă mai multe momente în timp adesea se descompun recursiv. De asemenea, în informatică, dacă o problemă poate fi rezolvată optim prin descompunerea ei în sub-probleme și apoi găsirea recursivă a soluțiilor optime pentru sub-probleme, atunci se spune că are o substructură optimală.

Dacă sub-problemele pot fi încastrate recursiv în probleme mai mari, astfel încât metodele de programare dinamică să poată fi aplicate, atunci există o relație între valoarea problemei mai mari și valorile sub-problemelor. În literatura de optimizare, această relație este numită ecuația Bellman.

Există două caracteristici cheie pe care o problemă trebuie să le aibă pentru ca programarea dinamică să poată fi aplicată: substructură optimală și suprapunere de sub-probleme. Dacă o problemă poate fi rezolvată prin combinarea soluțiilor optime la sub-probleme care nu se suprapun, atunci strategia este numită "împarte și cucerește" în loc de programare dinamică. De aceea, algoritmi precum merge sort și quick sort nu sunt clasificați ca probleme de programare dinamică.

Substructura optimală înseamnă că soluția pentru o problemă de optimizare dată poate fi obținută prin combinarea soluțiilor optime ale sub-problemelor sale. Astfel de substructuri optime sunt de obicei descrise prin recursivitate. De exemplu, dat un graf G=(V,E), cel mai scurt drum p de la un vârf u la un vârf v prezintă o substructură optimală: luăm oricare alt vârf intermediar w de-a lungul acestui drum p. Dacă p este într-adevăr cel mai scurt drum, atunci acesta poate fi împărțit în sub-drumuri p1 de la u la w și p2 de la w la v astfel încât acestea, la rândul lor, să fie într-adevăr cele mai scurte drumuri între vârfurile corespunzătoare (prin simplul argument de tăiere și lipire descris în Introducere în Algoritmi). Prin urmare, soluția pentru găsirea celor mai scurte drumuri poate fi formulată într-un mod recursiv, ceea ce fac algoritmul Bellman-Ford sau algoritmul Floyd-Warshall.

Suprapunerea de sub-probleme înseamnă că spațiul de sub-probleme trebuie să fie mic, adică orice algoritm recursiv care rezolvă problema ar trebui să rezolve aceleași sub-probleme de mai multe ori, în loc să genereze noi sub-probleme. De exemplu, să luăm formularea recursivă pentru generarea seriei Fibonacci: Fi = Fi-1 + Fi-2, cu cazul de bază F1 = F2 = 1. Atunci F43 = F42 + F41, și F42 = F41 + F40. Acum, F41 este rezolvat în sub-arborii recursivi atât pentru F43, cât și pentru F42. Chiar dacă numărul total de sub-probleme este de fapt mic (doar 43), vom ajunge să rezolvăm aceleași probleme de mai multe ori dacă adoptăm o soluție recursivă naivă. Programarea dinamică ține cont de acest fapt și rezolvă fiecare sub-problemă doar o singură dată.