Dynamické programování
Dynamické programování v teorii řízení a teorii počítačových systémů je způsob řešení složitých problémů jejich rozdělením na jednodušší dílčí úkoly. Je použitelný pro problémy s optimální podstrukturou, které vypadají jako soubor překrývajících se dílčích problémů, jejichž složitost je o něco menší než u původního. V tomto případě může být doba výpočtu ve srovnání s "naivními" metodami výrazně zkrácena.
Klíčová myšlenka dynamického programování je poměrně jednoduchá. K vyřešení problému je zpravidla nutné vyřešit jednotlivé části problému (podproblém) a následně sloučit řešení dílčích úkolů do jednoho společného řešení. Mnoho z těchto dílčích úkolů je často stejných. Přístup dynamického programování spočívá v řešení každého dílčího problému pouze jednou, čímž se sníží počet výpočtů. To je užitečné zejména v případech, kdy je počet opakujících se dílčích úkolů exponenciálně velký.
Metoda dynamického programování shora je jednoduchým zapamatováním výsledků řešení těch dílčích problémů, se kterými se může v budoucnu znovu setkat. Dynamické programování zdola zahrnuje přeformulování složitého problému jako rekurzivní sekvence jednodušších dílčích problémů.
Historie
Fráze „dynamické programování“ byla poprvé použita ve 40. letech 20. století Richardem Bellmanem k popisu procesu hledání řešení problému, kdy odpověď na jeden problém lze získat až po vyřešení problému, který mu „předcházel“. V roce 1953 tuto definici zdokonalil na moderní. Obor byl původně založen jako systémová analýza a inženýrství, což bylo uznáno IEEE . Bellmanův příspěvek k dynamickému programování byl zvěčněn ve jménu Bellmanovy rovnice , ústředního výsledku teorie dynamického programování, která přeformuluje optimalizační problém v rekurzivní formě.
Slovo „programování“ ve spojení „dynamické programování“ ve skutečnosti nemá téměř nic společného s „tradičním“ programováním (psáním kódu) a dává smysl jako ve spojení „ matematické programování “, které je synonymem slova „optimalizace“. Proto slovo „program“ v tomto kontextu spíše znamená optimální sled akcí k získání řešení problému. Například konkrétní plán akcí na výstavě je někdy označován jako program. Program je v tomto případě chápán jako platný sled událostí.
Myšlenka dynamického programování
Optimální podstruktura v dynamickém programování znamená, že k vyřešení původního problému lze použít optimální řešení menších dílčích problémů. Například nejkratší cestu v grafu z jednoho vrcholu (označeného s) do druhého (označeného t) lze nalézt následovně: nejprve vezmeme v úvahu nejkratší cestu ze všech vrcholů sousedících s s do t a poté vezmeme s ohledem na váhy hran, které spojují s se sousedními vrcholy, zvolíme nejlepší cestu k t (kterým vrcholem je nejlepší projít). V obecném případě můžeme problém, který má optimální podstrukturu, vyřešit provedením následujících tří kroků.
- Rozdělení úkolu na menší dílčí úkoly.
- Nalezení optimálního řešení dílčích problémů rekurzivně pomocí stejného tříkrokového algoritmu .
- Využití získaného řešení dílčích úloh ke konstrukci řešení původního problému.
Podproblémy se řeší tak, že se rozdělují na ještě menší podproblémy a tak dále, dokud nedojdou k triviálnímu případu problému, který lze vyřešit v konstantním čase (odpověď lze říci okamžitě). Pokud například potřebujeme najít n!, pak 1! = 1 (nebo 0! = 1).
Překrývající se podproblémy v dynamickém programování znamenají podproblémy, které se používají k řešení řady problémů (nejen jednoho) větší velikosti (to znamená, že totéž děláme několikrát). Pozoruhodným příkladem je výpočet Fibonacciho posloupnosti a - i v takovém triviálním případě jsme již dvakrát počítali výpočty pouze dvou Fibonacciho čísel. Pokud budete pokračovat dále a počítat , pak se to započítá ještě dvakrát, protože znovu a bude potřeba pro výpočet . Ukazuje se následující: jednoduchý rekurzivní přístup stráví čas výpočtem řešení problémů, které již vyřešil.
Abychom se takovému průběhu událostí vyhnuli, uložíme si řešení podproblémů, které jsme již vyřešili, a až budeme znovu potřebovat řešení podproblému, místo přepočítávání jej jednoduše získáme z paměti. Tento přístup se nazývá memoizace . Můžete také provádět další optimalizace - například pokud jsme si jisti, že již nepotřebujeme řešit dílčí úlohu, můžeme ji vyhodit z paměti a uvolnit ji pro jiné potřeby, nebo pokud je procesor nečinný a víme, že řešení některých dílčích úkolů, které ještě nebyly spočítány, potřebujeme v budoucnu, můžeme je vyřešit předem.
Shrneme-li výše uvedené, můžeme říci, že dynamické programování využívá následující vlastnosti problému:
- překrývající se dílčí úkoly;
- optimální spodní stavba;
- schopnost zapamatovat si řešení často se vyskytujících dílčích úkolů.
Dynamické programování obecně sleduje dva přístupy k řešení problémů:
- dynamické programování shora dolů: problém se rozdělí na menší podproblémy, ty se vyřeší a následně zkombinují k vyřešení původního problému. Memorování slouží k řešení již vyřešených dílčích úkolů.
- dynamické programování zdola nahoru: všechny dílčí úkoly, které jsou následně potřebné k vyřešení původního problému, jsou předem spočítány a následně použity k sestavení řešení původního problému. Tento způsob je z hlediska velikosti potřebného zásobníku a počtu volání funkcí lepší než programování shora dolů, ale někdy není snadné předem zjistit, které dílčí problémy musíme v budoucnu vyřešit.
Programovací jazyky si mohou zapamatovat výsledek volání funkce s určitou sadou argumentů ( memoization ), aby se urychlil „výpočet podle jména“. Některé jazyky mají tuto schopnost zabudovanou (např . Scheme , Common Lisp , Clojure , Perl , D ), zatímco jiné vyžadují další rozšíření ( C++ ).
Známé jsou sériové dynamické programování, které je obsaženo ve všech učebnicích operačního výzkumu , a nesériové dynamické programování (NSDP), které je v současnosti málo známé, ačkoli bylo objeveno v 60. letech 20. století.
Konvenční dynamické programování je speciálním případem nesériového dynamického programování, kde je graf vztahu proměnných pouze cestou. NSDP, která je přirozenou a obecnou metodou pro zohlednění struktury optimalizačního problému, považuje množinu omezení a/nebo účelovou funkci za rekurzivně vypočítatelnou funkci. To umožňuje najít řešení krok za krokem, v každé fázi pomocí informací získaných v předchozích fázích, a účinnost tohoto algoritmu přímo závisí na struktuře grafu proměnných vztahů. Pokud je tento graf dostatečně řídký, pak lze množství výpočtů v každé fázi udržet v rozumných mezích.
Jednou z hlavních vlastností problémů řešených pomocí dynamického programování je aditivnost . Neaditivní problémy se řeší jinými metodami. Například mnoho úkolů optimalizace investic společnosti není aditivní a řeší se porovnáním hodnoty společnosti s investicemi a bez nich.
Klasické problémy dynamického programování
- Problém nejdelší společné podsekvence : Vzhledem ke dvěma sekvencím musíte najít nejdelší společnou podsekvenci.
- Úkol najít největší rostoucí podsekvenci : je-li daná posloupnost, je třeba najít nejdelší rostoucí podsekvenci.
- Problém editační vzdálenosti (Levenshteinova vzdálenost) : vzhledem ke dvěma řetězcům je nutné najít minimální počet vymazání, nahrazení a přidání znaků, které transformují jeden řetězec na jiný.
- Problém výpočtu Fibonacciho čísel
- Problém řádu násobení matic : dané matice , …, , je potřeba minimalizovat počet skalárních operací pro jejich násobení.
- Problém volby trajektorie
- Problém sekvenčního rozhodování
- Problém využití pracovní síly
- Výzva pro řízení zásob
- Problém batohu : z neomezené množiny položek s vlastnostmi „cena“ a „hmotnost“ je nutné vybrat určitý počet položek tak, aby bylo dosaženo maximálních celkových nákladů s omezenou celkovou hmotností.
- Floyd-Warshallův algoritmus : Najděte nejkratší vzdálenosti mezi všemi vrcholy váženého orientovaného grafu.
- Algoritmus Bellman-Ford : Najděte nejkratší cestu ve váženém grafu mezi dvěma danými vrcholy.
- Maximální nezávislá množina vrcholů ve stromu : daný strom najděte maximální množinu vrcholů, z nichž žádné dva nejsou spojeny hranou.
- Úkol naplánovat dopravník : Existují dva dopravníky, každý s úlohami. Jsou uvedeny doby práce na každém dopravníku, usazení na něj a jeho vyjmutí, stejně jako doba přesunu na sousední místo. Chcete určit nejrychlejší způsob sestavení součásti pomocí obou dopravníků.
Literatura
- Bellman R. Dynamické programování. - M .: Nakladatelství zahraniční literatury , 1960.
- Kormen, T. , Leizerson, C. , Rivest, R. , Stein, C. Kapitola 15. Dynamické programování // Algorithms: Construction and Analysis = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
- Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. algoritmy . - McGraw-Hill Science / Engineering / Math, 2006. - 336 s. — ISBN 0073523402 .
- Akulich I. L. Kapitola 4. Problémy dynamického programování // Matematické programování v příkladech a úlohách. - M . : Vyšší škola , 1986. - 319 s. — ISBN 5-06-002663-9 .
- Bertele U., Brioshi F. Nesériové dynamické programování. - NY: Academic Press, 1972. - 235 stran.
- Gabasov R. , Kirillova F. M. Základy dynamického programování. -Mn. : Nakladatelství BSU, 1975. - 262 s.
Odkazy
- Video přednášky o dynamickém programování
- Teorie, úlohy, testovací systém .
 Slovníky a encyklopedie | ||||
|---|---|---|---|---|
| ||||