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.

Dělíme je na: * diskrétní vs. spojité * deterministické vs. nedeterministické (stochastické) * jednoparametrické vs. víceparametrické

Formální popis

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. +more 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 [url=https://web.archive.org/web/20110429062451/http://kam.mff.cuni.cz/~kuba/vyuka/textiky/matrix_mul.ps]příkladu násobení matic[/url].

Metody řešení

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

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í. +more 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. +more 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. +more Č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í

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

Reference

Literatura

František Nožička: Dynamické programování I, Diskrétní dynamické programování, Státní pedagogické nakladatelství, Praha 1977, 1. vydání. +more * 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

https://web. archive. +moreorg/web/20110429062451/http://kam. mff. cuni. cz/~kuba/vyuka/textiky/matrix_mul. ps (násobení matic) * https://web. archive. org/web/20051230031416/http://home. eunet. cz/berka/o/matempro. htm - neplatný odkaz .

Kategorie:Optimalizace (matematika) Kategorie:Operační výzkum