DINAMIČNO PROGRAMIRANJE: ZNAČILNOSTI, PRIMER, PREDNOSTI, SLABOSTI - TEHNOLOGIJA - 2026

Programiranje dinamični je model algoritem, ki rešuje kompleksen problem , ki ga tako, da ga v podprobleme, shranjevanje rezultate le-teh, da ne bi bilo treba preračunati rezultate.

Ta urnik se uporablja, kadar imate težave, ki jih je mogoče razdeliti na podobne podprobleme, tako da se njihovi rezultati lahko ponovno uporabijo. Ta urnik se večinoma uporablja za optimizacijo.

Dinamično programiranje. Podproblemi, nameščeni v Fibonaccijevem zaporedju. Vir: Wikimedia commons, en: Uporabnik: Dcoatzee, sledil uporabnik: Stannered / Public domain

Pred reševanjem razpoložljive podprobleme bo dinamični algoritem poskusil preučiti rezultate prej rešenih podproblemov. Rešitve podproblemov so združene, da se doseže najboljša rešitev.

Namesto da bi isti podproblem vedno znova izračunavali, lahko svojo rešitev shranite v nekaj pomnilnika, ko prvič naletite na ta podproblem. Ko se med rešitvijo drugega podproblema ponovno pojavi, bo vzeta rešitev, že shranjena v pomnilniku.

To je čudovita ideja za določitev pomnilniškega časa, kjer lahko z uporabo dodatnega prostora izboljšate čas, potreben za iskanje rešitve.

Značilnosti dinamičnega programiranja

Naslednje bistvene značilnosti so, s katerimi morate imeti težave, preden lahko začnete uporabljati dinamično programiranje:

Optimalna podstruktura

Ta značilnost izraža, da je problem optimizacije mogoče rešiti s kombiniranjem optimalnih rešitev sekundarnih problemov, ki ga sestavljajo. Te optimalne podstrukture opisujejo rekurzija.

Na primer, v grafu bo predstavljena optimalna podstruktura v najkrajši poti r, ki sega od vrha s do vrha t:

To pomeni, da je na tej najkrajši poti r mogoče vzeti katero koli vmesno točko i. Če je r res najkrajša pot, jo lahko razdelimo na podvrsti r1 (od s do i) in r2 (od i do t) tako, da so to najkrajše poti med ustreznimi točki.

Zato je za iskanje najkrajših poti rešitev enostavno oblikovati rekurzivno, kar počne algoritem Floyd-Warshall.

Prekrivajoči se podproblemi

Prostor podprobleme mora biti majhen. To pomeni, da bo vsak rekurzivni algoritem, ki rešuje problem, moral reševati iste podprobleme znova in znova, namesto da ustvarja nove podprobleme.

Na primer, za ustvarjanje Fibonaccijevega niza lahko to rekurzivno formulacijo štejemo: Fn = F (n - 1) + F (n - 2), pri čemer vzamemo, da je osnovni primer F1 = F2 = 1. Potem bomo imeli: F33 = F32 + F31 in F32 = F31 + F30.

Kot vidite, je F31 razrešen v rekurzivna podvrsta F33 in F32. Čeprav je skupno število podproblemov res majhno, če sprejmete takšno rekurzivno rešitev, boste iste težave reševali znova in znova.

To upošteva dinamično programiranje, zato vsako podproblemo reši samo enkrat. To je mogoče doseči na dva načina:

Pristop od zgoraj navzdol

Če je rešitev katerega koli problema mogoče rekurzivno oblikovati z uporabo rešitve njegovih podproblemov, in če se ti podproblemi prekrivajo, potem lahko rešitve podproblemov zlahka zapomnite ali shranite v tabelo.

Vsakič, ko se išče nova rešitev podproblema, se tabela preveri, ali je bila predhodno rešena. V primeru, da je rešitev shranjena, bo uporabljena, ne da bi jo ponovno izračunali. V nasprotnem primeru bo podproblema rešena in shrani rešitev v tabelo.

