Dynamické programování

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Dynamické programování je odvětví optimalizace. Stěžejní myšlenkou je rozklad problému na podproblémy, které jsou řešeny a jejich řešení je ukládáno pro další potenciálně možné použití. Metoda je obzvláště vhodná na úlohy, které se dají dělit na podúlohy, které jsou si podobné a mohou se opakovat. V mnoha úlohách jde volit způsob rozkladu na podproblémy. Tato volba může mít vliv na efektivitu celého výpočtu.

Dělíme je na:

  • diskrétní vs. spojité
  • deterministické vs. stochastické
  • jednoparametrické vs. víceparametrické

Formální popis[editovat | editovat zdroj]

Máme dán systém s množinou přípustných stavů a možných rozhodnutí. V určitých okamžicích máme učinit rozhodnutí, která mění stav systému na nějaký jiný stav. Celá posloupnost stavů systému a rozhodnutí (tzv. strategie) je nějak oceněna a úkolem je nalézt co nejcennější posloupnost rozhodnutí.

Tento popis si jde dobře představit na příkladu násobení matic.

Metody řešení[editovat | editovat zdroj]

Algoritmus řešení je založen na Bellmanově principu optimality: "Podstrategie optimální strategie je opět optimální." Tento princip platí pouze pro některé úlohy a na ty lze použít dynamické programování.

Příklad – Fibonacciho posloupnost[editovat | editovat zdroj]

Jako příklad použití dynamického programování uvedeme algoritmus pro výpočet n-tého Fibonacciho čísla. Podle matematické definice Fibonacciho posloupnosti bychom mohli počítat následujícím způsobem:

function fib(n)
    if n == 0 return 0
    if n == 1 return 1
    return fib(n − 1) + fib(n − 2)

Tento algoritmus zbytečně počítá většinu členů posloupnosti vícekrát. Algoritmus tedy můžeme zrychlit tím, že si budeme všechny již spočítané výsledky ukládat pro další použití. Lepší algoritmus lze tedy navrhnout následovně:

var m := map(0 → 0, 1 → 1)
function fib(n)
    if map m ještě neobsahuje klíč n
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

V tomto algoritmu začneme od výsledného členu posloupnosti a podle potřeby dopočítáváme předchozí členy. Tento přístup k řešení se nazývá shora dolu. Nevýhodou tohoto přístupu je, že si musíme pamatovat předchozí prvky posloupnosti v poli m a navíc musíme v každém kroku testovat zdali m obsahuje n. Výhodnější většinou bývá přístup zvaný zdola nahoru. V tomto přístupu se nejdříve počítají mezivýsledky a poté konečný výsledek. Algoritmus pro výpočet n-tého Fibonacciho čísla navržený podle přístupu zdola nahoru bude vypadat následovně:

function fib(n)
       var previousFib := 0, currentFib := 1
       if n = 0
           return 0
       else if n = 1
           return 1
       repeat n − 1 times
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
       return currentFib

Tento algoritmus postupně počítá Fibonacciho čísla od 0 do n. Vždy si pamatuje pouze dva předchozí členy posloupnosti. Časová složitost tohoto algoritmu je O(n). Paměťová složitost je O(1). Je třeba dodat, že tento algoritmus není nejrychlejší známý algoritmus pro výpočet n-tého Fibonacciho čísla. Rychlejší algoritmus je uveden zde.

Některé algoritmy založené na myšlence dynamického programování[editovat | editovat zdroj]

Algoritmus Needleman-Wunsch - algoritmus pro optimální přiřazení dvou sekvencí DNA.

Reference[editovat | editovat zdroj]

  • František Nožička: Dynamické programování I, Diskrétní dynamické programování, Státní pedagogické nakladatelství, Praha 1977, 1. vydání.
  • Jaroslav Samek, Zdeňka Nečasová, Jan Kodera: Dynamické programování v ekonomických procesech, Státní pedagogické nakladatelství, Praha 1983, 1. vydání

Externí odkazy[editovat | editovat zdroj]