Dynamické programování, základní principy

Chcete-li vybrat optimální řešení pro programovací úlohy, je někdy nutné projít velkým množstvím datových kombinací, které načte paměť osobního počítače. Takové metody zahrnují například programovací metodu "rozdělit a dobýt". V tomto případě algoritmus umožňuje oddělení úkolu do jednotlivých malých dílčích úkolů. Tato metoda se používá pouze v případech, kdy jsou malé podsoubory nezávislé na sobě. Aby se předešlo zbytečné práci v případě, že jsou podsoubory vzájemně závislé, použije se dynamická programovací metoda navržená americkým R. Bellmanem v padesátých letech.

Podstata metody

Dynamické programování spočívá v určení optimálního řešení n-dimenzionálního problému, který se dělí na n samostatné kroky. Každá z nich je subtask s ohledem na jednu proměnnou.

Hlavní výhodou tohoto přístupu je, že vývojáři se zabývají jednorozměrnými optimalizačními úlohami dílčích úkolů namísto n-dimenzionálního problému a řešení hlavního úkolu se shromažďuje "zdola nahoru".

Je vhodné použít dynamické programování v těch případech, kde jsou podsoubory vzájemně propojeny, tj. mají společné moduly. Algoritmus poskytuje řešení každému podsouboru jednou a odpovědi jsou uloženy ve zvláštní tabulce. To umožňuje znovu vypočítat odpověď, když se setkáte s podobnou podsoubor.

Úloha dynamického programování řeší problém optimalizace. Autor této metody R. Bellman formuloval princip optimality: ať už je počáteční stav v každém kroku a řešení určené v tomto kroku, všechny následující jsou zvoleny tak, aby byly optimální vzhledem ke stavu, který systém počítá na konci kroku.

Metoda zlepšuje výkon úkolů, které jsou řešeny vyhledáním variant nebo rekurzí.

Konstrukce algoritmu problému

Dynamické programování předpokládá konstrukci takového algoritmu problémů, v němž je úloha rozdělena na dvě nebo více podsouborů, takže její řešení je tvořeno optimálním řešením všech dílčích dílčích úkolů, které jsou v něm zahrnuty. Dále je zapotřebí napsat relaci opakování a vypočítat optimální hodnotu parametru pro problém jako celek.

Někdy ve třetím kroku je třeba dále pamatovat některé pomocné informace o průběhu každé dílčí zálohy. Toto se nazývá opačně.

Použití metody

Dynamické programování se používá, pokud existují dvě charakteristické rysy:

• optimalita pro dílčí úkoly;
• přítomnost překrývajících se dílčích úloh v problému.

Řešení optimalizačního problému metodou dynamického programování je nejprve nutné popsat strukturu řešení. Problém je optimální, pokud řešení problému spočívá v optimálních řešeních jeho dílčích úkolů. V tomto případě je vhodné používat dynamické programování.

Druhou vlastností problému, která je pro tuto metodu nezbytná, je malý počet dílčích úkolů. Rekurzivní řešení problému používá stejné překrývající se dílčí úkoly, jejichž počet závisí na velikosti původní informace. Odpověď je uložena ve zvláštní tabulce, program šetří čas pomocí těchto dat.

Je obzvláště efektivní používat dynamické programování, když je třeba v podstatě provádět úkoly v jednotlivých etapách. Zvažte například jednoduchý příklad úkolu výměny a opravy zařízení. Předpokládejme, že na slévárně výrobny pneumatik jsou pneumatiky vyráběny současně ve dvou různých formách. V případě, že některý z formulářů selže, musíte zařízení rozmontovat. Je zřejmé, že někdy je výhodnější nahradit druhou formu, aby nedošlo k rozebrání stroje v případě, a tato forma bude v příští fázi neúčinná. Kromě toho je snadnější nahradit oba pracovní formy dříve, než začnou selhat. Metoda dynamického programování určuje nejlepší strategii v otázce nahrazení těchto forem, přičemž se berou v úvahu všechny faktory: výhoda pokračování provozu formulářů, ztráta z nečinných strojů, náklady na odmítnuté pneumatiky a další.