Informácie o dynamickom programovaní nájdete v stovkách rôznych učebníc, článkov, videí, kurzoch... Doporučujem používať nižšie uvedené učebnice, ktoré vysvetľujú techniku krok po kroku (a máte ich k dispozícii elektronicky). 

 

Video lectures 19, 20, 21

Záznamy z prednášky z roku 2018 časť I a časť II

 

Prvý príklad, ktorý dáva odpovede na naše otázky, je výpočet Fibonacciho čísla, učebnica JE kapitola 3.1. s. 97 - 103.  Rekurzívny algoritmus má exponenciálnu zložitosť, pretože v priebehu výpočtu sa opakovane riešia tie isté podproblémy.

Ak rozumieme zdroju neefektívnosti algoritmu RecFibo, môžeme ho optimalizovať tak, že si ukladáme výsledky riešení jednotlivých podproblémov - algoritmus MemFibo. Táto technika sa zvykne označovať názvom memoizácia. Časová zložitosť algoritmu je úmerná počtu rôznych podproblémov. Algoritmus má ale netriviálnu priestorovú zložitosť. Posledný krok, ktorý nás privedie k najefektívnejšiemu riešeniu spočíva v tom, že si uvedomíme, aký je vzťah (závislosť) medzi jednotlivými podproblémami. 

Algoritmus IterFibo využíva túto závislosť a podproblémy rieši v poradí F_2, F_3, F_4, ... , F_n.

Zhrnutie: techniku dynamického programovania musíme použiť vtedy, keď použitie rekurzie vedie k opakovanému riešeniu tých istých podproblémov. Opakovanému riešeniu sa môžeme vyhnúť 

-- ukladaním medzivýsledkov (memoizácia)

-- zvolením vhodného poradia, v ktorom riešime podproblémy (dynamické programovanie). Ako postupovať pri návrhu algoritmu pri použití techniky dynamického programovania? Schému návrhu nájdete 

v  JE kap 3.4 , s. 105 - 107 a v CLRS kap. 15.3.

Problém ako   čo najefektívnejšie vynásobiť postupnoť matíc. Popis nájdete v CLRS, kap. 15.2. a na slajdoch k prednáške. Všimnite si, že problém ozátvorkovania je optimalizačný problém - spomedzi všetkých spôsobov ako vypočítať súčin matíc hľadáme ten, ktorý je najlacnejší (=optimálny). Riešenie problému "hrubou silou" by znamenalo zistiť, aká je cena všetkých možných postupov násobenia.

DIY Koľko existuje rôznych spôsobov ako vypočítať súčin postupnosti n matíc?

Problém môžeme riešiť prístupom rozdeľ a panuj. Potrebujeme si uvedomiť, že ak máme vynásobiť matice A_1, ..., A_n, tak najprv musíme poznať súčin matíc A_1 až A_i a súčin matíc A_(i+1) až A_n. Akú hodnotu má i? Nevieme, preto vyskúšame všetky hodnoty i --- a máme dekompozíciu. Dôležitá vec, ktorú si musíme uvedomiť je, že nepotrebujeme poznať všetky možné spôsoby, ako vypočítať súčin matíc  A_1 až A_i, ale stačí nám poznať jeden spôsob, a to ten optimálny

DIY Vysvetlite, prečo je zložitosť rekurzívneho algoritmu exponenciálna.

V momente, keď máme dekompozíciu problému na jednotlivé podproblémy, môžeme skúmať vzťah medzi nimi.

DIY Čo potrebujeme vedieť k tomu, aby sme optimálne vynásobili matice A_9 až A_15?

Všimnite si, že pri konštrukcii dynamického algoritmu sa využíva cena riešení jednotlivých podproblémov, vyjadrená rekurzívnou funkciou OPT. Závislosť medzi podproblémami je v tomto príklade daná počtom matíc (ak potrebujeme vedieť, ako optimálne vynásobiť postupnosť 8 matíc, stačí nám k tomu vedieť ako optimálne vynásobiť všetky jej podpostupnosti, a tie majú dĺžku max 7).

DIY Znovu si pozrite schému nárvhu algoritmov dynamického programovanie a každý bod schémy si namapujte na zodpovedajúce kroky pri návrhu algoritmu pre násobenie matíc.

DIY Všimnite si, aký je rozdiel medzi výpočtom ceny optimálneho riešenia a výpočtom optimálneho riešenia. Čo je jednoduchšie?

Dynamické programovanie je vhodnou technikou pre skúmanie rôznych vlastností reťazcov. Dva takéto algoritmy, ktoré majú veľmi podobnú štruktúru, nájdete v CLRS kap. 15.4 a v JE kap. 3.7, s. 111 - 116. Najkomplikovanejším bodom návrhu algoritmu je u oboch problémov dekompozícia. Zamerajte sa pri štúdiu algoritmov práve na tento bod. Riešenie problému Edit distance nájdete aj na slajdoch k prednáške.

DIY Algoritmus pre najdlhšiu spoločnú podpostunosť v CLRS postupuje pri dekompozícii odzadu (viz Theorem 15.1). Skúste navrhnúť algoritmus, ktorý postupuje od začiatku reťazcov.

Všimnite si, že optimalizačná funkcia je v oboch algoritmoch funkciou dvoch argumentov (c[i,j] resp Edit(i,j)). Z toho vyplýva, že musíme byť veľmi pozorní pri určovaní závislostí medzi podproblémami resp. pri určovaní, v akom poradí budeme podproblémy riešiť.

DIY V algoritme Edit distance v   JE  je poradie, v akom sa riešia jednotlivé podproblémy, zachytené obrázkom na strane 114. Je použité poradie jediné možné? Navrhnite iné poradie.

Algoritmus v JE kap. 3.8., s 116 -117. Problém pracuje s množinou čísel. Prirozdenou dekompozíciou je rozklad množiny na dve množiny (jednoprvkovú a "zbytok"). Zamyslite sa nad tým, prečo takáto dekompozícia nefunguje. Algoritmus v JE definuje podproblém ako dvojicu (množina čísel, suma ktorú chceme vytvoriť).

DIY Problém batohu je zovšeobecnením problému sumy. Modifikujte algoritmus pre problém sumy tak, aby riešil problém batohu. Hint: slajdy k prednáške.

JE kap. 3.9., s. 117 - 120, CLRS kap. 15.5.

Cvičenie

Otázky k zamysleniu a konkrétne príklady sú v komentároch k prednáške. Riešené príklady nájdete v učebnici Algorithm Design Vyriešte príklady. 

Ďalšie príklady k  nájdete vo všetkých troch učebných textoch, ktoré máte k dispozícii. Riešenia príkladov z CLR  sú dostupné.