Co je to 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 rozdělením problému 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ů.

Překrývající se subproblémy popisují komplikované rovnice, které, když jsou rozděleny na menší sady rovnic, znovu použijí části menších rovnic více než jednou, aby dosáhly odpovědi.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 tento problém řekl, že po výpočtu výsledku by měl tento výsledek uložit a připojit odpověď do rovnice později namísto toho, aby ji znovu vypočítal.Při jednání s dlouhými složitými procesy a rovnicemi to šetří čas a vytvoří rychlejší řešení pomocí mnohem méně kroků.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ž to 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 to souvisí se skutečným světem.

Během kterékoli z těchto operací, dynamického programováníAlgoritmus se snaží najít nejkratší cestu k řešení.K tomu může trvat jeden ze dvou přístupů.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.