10.1 Dynamické programování
- DP je další technika návrhu algoritmů, která je založená na rekurzivním rozkladu problému na podproblémy.
- Na rozdíl od klasické metody Rozděl a panuj, metoda DP využívá toho, že se podproblémy během rekurzivního rozkladu opakují.
- Podmínkou použití DP je tedy opakovaný výskyt stejných podproblémů při rekurzivním rozkladu.
- DP pak vede na mnohem rychlejší algoritmy než přímočarý rekurzivní rozklad.
Princip Dynamického programování (memoizace)
- Formulujeme řešení daného problému rekurzivně rozkladem na řešení podproblémů.
- Popíšeme řešení pomocí rekurzivního algoritmu, který má exponenciální složitost.
- Identifikujeme opakované výpočty stejných podproblémů.
- Vytvoříme prázdnou tabulku hodnot řešení podproblémů.
- Vložíme do ní hodnoty řešení triviálních instancí.
- Před výpočtem řešení podproblému se podíváme do tabulky.
- Pokud je políčko tohoto podproblému již vypočtené, vezmeme jeho hodnotu.
- Jinak tento podproblém vyřešíme pomocí volání rekurze.
- Po návratu z rekurze zapíšeme výsledek do příslušného políčka tabulky.
Princip Dynamického programování (iterace - bottom-up)
- Předchozí obecný postup vede na výpočet řízený shora dolů: řešení problému vyvolává řešení podproblémů a vyplňování jejich políček v tabulce.
- Jakmile ale dokážeme zkonstruovat tabulku hodnot řešení podproblémů, uvědomíme si, že ji lze vyplňovat bez rekurze, čili iteračně, zvolíme-li vhodné pořadí (topologické uspořádání) od triviálních koncových řešení směrem k řešení celého problému.
- Tím získáme řádově stejně rychlý, ale obvykle ještě jednodušší algoritmus, který vyplní tabulku zdola nahoru.