Co je dynamické programování?
Dynamické programování, když se odkazuje na oblast informatiky, popisuje skupinu podobných počítačových algoritmů určených k řešení složitých problémů rozdělením problému na sady menších problémů. Dynamické programování, které poprvé vytvořil Richard Bellman v 50. letech 20. století, pracuje s problémy, které se překrývají s dílčími problémy nebo s optimálními strukturami. Abychom pochopili, jak dynamické programování funguje, je nejlepší porozumět koncepci těchto dvou termínů.
Překrývající se subproblémy popisují složité rovnice, které při rozdělení na menší množiny rovnic znovu používají části menších rovnic více než jednou, aby dosáhly odpovědi. Například matematická rovnice, která má vypočítat všechny možné výsledky pomocí sady čísel, může vypočítat tentýž výsledek mnohokrát, zatímco ostatní výsledky se počítají pouze jednou. Dynamické programování by tomuto problému říkalo, že po výpočtu výsledku by měl tento výsledek uložit poprvé a později zapsat odpověď do rovnice namísto jejího opětovného výpočtu. Při řešení složitých procesů a rovnic to šetří čas a vytváří rychlejší řešení pomocí mnohem méně kroků.
Optimální substruktury vytvářejí řešení tak, že najdou nejlepší odpověď na všechny subproblémy a poté vytvoří nejlepší celkovou odpověď. Po rozdělení složitého problému na menší problémy počítač poté pomocí matematického systému určí, jaká je nejlepší odpověď pro každý problém. Vypočítá odpověď na původní problém z menších odpovědí. S tímto procesem existují nedostatky. I když poskytuje řešení, které funguje matematicky nejlépe, může, ale nemusí být nejlepším řešením v reálném životě, v závislosti na typu problému a na tom, jak souvisí s reálným světem.
Během kterékoli z těchto operací se algoritmus dynamického programování snaží najít nejkratší cestu k řešení. Může to provést jedním ze dvou přístupů. Přístup shora dolů rozdělí rovnici na menší rovnice a v případě potřeby znovu použije odpovědi na tyto rovnice. Přístup zdola nahoru se pokouší vyřešit nejmenší matematickou hodnotu po rozbití rovnice dolů a poté postupuje směrem nahoru k největší odtud. Oba přístupy šetří čas, ale dynamické programování funguje pouze tehdy, když se původní problém může rozložit na menší rovnice, které se v určitém okamžiku znovu použijí k vyřešení rovnice.