Dynamické programování
Dynamické programování je metoda pro efektivní řešení určitých optimalizačních úloh. Lze jej použít pro řešení úloh, které lze rozdělit na podúlohy, jejichž optimální řešení lze použít při řešení původní úlohy. Princip dynamického programování spočívá v rekurzivním dělení úlohy na menší části, které se řeší ve vhodném pořadí, jejich výsledky se zaznamenávají a jsou použity pro řešení složitějších podúloh včetně původní úlohy.[1]
Dělíme je na:
- diskrétní vs. spojité
- deterministické vs. nedeterministické (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]- Needlemanův–Wunschův algoritmus pro optimální přiřazení dvou sekvencí DNA
- Viterbiho algoritmus
- Algoritmus Cocke-Younger-Kasami a Earleyův analyzátor pro syntaktickou analýzu bezkontextových jazyků
- Floydův-Warshallův algoritmus pro počítání nejkratších cest v grafu
Odkazy
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]- ↑ TÖPFER, Pavel. Algoritmy a programovací techniky. 1. vyd. Praha: Prometheus, 1995. 299 s. ISBN 80-85849-83-6. S. 250–268.
Literatura
[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í
