Optimální podstruktura

Obr. 1. Hledání nejkratší cesty s využitím optimální podstruktury. Čísla reprezentují délky cest; úsečky znázorňují jednotlivé hrany, vlnovky nejkratší 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.^[1]

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.^[1] Pokud tomu tak není, ale problém má vlastnost překrývajících se podproblémů, používá se dynamické programování. 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 t_s až t_e je třeba vyřešit podproblémy začínající v časech t_m, kde t_s<t_m<t_e, 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 t_s závisí na hodnotě problému začínajícího v čase t_m.

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. 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. 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. 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. Viz Bellman-Hart-Karp algorimus, až bude (zatím Enwiki).
• Problém nejlevnější letenky

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Optimal substructure na anglické Wikipedii.

Související články

• Dynamické programování
• Bellmanova rovnice