V tomto tutoriáli sa dozviete, čo je dynamické programovanie. Nájdete tiež porovnanie medzi dynamickým programovaním a chamtivými algoritmami na riešenie problémov.
Dynamické programovanie je technika počítačového programovania, ktorá pomáha efektívne riešiť triedu problémov, ktoré majú prekrývajúce sa podproblémy a optimálnu vlastnosť podštruktúry.
Takéto problémy spočívajú v opakovanom výpočte hodnoty rovnakých podproblémov s cieľom nájsť optimálne riešenie.
Príklad dynamického programovania
Vezmite prípad generovania fibonacciho sekvencie.
Ak je postupnosť F (1) F (2) F (3) … F (50), riadi sa pravidlom 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)…
Všimnite si, ako existujú prekrývajúce sa podproblémy, musíme vypočítať F (48), aby sme vypočítali F (50) aj F (49). Toto je presne ten druh algoritmu, kde svieti dynamické programovanie.
Ako funguje dynamické programovanie
Dynamické programovanie funguje tak, že sa ukladajú výsledky čiastkových problémov, takže keď sú potrebné ich riešenia, sú poruke a nemusíme ich prepočítavať.
Táto technika ukladania hodnoty čiastkových problémov sa nazýva memoizácia. Uložením hodnôt do poľa šetríme čas na výpočty čiastkových problémov, s ktorými sme sa už stretli.
var m = mapa (0 → 0, 1 → 1) funkcia fib (n), ak kláves n nie je v mape mm (n) = fib (n - 1) + fib (n - 2) návrat m (n)
Dynamické programovanie memoizáciou je prístup zhora nadol k dynamickému programovaniu. Obrátením smeru, v ktorom algoritmus funguje, tj. Že sa vychádza zo základného prípadu a pracuje sa na riešení, môžeme tiež implementovať dynamické programovanie spôsobom zdola nahor.
funkcia fib (n) ak n = 0 návrat 0 iná var prevFib = 0, currentFib = 1 opakovanie n - 1 krát var newFib = prevFib + currentFib prevFib = currentFib currentFib = newFib návratový prúdFib
Rekurzia vs dynamické programovanie
Dynamické programovanie sa väčšinou používa na rekurzívne algoritmy. Nie je to náhoda, väčšina problémov s optimalizáciou vyžaduje rekurziu a na optimalizáciu sa používa dynamické programovanie.
Ale nie všetky problémy, ktoré používajú rekurziu, môžu používať dynamické programovanie. Pokiaľ sa nevyskytujú prekrývajúce sa podproblémy, ako napríklad v probléme sekvencie fibonacci, môže rekurzia dospieť k riešeniu iba pomocou prístupu rozdelenia a panovania.
To je dôvod, prečo rekurzívny algoritmus ako Merge Sort nemôže používať dynamické programovanie, pretože podproblémy sa nijako neprekrývajú.
Chamtivé algoritmy vs dynamické programovanie
Chamtivé algoritmy sú podobné dynamickému programovaniu v tom zmysle, že sú obidvomi nástrojmi na optimalizáciu.
Chamtivé algoritmy však hľadajú lokálne optimálne riešenia alebo inými slovami chamtivú voľbu v nádeji, že nájdu globálne optimum. Preto chamtivé algoritmy môžu urobiť odhad, ktorý vyzerá v tom čase optimálne, ale stáva sa nákladným po celej čiare a nezaručuje globálne optimum.
Dynamické programovanie na druhej strane nachádza optimálne riešenie pre podproblémy a potom urobí informovanú voľbu na kombinovanie výsledkov týchto podproblémov s nájdením najoptimálnejšieho riešenia.
