Dynamické programování

Dynamické programování (DP; angl. dynamic programming, DP) — je metoda řešení složitých optimalizačních úloh, založená na rozkladě původní úlohy na posloupnost jednodušších podúloh. Metoda se používá pro vícekorové procesy rozhodování, kde optimální řešení celé úlohy lze sestavit z optimálních řešení jejích podúloh.

Termín zavedl americký matematik Richard Bellman v 50. letech 20. století. V tomto kontextu slovo „programování" označuje „plánování" nebo „sestavení optimálního plánu činnosti", nikoli psaní počítačového kódu.

Klíčové vlastnosti a věty

Použitelnost dynamického programování pro danou úlohu je určena přítomností dvou základních vlastností.

Bellmanův princip optimality

Ústředním konceptem metody je Bellmanův princip optimality (angl. Bellman's principle of optimality). Říká: bez ohledu na to, jaký je počáteční stav a počáteční rozhodnutí, musí následující rozhodnutí tvořit optimální strategii vzhledem ke stavu vzniklému v důsledku prvního rozhodnutí.

Jinými slovy, každá část optimální trajektorie je sama o sobě optimální. Tato vlastnost umožňuje rozložit celkovou úlohu na posloupnost jednodušších podúloh a řešit je rekurzivně.

Překrývající se podúlohy

Úloha má vlastnost překrývajících se podúloh (angl. overlapping subproblems), pokud se při jejím rekurzivním řešení tytéž podúlohy opakovaně vyskytují. DP umožňuje vyhnout se opakovaným výpočtům tím, že ukládá řešení již vyřešených podúloh (tato technika se nazývá memoizace nebo tabelace), což výrazně zvyšuje efektivitu oproti naivnímu rekurzivnímu prohledávání.

Bellmanova rovnice

Z principu optimality vyplývá základní rekurentní vztah metody — Bellmanova rovnice. Spojuje „hodnotu" (optimální zisk nebo cenu) aktuálního stavu s hodnotami následujících stavů. V obecné podobě pro deterministický vícekorový proces s aditivní účelovou funkcí má tvar:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

kde:

• $k$ — číslo kroku (od $m$ do 1);
• $x$ — stav systému v kroku $k-1$;
• $y$ — řídící rozhodnutí přijímané v kroku $k$;
• ${\phi }_k(x,y)$ — zisk (nebo cena) v k-tém kroku;
• $f_k(x,y)$ — funkce určující nový stav systému;
• $V_k(s)$ — optimální hodnota účelové funkce pro podúlohu začínající v kroku $k$ ve stavu $s$.

Rovnice se řeší postupně, zpravidla „od konce", přičemž se postupuje od posledního kroku k prvnímu.

Příklady použití

• Úloha o nejkratší cestě v grafu: Tato úloha má vlastnost optimální podstruktury, protože každý úsek nejkratší cesty je sám nejkratší. Bellmanův-Fordův algoritmus a Floydův-Warshallův algoritmus jsou klasickými příklady použití DP pro řešení této úlohy.
• Úloha o batohu: Úloha o optimálním naplnění batohu s omezenou kapacitou předměty s různou hodnotou a hmotností. DP umožňuje řešit tuto úlohu postupným procházením předmětů a výpočtem maximální hodnoty pro všechny možné hodnoty zbývající kapacity v každém kroku.
• Úloha o rozdělení zdrojů: Rozdělení omezeného zdroje (například investic) mezi několik projektů za účelem maximalizace celkového efektu.

Omezení

Hlavním omezením metody je prokletí dimenzionality (angl. curse of dimensionality) — termín zavedený Bellmanem pro označení exponenciálního růstu počtu stavů a v důsledku toho i výpočetní složitosti při zvyšování počtu proměnných popisujících stav systému. Toto omezení zužuje praktické použití přesného DP pro úlohy velmi velké dimenze.

Související pojmy

• Operační výzkum
• Teorie optimálního řízení
• Markovský rozhodovací proces (stochastické zobecnění)
• Hamiltonova–Jacobiho–Bellmanova rovnice (analogie pro spojitý čas)