The dynamické programování je algoritmický model, který řeší složitý problém tak, že jej rozdělí na dílčí problémy a ukládá jejich výsledky, aby nemusel tyto výsledky přepočítávat.
Tento plán se používá, pokud máte problémy, které lze rozdělit na podobné dílčí problémy, aby bylo možné jejich výsledky znovu použít. Toto programování se z velké části používá k optimalizaci.
Před řešením dostupného dílčího problému se dynamický algoritmus pokusí prozkoumat výsledky dříve vyřešených dílčích problémů. Řešení dílčích problémů jsou kombinována, aby bylo dosaženo nejlepšího řešení.
Místo opakovaného výpočtu stejného dílčího problému můžete své řešení uložit do nějaké paměti, když se s tímto dílčím problémem poprvé setkáte. Když se znovu objeví během řešení jiného dílčího problému, bude přijato řešení již uložené v paměti.
Je to skvělý nápad opravit čas v paměti, kde pomocí dalšího prostoru můžete zlepšit čas potřebný k nalezení řešení..
Rejstřík článků
Před použitím dynamického programování musíte mít problém s následujícími základními charakteristikami:
Tato charakteristika vyjadřuje, že optimalizační problém lze vyřešit kombinací optimálních řešení sekundárních problémů, které jej tvoří. Tyto optimální substruktury jsou popsány rekurzí.
Například v grafu bude představena optimální podstruktura na nejkratší cestě r, která vede od vrcholu s k vrcholu t:
To znamená, že v této nejkratší cestě r lze vzít jakýkoli mezilehlý vrchol i. Pokud je r skutečně nejkratší trasa, lze ji rozdělit na dílčí trasy r1 (od s do i) a r2 (od i do t) takovým způsobem, že jsou to zase nejkratší trasy mezi odpovídajícími vrcholy.
Proto, aby bylo možné najít nejkratší trasy, lze řešení snadno formulovat rekurzivně, což dělá algoritmus Floyd-Warshall..
Prostor pro dílčí problém musí být malý. To znamená, že jakýkoli rekurzivní algoritmus, který vyřeší problém, bude muset řešit stejné dílčí problémy znovu a znovu, místo generování nových dílčích problémů..
Například pro generování Fibonacciho řady lze uvažovat o této rekurzivní formulaci: Fn = F (n-1) + F (n-2), přičemž jako základní případ vezmeme F1 = F2 = 1. Pak budeme mít: F33 = F32 + F31 a F32 = F31 + F30.
Jak vidíte, F31 se řeší do rekurzivních podstromů F33 i F32. Přestože je celkový počet dílčích problémů opravdu malý, pokud přijmete takové rekurzivní řešení, nakonec vyřešíte stejné problémy znovu a znovu..
Toto je zohledněno dynamickým programováním, takže každý dílčí problém řeší pouze jednou. Toho lze dosáhnout dvěma způsoby:
Pokud lze řešení kteréhokoli problému rekurzivně formulovat pomocí řešení jeho dílčích problémů a pokud se tyto dílčí problémy překrývají, lze řešení dílčích problémů snadno zapamatovat nebo uložit do tabulky.
Pokaždé, když bude hledáno nové řešení podproblémů, bude tabulka zkontrolována, zda byla dříve vyřešena. Pokud je řešení uloženo, bude použito místo jeho opětovného výpočtu. V opačném případě bude dílčí problém vyřešen uložením řešení do tabulky.
Poté, co bude řešení problému rekurzivně formulováno z hlediska jeho dílčích problémů, bude možné pokusit se problém přeformulovat vzestupně: nejdříve se pokusíme dílčí problémy vyřešit a pomocí jejich řešení dospět k řešení větších dílčích problémů.
To se také obecně provádí ve formě tabulky, která iterativně generuje řešení pro větší a větší dílčí problémy pomocí řešení menších dílčích problémů. Například pokud jsou již známy hodnoty F31 a F30, lze hodnotu F32 vypočítat přímo.
Jedním z významných rysů problému, který lze vyřešit dynamicky, je to, že by měl mít překrývající se dílčí problémy. To odlišuje dynamické programování od techniky rozděl a panuj, kde není nutné ukládat nejjednodušší hodnoty.
Je to podobné jako s rekurzí, protože při výpočtu základních případů lze konečnou hodnotu určit indukčně. Tento přístup zdola nahoru funguje dobře, když nová hodnota závisí pouze na dříve vypočítaných hodnotách.
U libovolného kladného celého čísla „e“ lze provést kterýkoli z následujících tří kroků.
- Odečtěte 1 od čísla. (e = e-1).
- Pokud je dělitelné 2, vydělte 2 (pokud e% 2 == 0, pak e = e / 2).
- Pokud je dělitelné 3, vydělte 3 (pokud e% 3 == 0, pak e = e / 3).
Na základě výše uvedených kroků je třeba zjistit minimální počet těchto kroků, aby se hodnota e dostala na 1. Například:
- Pokud e = 1, výsledek: 0.
- Pokud e = 4, výsledek: 2 (4/2 = 2/2 = 1).
- Když e = 7, výsledek: 3 (7-1 = 6/3 = 2/2 = 1).
Dalo by se uvažovat o tom, že si vždy zvolíme krok, díky kterému je n co nejnižší, a takto pokračujeme, dokud nedosáhne 1. Je však vidět, že zde tato strategie nefunguje..
Například pokud e = 10, kroky by byly: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 kroky). Optimální forma je však: 10-1 = 9/3 = 3/3 = 1 (3 kroky). Měly by proto být vyzkoušeny všechny možné kroky, které lze provést pro každou nalezenou hodnotu n, a zvolit minimální počet těchto možností.
Vše začíná rekurzí: F (e) = 1 + min F (e-1), F (e / 2), F (e / 3) pokud e> 1, přičemž jako základní případ se vezme: F (1) = 0. Když máme rovnici rekurence, můžeme začít kódovat rekurzi.
Je však vidět, že má překrývající se dílčí problémy. Optimální řešení pro daný vstup dále závisí na optimálním řešení jeho dílčích problémů.
Stejně jako v zapamatování, kde jsou řešení dílčích problémů, které jsou vyřešeny, uložena pro pozdější použití. Nebo stejně jako v dynamickém programování začínáte od spodní části a postupujete až k danému e. Pak oba kódy:
Jednou z hlavních výhod používání dynamického programování je, že zrychluje zpracování, protože se používají reference, které byly dříve vypočítány. Jelikož se jedná o techniku rekurzivního programování, snižuje řádky kódu programu.
Chamtivé algoritmy jsou podobné dynamickému programování v tom, že jsou oba nástroji pro optimalizaci. Chamtivý algoritmus však hledá optimální řešení v každém místním kroku. To znamená, že hledá chamtivou volbu v naději, že najde globální optimum..
Chamtivé algoritmy proto mohou vytvořit předpoklad, který v danou chvíli vypadá optimálně, ale v budoucnu se stane nákladným a nezaručuje globální optimum..
Na druhou stranu dynamické programování najde optimální řešení pro dílčí problémy a poté provede informovanou volbu kombinací výsledků těchto dílčích problémů, aby skutečně našlo nejoptimálnější řešení..
- K uložení vypočítaného výsledku každého dílčího problému je zapotřebí hodně paměti, přičemž nelze zaručit, že uložená hodnota bude použita nebo ne.
- Mnohokrát je výstupní hodnota uložena, aniž by byla během provádění použita v následujících dílčích problémech. To vede k zbytečnému využití paměti.
- V dynamickém programování se funkce nazývají rekurzivně. Tím se paměť zásobníku neustále zvyšuje.
Pokud máte ke spuštění kódu omezenou paměť a rychlost zpracování není problém, můžete použít rekurzi. Například pokud vyvíjíte mobilní aplikaci, je paměť pro její spuštění velmi omezená.
Pokud chcete, aby program běžel rychleji a nemáte paměťová omezení, je lepší použít dynamické programování.
Dynamické programování je efektivní metoda řešení problémů, které by se jinak mohly zdát extrémně obtížné v rozumném čase vyřešit..
Algoritmy založené na paradigmatu dynamického programování se používají v mnoha oblastech vědy, včetně mnoha příkladů umělé inteligence, od plánování řešení problémů až po rozpoznávání řeči..
Dynamické programování je docela efektivní a funguje velmi dobře pro širokou škálu problémů. Mnoho algoritmů lze považovat za chamtivé aplikace algoritmů, například:
- Fibonacciho číselná řada.
- Hanojské věže.
- Všechny nejkratší páry tras od Floyd-Warshall.
- Problém s batohem.
- Plánování projektu.
- Nejkratší cesta přes Dijkstra.
- Řízení letu a řízení robotiky.
- Problémy s matematickou optimalizací.
- Timesharing - naplánujte úlohu, abyste maximalizovali využití procesoru.
Fibonacciho čísla jsou čísla nalezená v následující sekvenci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 atd..
V matematické terminologii je posloupnost Fn Fibonacciho čísel definována vzorcem opakování: F (n) = F (n -1) + F (n -2), kde F (0) = 0 a F (1) = 1.
V tomto příkladu je vyhledávací pole se všemi počátečními hodnotami inicializováno s -1. Kdykoli je potřeba řešení dílčího problému, nejprve se prohledá tato vyhledávací matice.
Pokud je tam vypočítaná hodnota, bude tato hodnota vrácena. V opačném případě bude výsledek vypočítán tak, aby byl uložen do vyhledávacího pole, aby jej bylo možné později znovu použít.
V tomto případě se pro stejnou Fibonacciho řadu nejprve vypočítá f (0), poté f (1), f (2), f (3) atd. Řešení dílčích problémů tak budou konstruována zdola nahoru.
Zatím žádné komentáře