U ovom vodiču naučit ćete što je dinamičko programiranje. Također ćete pronaći usporedbu između dinamičkog programiranja i pohlepnih algoritama za rješavanje problema.
Dinamičko programiranje je tehnika u računalnom programiranju koja pomaže u učinkovitom rješavanju klase problema koji imaju preklapajuće podprobleme i optimalno svojstvo podstrukture.
Takvi problemi uključuju opetovano izračunavanje vrijednosti istih potproblema kako bi se pronašlo optimalno rješenje.
Primjer dinamičkog programiranja
Uzmimo slučaj generiranja fibonaccijeve sekvence.
Ako je slijed F (1) F (2) F (3) … F (50), slijedi pravilo 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)…
Primijetite kako postoje podproblemi koji se preklapaju, moramo izračunati F (48) da bismo izračunali i F (50) i F (49). To je upravo vrsta algoritma u kojem dinamičko programiranje svijetli.
Kako funkcionira dinamičko programiranje
Dinamičko programiranje funkcionira spremanjem rezultata potproblema tako da su im potrebna rješenja kad su potrebna, a mi ih ne moramo ponovno izračunavati.
Ova tehnika pohranjivanja vrijednosti potproblema naziva se memoizacija. Spremanjem vrijednosti u nizu štedimo vrijeme za izračunavanja pod-problema na koje smo već naišli.
var m = karta (0 → 0, 1 → 1) funkcija fib (n) ako ključ n nije u mapi mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Dinamičko programiranje memoizacijom pristup je dinamičnom programiranju odozgo prema dolje. Preokretanjem smjera u kojem algoritam radi, tj. Polazeći od osnovnog slučaja i radeći prema rješenju, također možemo implementirati dinamičko programiranje odozdo prema gore.
funkcija fib (n) ako je n = 0 povratak 0 inače var prevFib = 0, currFib = 1 ponovite n - 1 puta var newFib = prevFib + currFib prevFib = currFib currFib = newFib povrat strujeFib
Rekurzija vs dinamičko programiranje
Dinamičko programiranje uglavnom se primjenjuje na rekurzivne algoritme. To nije slučajno, većina problema s optimizacijom zahtijeva rekurziju, a za optimizaciju se koristi dinamičko programiranje.
Ali ne mogu svi problemi koji koriste rekurziju koristiti dinamičko programiranje. Ako nema prisutnih preklapajućih podproblema kao u problemu fibonaccijeve sekvence, rekurzija može doći do rješenja samo primjenom pristupa podijeli i osvoji.
To je razlog zašto rekurzivni algoritam poput Merge Sort ne može koristiti dinamičko programiranje, jer se podproblemi ne preklapaju ni na koji način.
Pohlepni algoritmi vs dinamičko programiranje
Pohlepni algoritmi slični su dinamičkom programiranju u smislu da su obojica alata za optimizaciju.
Međutim, pohlepni algoritmi traže lokalno optimalna rješenja ili drugim riječima, pohlepan izbor, u nadi da će pronaći globalni optimum. Stoga pohlepni algoritmi mogu pretpostaviti da u to vrijeme izgleda optimalno, ali postaje skupo i ne garantiraju globalni optimum.
S druge strane, dinamičko programiranje pronalazi optimalno rješenje za potprobleme, a zatim donosi informirani izbor da kombinira rezultate tih podproblema kako bi pronašlo najoptimalnije rješenje.