Pristop od spodaj navzgor

Ko je rešitev problema formulirana rekurzivno glede na njene podprobleme, je mogoče poskusiti težavo preoblikovati navzgor: najprej bomo poskušali rešiti podprobleme in uporabiti njihove rešitve, da bomo prišli do rešitev za večje podprobleme.

To se običajno naredi tudi v obliki tabel, pri čemer se z uporabo rešitev za manjše podprobleme iterativno ustvarjajo rešitve za večje in večje podprobleme. Na primer, če sta vrednosti F31 in F30 že znani, lahko vrednost F32 izračunamo neposredno.

Primerjava z drugimi tehnikami

Pomembna značilnost problema, ki ga je mogoče rešiti z dinamičnim programiranjem, je ta, da bi se morale podprobleme prekrivati. To razlikuje dinamično programiranje od tehnike delitve in osvajanja, kjer ni treba shraniti najpreprostejših vrednosti.

Podobno je z rekurzijo, saj lahko pri izračunu osnovnih primerov končno vrednost določimo induktivno. Ta pristop od spodaj navzgor deluje dobro, če je nova vrednost odvisna samo od predhodno izračunanih vrednosti.

Primer

Najmanjši koraki do 1

Za vsako pozitivno celo število "e" lahko izvedemo katerega koli od naslednjih treh korakov.

- Od števila odštejte 1. (e = e-1).

- Če je deljiv z 2, ga delimo z 2 (če je e% 2 == 0, potem je e = e / 2).

- Če je deljiv s 3, ga delimo s 3 (če je e% 3 == 0, potem je e = e / 3).

Glede na zgornje korake je treba najti najmanjše število teh korakov, da je e enak 1. Na primer:

- Če je e = 1, rezultat: 0.

- Če je e = 4, rezultat: 2 (4/2 = 2/2 = 1).

- Ko je e = 7, rezultat: 3 (7-1 = 6/3 = 2/2 = 1).

Fokus

Mogoče bi si lahko zamislili, da bi vedno izbirali korak, ki naredi n čim nižji in tako nadaljevali, dokler ne doseže 1. Vendar je mogoče videti, da tu strategija ne deluje.

Na primer, če je e = 10, bi bili koraki: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 koraki). Vendar pa je optimalna oblika: 10-1 = 9/3 = 3/3 = 1 (3 koraki). Zato je treba preizkusiti vse možne korake, ki jih lahko naredimo za vsako vrednost n najdenih vrednosti, pri čemer izberemo najmanjše število teh možnosti.

Vse se začne s rekurzijo: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)}, če je e> 1, pri čemer vzamemo za osnovo: F (1) = 0. Z enačbo ponovitve lahko začnete kodirati rekurzijo.

Vendar je razvidno, da ima podprobleme, ki se prekrivajo. Poleg tega je optimalna rešitev za določen vhod odvisna od optimalne rešitve njegovih podproblemov.

Kot pri memorizaciji, kjer so rešitve podproblemov, ki jih rešujemo, shranjene za kasnejšo uporabo. Tako kot pri dinamičnem programiranju začnete na dnu in se lotite poti do danega e. Nato obe kodi:

Spominjanje

Dinamično programiranje od spodaj navzgor

Prednost

Ena glavnih prednosti uporabe dinamičnega programiranja je, da pospeši obdelavo, saj se uporabljajo že prej izračunane reference. Ker gre za rekurzivno tehniko programiranja, zmanjšuje vrstice kode v programu.

Hudobni algoritmi in dinamično programiranje

Pohlepni algoritmi so podobni dinamičnemu programiranju, saj sta oba orodja za optimizacijo. Vendar pohlepni algoritem išče optimalno rešitev na vsakem lokalnem koraku. Se pravi, da išče požrešno izbiro v upanju, da bo našel globalni optimum.

Zato lahko pohlepni algoritmi predpostavljajo, da je takrat videti optimalno, v prihodnosti pa postane drago in ne zagotavlja globalnega optimalnega.

