Skip to content

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)

  1. Formulujeme řešení daného problému rekurzivně rozkladem na řešení podproblémů.
  2. Popíšeme řešení pomocí rekurzivního algoritmu, který má exponenciální složitost.
  3. Identifikujeme opakované výpočty stejných podproblémů.
  4. Vytvoříme prázdnou tabulku hodnot řešení podproblémů.
  5. Vložíme do ní hodnoty řešení triviálních instancí.
  6. Před výpočtem řešení podproblému se podíváme do tabulky.
  7. Pokud je políčko tohoto podproblému již vypočtené, vezmeme jeho hodnotu.
  8. Jinak tento podproblém vyřešíme pomocí volání rekurze.
  9. 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.