Selles õpetuses saate teada, mis on dünaamiline programmeerimine. Samuti leiate võrdluse dünaamilise programmeerimise ja ahnete algoritmide vahel probleemide lahendamiseks.
Dünaamiline programmeerimine on arvuti programmeerimise tehnika, mis aitab tõhusalt lahendada klassi probleeme, millel on kattuvad alamprobleemid ja optimaalsed alamstruktuuri omadused.
Sellised probleemid hõlmavad optimaalse lahenduse leidmiseks korduvalt samade alamprobleemide väärtuse arvutamist.
Dünaamilise programmeerimise näide
Võtame näiteks fibonacci järjestuse genereerimise juhtumi.
Kui järjestus on F (1) F (2) F (3)… F (50), järgib see reeglit 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)…
Pange tähele, kuidas kattuvad alamprobleemid on, nii F (50) kui ka F (49) arvutamiseks peame arvutama F (48). See on täpselt selline algoritm, kus dünaamiline programmeerimine särab.
Kuidas dünaamiline programmeerimine töötab
Dünaamiline programmeerimine toimib alamprobleemide tulemuse salvestamise teel nii, et kui nende lahendusi vajatakse, on need käepärast ja meil pole vaja neid ümber arvutada.
Seda alamprobleemide väärtuse salvestamise tehnikat nimetatakse memosatsiooniks. Massiivi väärtuste salvestamisega säästame aega juba kokku puutunud alamprobleemide arvutamiseks.
var m = kaart (0 → 0, 1 → 1) funktsioon fib (n), kui klahvi n pole kaardil mm (n) = fib (n - 1) + fib (n - 2) tagastab m (n)
Dünaamiline programmeerimine memode abil on ülalt-alla lähenemine dünaamilisele programmeerimisele. Algoritmi töötamise suuna vastupidiseks muutmisega, st alustades baasjuhtumist ja töötades lahenduse poole, saame dünaamilise programmeerimise rakendada ka alt üles.
funktsioon fib (n) kui n = 0 tagastab 0 muud var prevFib = 0, currFib = 1 kordus n - 1 kord var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFib
Rekursioon vs dünaamiline programmeerimine
Dünaamilist programmeerimist rakendatakse enamasti rekursiivsetele algoritmidele. See pole juhus, enamik optimeerimisprobleeme nõuab rekursi ja optimeerimiseks kasutatakse dünaamilist programmeerimist.
Kuid mitte kõik rekursiooni kasutavad probleemid ei saa kasutada dünaamilist programmeerimist. Välja arvatud juhul, kui esineb kattuvaid alamprobleeme nagu fibonacci järjestuse probleemis, võib rekursioon lahenduseni jõuda ainult jagamise ja vallutamise lähenemisviisi abil.
See on põhjus, miks rekursiivne algoritm nagu Merge Sort ei saa kasutada dünaamilist programmeerimist, kuna alamprobleemid ei kattu mingil viisil.
Ahned algoritmid vs dünaamiline programmeerimine
Ahned algoritmid sarnanevad dünaamilise programmeerimisega selles mõttes, et need on mõlemad optimeerimise vahendid.
Ahned algoritmid otsivad globaalse optimaali leidmise lootuses siiski kohapeal optimaalseid lahendusi või teisisõnu ahne valikut. Seega võivad ahned algoritmid teha oletuse, mis näib hetkel optimaalne, kuid mis kulgeb liinil kulukaks ega taga globaalselt optimaalset.
Dünaamiline programmeerimine aga leiab alamprobleemidele optimaalse lahenduse ja teeb seejärel teadliku valiku nende alamprobleemide tulemuste ühendamiseks, et leida kõige optimaalsem lahendus.
