Co je dynamické programování?
Dynamické programování, když odkazuje na oblast informatiky, popisuje skupinu podobných počítačových algoritmů, které měly vyřešit složité problémy tím, že problém rozdělí na sady menších problémů. Dynamické programování, které poprvé vytvořilo Richard Bellman v 50. letech 20. století, pracuje s problémy, které jsou buď překrývajícími se subproblémy nebo optimálními substruktury. Abychom pochopili, jak funguje dynamické programování, je nejlepší pochopit koncept těchto dvou termínů. Například matematická rovnice, která byla uvedena pro výpočet všech možných výsledků pomocí sady čísel, může vypočítat stejný výsledek mnohokrát při výpočtu dalších výsledků pouze jednou. Dynamické programování by řeklo tento problém, že po výpočtu výsledku by měl tento výsledek poprvé uložit a připojit odpověď doRovnice později namísto toho, aby ji znovu vypočítala. Při jednání s dlouhými složitými procesy a rovnicemi to šetří čas a vytváří rychlejší řešení pomocí mnohem méně kroků.
Optimální substruktury vytvářejí řešení nalezením nejlepší odpovědi na všechny subproblémy a poté vytvořením nejlepší celkové odpovědi. Po rozdělení složitého problému na menší problémy pak počítač použije matematický systém k určení, 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ž dává řešení, které funguje nejlépe matematicky, může nebo nemusí být nejlepším řešením v reálném životě, v závislosti na typu problému a na tom, jak se to týká skutečného světa.
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 trvat jeden zdva přístupy k tomu. Přístup shora dolů rozbije rovnici do menších rovnic a v případě potřeby znovu použije odpovědi na tyto rovnice. Přístup zdola nahoru se snaží vyřešit nejmenší matematickou hodnotu po rozbití rovnice dolů a poté odtud prochází směrem k největšímu. Oba přístupy šetří čas, ale dynamické programování funguje pouze tehdy, když se původní problém může rozdělit na menší rovnice, které jsou v určitém okamžiku znovu použity k vyřešení rovnice.