În acest tutorial, veți afla ce este programarea dinamică. De asemenea, veți găsi comparația dintre programarea dinamică și algoritmii lacomi pentru rezolvarea problemelor.
Programarea dinamică este o tehnică de programare pe computer care ajută la rezolvarea eficientă a unei clase de probleme care au suprapuneri suprapuse și proprietăți optime ale structurii.
Astfel de probleme implică calcularea în mod repetat a valorii acelorași subprobleme pentru a găsi soluția optimă.
Exemplu de programare dinamică
Să luăm cazul generării secvenței Fibonacci.
Dacă secvența este F (1) F (2) F (3)… F (50), urmează regula F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46) …
Observați cum există subprobleme suprapuse, trebuie să calculăm F (48) pentru a calcula atât F (50), cât și F (49). Acesta este exact genul de algoritm în care programarea dinamică strălucește.
Cum funcționează programarea dinamică
Programarea dinamică funcționează stocând rezultatul subproblemelor, astfel încât atunci când soluțiile lor sunt necesare, acestea sunt la îndemână și nu este nevoie să le recalculăm.
Această tehnică de stocare a valorii subproblemelor se numește memoizare. Salvând valorile din matrice, economisim timp pentru calculele subproblemelor pe care le-am întâlnit deja.
var m = hartă (0 → 0, 1 → 1) funcție fib (n) dacă tasta n nu este în hartă mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Programarea dinamică prin memoizare este o abordare de sus în jos a programării dinamice. Prin inversarea direcției în care funcționează algoritmul, adică pornind de la cazul de bază și lucrând spre soluție, putem implementa, de asemenea, programare dinamică într-un mod ascendent.
funcția fib (n) dacă n = 0 returnează altceva var prevFib = 0, currFib = 1 repetă n - de 1 ori var newFib = prevFib + currFib prevFib = currFib currFib = newFib returnează curentFib
Recursivitate vs Programare dinamică
Programarea dinamică este aplicată mai ales algoritmilor recursivi. Aceasta nu este o coincidență, majoritatea problemelor de optimizare necesită recursivitate și programarea dinamică este utilizată pentru optimizare.
Dar nu toate problemele care utilizează recursivitatea pot utiliza programarea dinamică. Cu excepția cazului în care există prezența unor subprobleme care se suprapun ca în problema secvenței Fibonacci, o recursivitate poate ajunge la soluție doar folosind o abordare de divizare și cucerire.
Acesta este motivul pentru care un algoritm recursiv, precum Merge Sort, nu poate utiliza Programare dinamică, deoarece subproblemele nu se suprapun în niciun fel.
Algoritmi lacomi vs Programare dinamică
Algoritmii Greedy sunt similari cu programarea dinamică în sensul că ambele sunt instrumente de optimizare.
Cu toate acestea, algoritmii lacomi caută soluții optime la nivel local sau, cu alte cuvinte, o alegere lacomă, în speranța de a găsi un optim global. Prin urmare, algoritmii lacomi pot face o presupunere care pare optimă la momentul respectiv, dar devine costisitoare și nu garantează un optim global.
Programarea dinamică, pe de altă parte, găsește soluția optimă pentru subprobleme și apoi face o alegere în cunoștință de cauză pentru a combina rezultatele acelor subprobleme pentru a găsi cea mai optimă soluție.
