Optimální podstruktura

cesty; to znamená, že mohou existovat jiné hrany, které nejsou na tomto zjednodušeném obrázku zakresleny. Problém v matematické informatice má optimální podstrukturu, pokud lze jeho optimální řešení zkonstruovat z optimálních řešení jeho podproblémů. Pro řešení problémů s optimální podstrukturou lze s výhodou používat metody dynamického programování nebo hladové algoritmy.

Hladové algoritmy se pro řešení problémů s optimální podstrukturou používají obvykle tehdy, když lze dokázat, že jsou optimální v každém kroku. Pokud tomu tak není, ale problém má vlastnost překrývajících se podproblémů, používá se dynamické programování. +more Pokud problém nevykazuje žádnou z uvedených vlastností, bývá nejlepším způsobem řešení prosté prohledávání stavového prostoru, které může být časově náročné.

Při aplikaci dynamického programování na matematickou optimalizaci je Bellmanův princip optimality založen na myšlence, že pro vyřešení dynamického optimalizačního problému pro interval ts až te je třeba vyřešit podproblémy začínající v časech tm, kde tsme, což je případ optimální podstruktury. Princip optimality se používá pro odvození Bellmanovy rovnice, která popisuje, jak hodnota problému začínajícího v čase ts závisí na hodnotě problému začínajícího v čase tm.

Příklad

Příkladem problému s optimální podstrukturou je hledání nejkratší cesty z města A do města B. Je zřejmé, že pokud nejkratší cesta z Plzně do Hodonína bude přes Prahu a Brno, pak nejkratší cesta z Prahy do Hodonína bude také přes Brno. +more To znamená, že problém, jak se dostat z Prahy do Hodonína je podproblémem problému jak se dostat z Plzně do Hodonína.

Příkladem problému, který s velkou pravděpodobností nemá optimální podstrukturu je hledání nejlevnější letenky mezi určitými dvěma městy, např. z Buenos Aires do Kyjeva. +more I kdyby nejlevnější let by měl zastávky v Miami a v Londýně, nelze z toho vyvodit, že nejlevnější letecké spojení z Miami do Kyjeva bude přes Londýn, protože cena, za kterou letecké společnosti prodávají letenky na trasy zahrnující více letů, obvykle není součtem cen za jednotlivé lety.

Definice

Formálnější definice optimální podstruktury je následující:

Problém je kolekce alternativ. Každá alternativa a má přiřazenou cenu c(a) Předpokládejme, že množinu alternativ lze rozložit na vzájemně disjunktní třídy, tedy že každá alternativa patří do právě jedné třídy. +more Dále předpokládejme, že každá třída má svoji nákladovou funkci. Lze nalézt minimum těchto nákladových funkcí a také lze nalézt minimum globální nákladové funkce omezené na stejné podtřídy. Pokud si tato minima odpovídají pro každou třídu, pak lze zřejmě globální minimum vybírat ze třídy, která má nejmenší hodnotu nákladové funkce. Pokud minimalizace lokálních funkcí je jednodušší problém a pokud po konečném počtu lokálních redukcí se problém stane triviálním, pak problém má optimální podstrukturu.

Problémy s optimální podstrukturou

Hledání nejdelší společné podposloupnosti * Hledání rostoucí podposloupnosti * Hledání nejdelšího palindromu v řetězci * Hledání nejkratších cest mezi všemi uzly grafu * Libovolný problém, který je řešitelný metodami dynamického programování

Problémy bez optimální podstruktury

Problém nejdelší cesty, nemá polynomiální optimální podstrukturu. Má nepolynomiální optimální podstrukturu, když si pamatujeme mezilehlé vrcholy. +more Viz Bellman-Hart-Karp algorimus, až bude (zatím Enwiki). * Problém nejlevnější letenky.

Odkazy

Reference

Související články

Dynamické programování * Bellmanova rovnice

Kategorie:Dynamické programování