Dynamické programovaní
Postup návrhu algoritmu dynamickým programováním:
1. Rozmyslet rozdělení na (překrývající se) podproblémy.
2. Sestavit rekurzivní algoritmus.
► Typicky hledáme optimální hodnotu, pro niž sestavíme rekurzivní vztah.
► V tomto kroku se nestaráme o složitost!
3. Určit správné pořadí počítání podproblémů, které zajistí, že se každý spočítá právě jednou, (bottom-up přístup)
► Alternativou je top-down with memoization, ale většinou preferujeme bottom-up. Proč?
4. Chceme-li kromě optimální hodnoty znát i její realizaci: Navrhnout způsob, jak řešení sestavit.
► Použijeme napočítané hodnoty podproblémů, někdy je třeba mírná modifikace.
Dynamické programovaní
Nejmenší počet kroků k jedničce
Máme dáno kladné celé číslo n. V každé iteraci můžeme provést jednu z následujících operací:
1. odečíst od r? jedničku;
2. pokud je n sudé, vydělit n dvěma;
3. pokud je n dělitelné třemi, vydělit n třemi.
Jaký je nejmenší počet iterací takový, že se z n stane číslo 1?
► Použijeme přístup: „V každé iteraci použijeme tu operaci, která hodnotu čísla n nejvíc sníží." Je toto korektní přístup?
Dynamické programovaní
Nejmenší počet kroků k jedničce
Máme dáno kladné celé číslo n. V každé iteraci můžeme provést jednu z následujících operací:
1. odečíst od r? jedničku;
2. pokud je n sudé, vydělit n dvěma;
3. pokud je n dělitelné třemi, vydělit n třemi.
Jaký je nejmenší počet iterací takový, že se z n stane číslo 1?
► Použijeme přístup: „V každé iteraci použijeme tu operaci, která hodnotu čísla n nejvíc sníží." Je toto korektní přístup?
► Chceme použít dynamické programování:
1. podproblémy
2. rekurzivní vztah pro optimální hodnotu
3. pořadí počítání podproblémů
4. sestavení řešení
Dynamické programovaní
Zalamování řádků v odstavci
Mějme text skládající se z r? slov, šírka /tého slova je w; pixelů. Chceme text vypsat do odstavce tak, aby byl zarovnán do bloku a na každém řádku byly co nejmenší mezery (mezery musí být minimálně 1 pixel). Maximální délka řádkuje m pixelů. Každému řádku kromě posledního je určena penalizace
kde / a j jsou indexy prvního a posledního slova na řádku. Cílem je minimalizovat součet penalizací všech řádků (kromě posledního).
► Chceme použít dynamické programování:
1. podproblémy
2. rekurzivní vztah pro optimální hodnotu
3. pořadí počítání podproblémů
4. sestavení řešení
J
k=i
Dynamické programovaní
Zalamování řádků v odstavci
Mějme text skládající se z r? slov, šírka /tého slova je w; pixelů. Chceme text vypsat do odstavce tak, aby byl zarovnán do bloku a na každém řádku byly co nejmenší mezery (mezery musí být minimálně 1 pixel). Maximální délka řádkuje m pixelů. Každému řádku kromě posledního je určena penalizace
kde / a j jsou indexy prvního a posledního slova na řádku. Cílem je minimalizovat součet penalizací všech řádků (kromě posledního).
► Chceme použít dynamické programování:
1. podproblémy
2. rekurzivní vztah pro optimální hodnotu
3. pořadí počítání podproblémů
4. sestavení řešení
K zamyšlení: Co kdyby penalizace byla lineární místo kubické?
j
k=i
Dynamické programovaní
Firemní večírek
Firma ZretezenySeznam.cz porada firemní večírek k příležitosti 42. narozenin jejího zakladatele a CEO. Zaměstnanci firmy jsou uspořádáni do stromové hierarchie. Specialisté z HR oddělení znají pro každého zaměstnance z jeho míru zábavnosti fz. Dále pak zjistili, že není vhodné, aby se večírku účastnil libovolný zaměstnanec zároveň se svým přímým nadřízeným. Samozřejmě je ovšem nutné, aby se večírku účastnil sám CEO (kořen stromu). Sestavte seznam hostů, který bude respektovat tato omezení a zároveň maximalizovat součet jejich zábavnosti.
► Jak zformulujeme zadání formálně?
Dynamické programovaní
Firemní večírek
Firma ZretezenySeznam.cz porada firemní večírek k příležitosti 42. narozenin jejího zakladatele a CEO. Zaměstnanci firmy jsou uspořádáni do stromové hierarchie. Specialisté z HR oddělení znají pro každého zaměstnance z jeho míru zábavnosti fz. Dále pak zjistili, že není vhodné, aby se večírku účastnil libovolný zaměstnanec zároveň se svým přímým nadřízeným. Samozřejmě je ovšem nutné, aby se večírku účastnil sám CEO (kořen stromu). Sestavte seznam hostů, který bude respektovat tato omezení a zároveň maximalizovat součet jejich zábavnosti.
► Jak zformulujeme zadání formálně?
► Chceme použít dynamické programování:
1. podproblémy
2. rekurzivní vztah pro optimální hodnotu
3. pořadí počítání podproblémů
4. sestavení řešení
Dynamické programovaní
Obarvení stromu
Mějme kořenový binární strom s n vrcholy a přirozené číslo k < n. Chceme obarvit k vrcholů stromu tak, aby každý vrchol měl obarveného co nejbližšího předchůdce. Obarvení chápeme jako podmnožinu vrcholů stromu K. Pro každý vrchol definujeme cenu obarvení jako:
Celková cena obarvení pak je cena(K) = maxu cena{v, K). Chceme najít obarvení s minimální cenou.
Poznámka: Bude nám stačit řešení se složitostí 0(n2k2).
pokud v G K
pokud v je kořen a v 0 K
jinak
k 1 + cena(parent(v), K)
Dynamické programovaní
Rekonstrukce textu bez mezer
Máme text, ze kterého zmizely všechny mezery a interpunkce. Chceme zrekonstruovat jeho (alespoň jednu možnou) původní podobu. K dispozici máme slovník, kterého se pomocí funkce isWord(w) můžeme dotazovat, zda je daný řetězec platné slovo.
Dynamické programovaní
Hra o nej větší součet
Dva hráči hrají následující hru: Na stole je řada n karet s čísly. V každém kole hráč vezme jednu kartu buď z levého nebo z pravého konce řady. Hráči se střídají. Na konci vyhrává ten hráč, jehož součet čísel na kartách je větší.
Chceme určit, který z hráčů vyhraje, za předpokladu, že oba hrají co nejlépe.
► Uvažujme strategii: „Vždy vezmu větší ze dvou krajních karet." Je tato strategie optimální?