Ebben az oktatóanyagban megtudhatja, mi a dinamikus programozás. Ezenkívül megtalálja a dinamikus programozás és a kapzsi algoritmusok összehasonlítását a problémák megoldása érdekében.
A dinamikus programozás a számítógépes programozás olyan technikája, amely segít hatékonyan megoldani egy olyan problémaosztályt, amelyek átfedő alproblémákkal és optimális alépítménytulajdonságokkal rendelkeznek.
Az ilyen problémák magukban foglalják ugyanazon részproblémák értékének ismételt kiszámítását az optimális megoldás megtalálása érdekében.
Dinamikus programozási példa
Vegyük a fibonacci szekvencia előállításának esetét.
Ha a szekvencia F (1) F (2) F (3)… F (50), akkor az F (n) = F (n-1) + F (n-2) szabályt követi
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Figyeljük meg, hogy vannak-e átfedő részproblémák, ki kell számolnunk az F (48) értéket az F (50) és az F (49) számításához. Pontosan ez az a fajta algoritmus, ahol a dinamikus programozás ragyog.
Hogyan működik a dinamikus programozás
A dinamikus programozás úgy működik, hogy az alproblémák eredményét úgy tárolja, hogy amikor megoldásaikra szükség van, akkor kéznél vannak, és nem kell újraszámolnunk őket.
Ezt a technikát az alproblémák értékének tárolására memoizálásnak nevezzük. A tömbben lévő értékek mentésével időt spórolunk a már találkozott részproblémák kiszámítására.
var m = térkép (0 → 0, 1 → 1) fib (n) függvény, ha az n kulcs nincs a térképen mm (n) = fib (n - 1) + fib (n - 2) visszatér m (n)
A memória általi dinamikus programozás a dinamikus programozás felülről lefelé irányuló megközelítése. Az algoritmus működési irányának megfordításával, azaz az alapesettől kezdve és a megoldás felé haladva, dinamikus programozást is megvalósíthatunk alulról felfelé.
fib (n) függvény, ha n = 0 visszatér 0 egyéb var prevFib = 0, currFib = 1 ismétlés n - 1-szer var newFib = prevFib + currFib prevFib = currFib currFib = newFib visszatérő áramFib
Rekurzió vs dinamikus programozás
A dinamikus programozást leginkább rekurzív algoritmusokra alkalmazzák. Ez nem véletlen, a legtöbb optimalizálási probléma rekurziót igényel, és az optimalizáláshoz dinamikus programozást használnak.
De nem minden rekurziót használó probléma használhatja a dinamikus programozást. Hacsak nincsenek átfedő részproblémák, mint a fibonacci szekvencia problémában, a rekurzió csak megosztani és meghódítani megközelítéssel érheti el a megoldást.
Ez az oka annak, hogy egy olyan rekurzív algoritmus, mint a Merge Sort, nem tudja használni a dinamikus programozást, mert az alproblémák semmilyen módon nem fedik egymást.
Kapzsi algoritmusok vs dinamikus programozás
A kapzsi algoritmusok abban az értelemben hasonlítanak a dinamikus programozáshoz, hogy mindketten az optimalizálás eszközei.
A kapzsi algoritmusok azonban lokálisan optimális megoldásokat keresnek, más szóval mohó választást keresnek a globális optimum megtalálásának reményében. Ezért a kapzsi algoritmusok olyan találgatásokat tehetnek, amelyek akkor optimálisnak tűnnek, de költségesek lesznek a sorban, és nem garantálják a globális optimális értéket.
A dinamikus programozás viszont megtalálja az optimális megoldást az alproblémákra, majd megalapozott döntést hoz az említett részproblémák eredményeinek egyesítésével a legoptimálisabb megoldás megtalálásához.