Po drugi strani pa dinamično programiranje najde optimalno rešitev za podprobleme in se nato informirano odloči tako, da združi rezultate teh podproblemov, da dejansko najde najbolj optimalno rešitev.

Slabosti

- Za shranjevanje izračunanega rezultata vsakega podproblema je potrebno veliko pomnilnika, ne da bi zagotovili, da bo shranjena vrednost uporabljena ali ne.

- Velikokrat se izhodna vrednost shrani, ne da bi se med izvajanjem kdaj uporabila v naslednjih podproblemah. To vodi do nepotrebne porabe pomnilnika.

- Pri dinamičnem programiranju se funkcije imenujejo rekurzivno. S tem se spomin v nalogi stalno povečuje.

Rekurzija vs dinamično programiranje

Če imate omejen pomnilnik za zagon kode in hitrost obdelave ni zaskrbljujoča, lahko uporabite rekurzijo. Na primer, če razvijate mobilno aplikacijo, je pomnilnik zelo omejen za zagon aplikacije.

Če želite, da se program zažene hitreje in nima omejitev pomnilnika, je bolje uporabiti dinamično programiranje.

Prijave

Dinamično programiranje je učinkovita metoda reševanja problemov, ki se sicer zdi težko težko rešiti v razumnem času.

Algoritmi, ki temeljijo na paradigmi dinamičnega programiranja, se uporabljajo na številnih znanstvenih področjih, vključno s številnimi primeri umetne inteligence, od načrtovanja reševanja problemov do prepoznavanja govora.

Algoritmi, ki temeljijo na dinamičnem programiranju

Dinamično programiranje je dokaj učinkovito in deluje zelo dobro pri številnih težavah. Številne algoritme lahko vidimo kot požrešne aplikacije algoritmov, kot so:

- Fibonaccijeva številčna serija.

- stolpi v Hanoju

- Vsi pari krajših poti skozi Floyd-Warshall.

- Težava z nahrbtnikom.

- Načrtovanje projektov.

- Najkrajša pot skozi Dijkstra.

- Nadzor letenja in robotika.

- Problemi matematične optimizacije.

- Časovna zaloga: načrtujte opravilo, da povečate porabo CPE-ja.

Fibonaccijeva številčna vrsta

Fibonaccijeva števila so številke, ki jih najdemo v naslednjem zaporedju: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 itd.

V matematični terminologiji je zaporedje Fn Fibonaccijevih števil definirano s formulo ponovitve: F (n) = F (n -1) + F (n -2), kjer je F (0) = 0 in F ( 1) = 1.

Pristop od zgoraj navzdol

V tem primeru se iskalna matrika z vsemi začetnimi vrednostmi inicializira z -1. Kadar koli je potrebna podproblema, se najprej poišče ta iskalna matrika.

Če je izračunana vrednost tam, se ta vrednost vrne. V nasprotnem primeru se izračuna, da bo rezultat shranjen v iskalnem nizu, da ga bomo pozneje lahko ponovno uporabili.

Pristop od spodaj navzgor

V tem primeru za isti Fibonaccijev niz najprej izračunamo f (0), nato f (1), f (2), f (3) in tako naprej. Tako se rešitve podproblem gradijo od spodaj navzgor.

Reference

1. Vineet Choudhary (2020). Uvod v dinamično programiranje. Insider za razvijalce Izvedeno iz: developerinsider.co.
2. Alex Allain (2020). Dinamično programiranje v C ++. C Programiranje Izvedeno iz: cprogramming.com.
3. Po akademiji (2020). Ideja dinamičnega programiranja. Izvedeno iz: afteracademy.com.
4. Anirudha Chaudhari (2019). Dinamično programiranje in rekurzija - razlika, prednosti s primerom. CSE stack. Izvedeno iz: csestack.org.
5. Šifra kuharja (2020). Vadnica za dinamično programiranje. Vzeto iz: codechef.com.
6. Programiz (2020). Dinamično programiranje. Vzeto iz: programiz.com.