V tej vadnici boste izvedeli, kaj je dinamično programiranje. Našli boste tudi primerjavo med dinamičnim programiranjem in požrešnimi algoritmi za reševanje problemov.
Dinamično programiranje je tehnika računalniškega programiranja, ki pomaga učinkovito rešiti vrsto problemov s prekrivajočimi se podproblemi in optimalno lastnostjo podstrukture.
Takšni problemi vključujejo večkratno izračunavanje vrednosti istih podproblemov, da bi našli optimalno rešitev.
Primer dinamičnega programiranja
Vzemimo primer generiranja fibonacijevega zaporedja.
Če je zaporedje F (1) F (2) F (3)… F (50), sledi pravilu 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)…
Upoštevajte, kako obstajajo podproblemi, ki se prekrivajo, izračunati moramo F (48), da izračunamo F (50) in F (49). To je točno tak algoritem, pri katerem dinamično programiranje zasije.
Kako deluje dinamično programiranje
Dinamično programiranje deluje tako, da shrani rezultat podproblemov, tako da so, kadar so potrebne njihove rešitve, na dosegu roke in jih ni treba preračunavati.
Ta tehnika shranjevanja vrednosti podproblemov se imenuje memoizacija. S shranjevanjem vrednosti v matriki prihranimo čas za izračune podproblemov, na katere smo že naleteli.
var m = preslikava (0 → 0, 1 → 1) funkcija fib (n), če ključa n ni na zemljevidu mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Dinamično programiranje z memoizacijo je pristop k dinamičnemu programiranju od zgoraj navzdol. Če obrnemo smer, v kateri deluje algoritem, tj. Tako, da začnemo od osnovnega primera in se usmerimo k rešitvi, lahko izvajamo tudi dinamično programiranje od spodaj navzgor.
funkcija fib (n), če je n = 0 vrnitev 0 sicer var prevFib = 0, currFib = 1 ponovitev n - 1-krat var newFib = prevFib + currFib prevFib = currFib currFib = newFib povratni tokFib
Rekurzija vs dinamično programiranje
Dinamično programiranje se večinoma uporablja za rekurzivne algoritme. To ni naključje, večina optimizacijskih problemov zahteva rekurzijo in za optimizacijo se uporablja dinamično programiranje.
Toda pri vseh težavah, ki uporabljajo rekurzijo, ni mogoče uporabiti dinamičnega programiranja. Če ni prisotnih prekrivajočih se podproblemov, kot pri problemu fibonacijevega zaporedja, lahko rekurzija rešitev doseže le s pristopom deli in vladaj.
To je razlog, zakaj rekurzivni algoritem, kot je Merge Sort, ne more uporabljati dinamičnega programiranja, ker se podproblemi nikakor ne prekrivajo.
Pohlepni algoritmi vs dinamično programiranje
Pohlepni algoritmi so podobni dinamičnemu programiranju v smislu, da so oba orodja za optimizacijo.
Pohlepni algoritmi pa iščejo lokalno optimalne rešitve ali z drugimi besedami pohlepno izbiro v upanju, da bodo našli globalni optimum. Pohlepni algoritmi lahko torej ugibajo, da je takrat videti optimalno, vendar postaja drago in ne zagotavlja globalnega optimalnega.
Dinamično programiranje pa poišče optimalno rešitev za podprobleme in se nato premišljeno odloči, da rezultate teh podproblemov kombinira, da najde najbolj optimalno rešitev.
