Šioje pamokoje sužinosite, kas yra dinaminis programavimas. Taip pat rasite palyginimą tarp dinaminio programavimo ir godžių algoritmų problemoms spręsti.
„Dinaminis programavimas“ yra kompiuterinio programavimo technika, padedanti efektyviai išspręsti problemų klasę, kuri turi sutampančius subproblemas ir optimalią posistemio savybę.
Tokios problemos apima pakartotinį tų pačių problemų vertės apskaičiavimą, norint rasti optimalų sprendimą.
Dinaminio programavimo pavyzdys
Imkime fibonacci sekos generavimo atvejį.
Jei seka yra F (1) F (2) F (3)… F (50), ji vadovaujasi taisykle 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)…
Atkreipkite dėmesį, kaip yra sutampančių paprogramių, kad galėtume apskaičiuoti F (50) ir F (49), turime apskaičiuoti F (48). Tai yra būtent toks algoritmas, kuriame šviečia dinaminis programavimas.
Kaip veikia dinaminis programavimas
Dinaminis programavimas veikia saugant tarpinių problemų rezultatą, kad, kai reikalingi jų sprendimai, jie būtų prieinami ir mums nereikėtų jų perskaičiuoti.
Ši subproblemų vertės saugojimo technika vadinama atmintimi. Išsaugodami masyvo reikšmes, mes sutaupome laiko jau susidūrusių problemų problemoms apskaičiuoti.
var m = žemėlapis (0 → 0, 1 → 1) funkcija fib (n), jei klavišas n nėra žemėlapyje mm (n) = fib (n - 1) + fib (n - 2) grąžina m (n)
Dinaminis programavimas atmintinėmis yra „iš viršaus į apačią“ metodas į dinaminį programavimą. Apversdami algoritmo veikimo kryptį, ty pradėdami nuo pagrindinio atvejo ir dirbdami link sprendimo, taip pat galime įgyvendinti dinaminį programavimą iš apačios į viršų.
funkcija fib (n), jei n = 0 grąža 0 kitas var prevFib = 0, currFib = 1 kartotinis n - 1 kartas var newFib = prevFib + currFib prevFib = currFib curr fibF = newFib return currentFib
Rekursija vs dinaminis programavimas
Dinaminis programavimas dažniausiai taikomas rekursiniams algoritmams. Tai nėra sutapimas, daugumai optimizavimo problemų reikia rekursijos, o optimizavimui naudojamas dinaminis programavimas.
Bet ne visos problemos, kuriose naudojamas rekursija, gali naudoti dinaminį programavimą. Jei nėra sutampančių subproblemų, kaip antai fibonacci sekos problemoje, rekursija gali pasiekti sprendimą tik naudojant padalijimo ir užkariavimo metodą.
Tai yra priežastis, kodėl rekursiškas algoritmas, pvz., „Merge Sort“, negali naudoti dinaminio programavimo, nes paprogramės jokiu būdu nesutampa.
Gobšūs algoritmai ir dinaminis programavimas
Godūs algoritmai yra panašūs į dinaminį programavimą ta prasme, kad jie abu yra optimizavimo įrankiai.
Tačiau godūs algoritmai ieško optimalių lokalių sprendimų arba, kitaip tariant, godaus pasirinkimo, tikėdamiesi rasti visuotinį optimalumą. Taigi godūs algoritmai gali padaryti spėjimą, kuris tuo metu atrodo optimalus, tačiau tampa brangus ir neužtikrina visuotinio optimalumo.
Kita vertus, dinaminis programavimas randa optimalų subproblemų sprendimą ir tada pasirenka pagrįstą šių subproblemų rezultatų derinimą, kad būtų rastas optimaliausias sprendimas.
