Optimální spodní konstrukce - Optimal substructure

Obrázek 1 . Hledání nejkratší cesty pomocí optimální spodní konstrukce. Čísla představují délku cesty; přímé čáry označují jednotlivé hrany , vlnovky označují nejkratší cesty , tj. mohou zde být další vrcholy, které zde nejsou zobrazeny.

V informatice se říká, že problém má optimální podstrukturu, pokud lze optimální řešení sestrojit z optimálního řešení jejích dílčích problémů. Tato vlastnost se používá k určení užitečnosti dynamického programování a chamtivých algoritmů pro problém.

Obvykle se chamtivý algoritmus používá k řešení problému s optimální podstrukturou, pokud lze indukcí dokázat, že je to optimální v každém kroku. Jinak se za předpokladu, že problém vykazuje překrývající se dílčí problémy , použije dynamické programování . Pokud neexistují žádné vhodné chamtivé algoritmy a problém nevykazuje překrývající se dílčí problémy, je často nejlepší alternativou zdlouhavé, ale přímé hledání prostoru řešení.

Při použití dynamického programování do matematické optimalizace , Richarda Bellmanův ‚s princip optimality je založen na myšlence, že v zájmu vyřešení problému dynamické optimalizace z nějaké počáteční období t k nějakému končícím období T , jeden má implicitně řešit podproblémy počínaje pozdější data s , kde t <s <T . Toto je příklad optimální spodní konstrukce. Princip odvození se používá k odvození Bellmanovy rovnice , která ukazuje, jak hodnota problému počínaje od t souvisí s hodnotou problému počínaje s .

Příklad

Zvažte nalezení nejkratší cesty pro cestování mezi dvěma městy autem, jak je znázorněno na obrázku 1. Je pravděpodobné, že takový příklad bude vykazovat optimální spodní konstrukci. To znamená, že pokud nejkratší trasa ze Seattlu do Los Angeles prochází Portlandem a poté Sacramentem, pak musí nejkratší cesta z Portlandu do Los Angeles projít také Sacramentem. To znamená, že problém, jak se dostat z Portlandu do Los Angeles, je vnořen do problému, jak se dostat ze Seattlu do Los Angeles. (Vlnovky v grafu představují řešení dílčích problémů.)

Jako příklad problému, u kterého je nepravděpodobné, že by vykazoval optimální spodní konstrukci, zvažte problém nalezení nejlevnější letenky z Buenos Aires do Moskvy. I když tato letenka zahrnuje zastávky v Miami a poté v Londýně, nemůžeme usoudit, že nejlevnější letenka z Miami do Moskvy zastavuje v Londýně, protože cena, za kterou letecká společnost prodává víceletou cestu, obvykle není součtem cen za které by prodávala jednotlivé lety v rámci cesty.

Definice

Lze uvést trochu formálnější definici optimální spodní konstrukce. Nechť je „problém“ souborem „alternativ“ a každá alternativa má související náklady, c (a) . Úkolem je najít sadu alternativ, která minimalizuje c (a) . Předpokládejme, že alternativy lze rozdělit na podmnožiny, tj. Každá alternativa patří pouze do jedné podmnožiny. Předpokládejme, že každá podmnožina má svou vlastní nákladovou funkci. Lze nalézt minima každé z těchto nákladových funkcí, stejně jako minima globální nákladové funkce omezená na stejné podmnožiny . Pokud se tato minima shodují pro každou podmnožinu, pak je téměř zřejmé, že globální minimum nelze vybrat nikoli z celé sady alternativ, ale pouze ze sady, která se skládá z minim menších funkcí místních nákladů, které jsme definovali. Pokud je minimalizace místních funkcí problémem „nižšího řádu“ a (konkrétně) pokud se po konečném počtu těchto redukcí stane problém triviální, pak má problém optimální podstrukturu.

Problémy s optimální spodní konstrukcí

Problémy bez optimální spodní konstrukce

  • Problém s nejdelší cestou
  • Umocňování řetězcem sčítání
  • Nejlevnější cena letenky. (Pomocí online vyhledávání letů často zjistíme, že nejlevnější let z letiště A na letiště B zahrnuje jediné spojení přes letiště C, ale nejlevnější let z letiště A na letiště C zahrnuje spojení přes jiné letiště D.) pokud problém vezme jako parametr maximální počet mezipřistání, pak má problém optimální spodní konstrukci: nejlevnější let z A do B zahrnující jediné spojení je buď přímý let; nebo let z A do nějakého cíle C plus optimální přímý let z C do B.

Viz také

Reference

  1. ^ a b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). Úvod do algoritmů (3. vyd.). MIT Stiskněte . ISBN   978-0-262-03384-8 .