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ší.
- Objektově orientované programování
- Modulární programování
- Vlastnosti a metody záznamu algoritmů
- Java programovací jazyk
- Základní programovací jazyk a jeho historie
- Seznam programovacích jazyků. Programovací jazyky nízké a vysoké úrovně
- Použití indexOf (jаvascript) při práci s maticemi a řetězci
- Procedurální programování je co?
- Jaký programovací jazyk mám zvolit pro začátečníka, který se má učit
- Řešení problémů s programováním. Cyklický algoritmus
- Nelineární programování je jednou ze součástí matematického programování
- Lineární programování
- Matematické programování je správným způsobem, jak dosáhnout nejlepšího rozhodnutí
- Metoda Homori. Řešení celočíselných programovacích problémů
- Populární metody pro seskupování prvků pole: třídění podle vložení a použití klíče
- Jak aktualizovat stránku v prohlížeči:
- Třídící algoritmy tak, jak jsou
- Dynamické pole a jeho funkce
- Nejjednodušší programovací jazyk pro začátečníky
- Co je to programovací systém
- Proč používat programovací jazyky na vysoké úrovni?