DYNAMICKÉ PROGRAMOVÁNÍ: VLASTNOSTI, PŘÍKLAD, VÝHODY, NEVÝHODY - TECHNOLOGIE - 2025

Dynamické programování je model algoritmus, který řeší komplexní problém tím, rozdělením ji do podproblémy, ukládání jeho výsledky, aby se zabránilo nutnosti přepočítat výsledky.

Tento rozvrh se používá, pokud máte problémy, které lze rozdělit na podobné dílčí problémy, takže jejich výsledky lze znovu použít. Tento plán se z velké části používá pro optimalizaci.

Dynamické programování. Subproblems superponované ve Fibonacciho posloupnosti. Zdroj: Wikimedia commons, en: Uživatel: Dcoatzee, sledováno uživatelem: Stannered / Public domain

Před vyř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í těchto problémů jsou kombinována tak, aby bylo dosaženo nejlepšího řešení.

Namísto výpočtu stejného subproblému znovu a znovu můžete své řešení uložit do paměti, když se s tímto subproblemem setkáte poprvé. Když se znovu objeví během řešení jiného subproblemu, řešení již uložené v paměti bude přijato.

To je skvělý nápad pro stanovení času paměti, kde využití dalšího prostoru může zlepšit čas potřebný k nalezení řešení.

Vlastnosti dynamického programování

Před použitím dynamického programování musíte mít potíže s následujícími základními charakteristikami:

Optimální podstruktura

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 prezentována optimální substruktura v nejkratší cestě r, která přechází z vrcholu do vrcholu t:

To znamená, že v této nejkratší cestě lze vzít jakýkoli střední vrchol. Pokud je r skutečně nejkratší cestou, lze ji rozdělit na subrouty r1 (od s do i) a r2 (od i do t) takovým způsobem, že se jedná o nejkratší trasy mezi odpovídajícími vrcholy.

Proto, pro nalezení nejkratších cest, řešení lze snadno formulovat rekurzivně, což je to, co dělá algoritmus Floyd-Warshall.

Překrývající se dílčí problémy

Podřízený prostor musí být malý. To znamená, že jakýkoli rekurzivní algoritmus, který řeší problém, bude muset znovu a znovu řešit stejné subproblémy, místo aby generoval nové subproblems.

Například pro generování Fibonacciho řady můžeme 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 rozkládá na rekurzivní podstromy F33 i F32. Přestože je celkový počet dílčích problémů opravdu malý, přijmete-li rekurzivní řešení, jako je toto, nakonec budete znovu a znovu řešit stejné problémy.

Toto je zohledněno dynamickým programováním, takže řeší každý subproblem pouze jednou. Toho lze dosáhnout dvěma způsoby:

Přístup shora dolů

Pokud lze řešení jaké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í, mohou být řešení těchto problémů snadno zapamatována nebo uložena do tabulky.

Pokaždé, když se hledá nové řešení subproblem, tabulka se zkontroluje, aby se zjistilo, zda bylo dříve vyřešeno. V případě, že je řešení uloženo, bude použito místo jeho opětovného výpočtu. Jinak bude subproblem vyřešen a řešení uloží do tabulky.

Přístup zdola nahoru

Poté, co je řešení problému formulováno rekurzivně, pokud jde o jeho dílčí problémy, je možné se pokusit problém přeformulovat vzhůru: nejprve se pokusíme řešit dílčí úlohy a pomocí jejich řešení dospět k řešení větších dílčích problémů.

To se také obecně provádí v podobě tabulky, která iterativně generuje řešení větších a větších subproblémů pomocí řešení menších subproblémů. Pokud jsou například hodnoty F31 a F30 již známy, lze hodnotu F32 vypočítat přímo.

Porovnání s jinými technikami

Jedním z významných rysů problému, který může být vyřešen dynamickým programováním, je to, že by měl mít podřízené problémy překrývající se. To odlišuje dynamické programování od techniky dělení a dobývání, kde není nutné ukládat nejjednodušší hodnoty.

Je to podobné rekurzi, protože při výpočtu základních případů lze konečnou hodnotu stanovit induktivně. Tento přístup zdola nahoru funguje dobře, když nová hodnota závisí pouze na dříve vypočítaných hodnotách.

Příklad

Minimální kroky k dosažení 1

Pro každé kladné celé číslo "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, dělí se 2 (pokud e% 2 == 0, pak e = e / 2).

- Pokud je dělitelná 3, dělí se 3 (pokud e% 3 == 0, pak e = e / 3).

Na základě výše uvedených kroků by měl být nalezen minimální počet těchto kroků, který přinese e 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).

Zaměřit se

Dalo by se uvažovat o tom, že si vždy vybereme krok, který n je tak nízký, jak je to možné, a takto pokračujeme, dokud nedosáhne 1. Je však vidět, že tato strategie zde 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). Proto musí být vyzkoušeny všechny možné kroky, které mohou být provedeny pro každou nalezenou hodnotu n, výběr minimálního počtu těchto možností.

Všechno to začíná rekurzí: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)}, pokud e> 1, vezme se jako základní případ: F (1) = 0. S opakovací rovnicí můžete začít kódovat rekurzi.

Je však vidět, že má překrývající se subproblémy. Optimální řešení pro daný vstup navíc závisí na optimálním řešení jeho dílčích problémů.

Stejně jako v memorování, kde jsou řešení dílčích problémů, která jsou vyřešena, uložena pro pozdější použití. Nebo jako v dynamickém programování začnete od dna a pracujete až k danému e. Pak oba kódy:

Memorování

Dynamické programování zdola nahoru

Výhoda

Jednou z hlavních výhod použití dynamického programování je to, že zrychluje zpracování, protože se používají odkazy, které byly dříve vypočteny. Protože se jedná o rekurzivní programovací techniku, snižuje řádky kódu v programu.

Prostorné algoritmy vs. dynamické programování

Greedy algoritmy jsou podobné dynamickému programování v tom, že jsou oba nástroje 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í optima.

Proto chamtivé algoritmy mohou vytvořit předpoklad, který vypadá optimálně v té době, ale v budoucnu bude drahý a nezaručuje globální optimální.

Na druhé straně 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í.

Nevýhody

- K uložení vypočteného výsledku každého subproblemu je potřeba hodně paměti, aniž by bylo možné zaručit, že uložená hodnota bude nebo nebude použita.

- Výstupní hodnota je mnohokrát 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 neustále zvyšuje paměť zásobníku.

Rekurze vs. dynamické programování

Pokud máte omezenou paměť pro spuštění kódu a rychlost zpracování není problémem, můžete použít rekurzi. Například, pokud vyvíjíte mobilní aplikaci, je paměť pro spuštění aplikace velmi omezená.

Pokud chcete, aby program běžel rychleji a neměl žádná omezení paměti, je výhodné použít dynamické programování.

Aplikace

Dynamické programování je efektivní metoda řešení problémů, které by se jinak mohly zdát extrémně obtížné vyřešit v přiměřeném čase.

Algoritmy založené na paradigmatu dynamického programování se používají v mnoha oblastech vědy, včetně mnoha příkladů v umělé inteligenci, od plánování řešení problémů po rozpoznávání řeči.

Algoritmy založené na dynamickém programování

Dynamické programování je velmi efektivní a funguje velmi dobře pro celou řadu problémů. Mnoho algoritmů lze chápat jako chamtivé aplikace algoritmů, jako například:

- Fibonacciho číselné řady.

- Věže v Hanoji.

- Všechny páry kratších cest přes 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í.

- Timeshare: naplánujte úlohu tak, aby se maximalizovalo využití CPU.

Fibonacciho řada čísel

Fibonacciho čísla jsou čísla nalezená v následující posloupnosti: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 atd.

V matematické terminologii je sekvence Fn Fibonacciho čísel definována opakovacím vzorcem: F (n) = F (n -1) + F (n -2), kde F (0) = 0 a F (1) = 1.

Přístup shora dolů

V tomto příkladu je vyhledávací pole se všemi počátečními hodnotami inicializováno -1. Kdykoli je potřeba řešení dílčího problému, bude nejprve prohledána 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 mohl být později znovu použit.

Přístup zdola nahoru

V tomto případě se pro stejnou sérii Fibonacci nejprve vypočítá f (0), poté f (1), f (2), f (3) atd. Řešení problémů se tedy staví zdola nahoru.

Reference

1. Vineet Choudhary (2020). Úvod do dynamického programování. Developer Insider Převzato z: developerinsider.co.
2. Alex Allain (2020). Dynamické programování v C ++. Programování v C. Převzato z: cprogramming.com.
3. Po akademii (2020). Idea dynamického programování. Převzato z: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamické programování a rekurze - rozdíl, výhody s příkladem. Zásobník CSE. Převzato z: csestack.org.
5. Code Chef (2020). Výukový program pro dynamické programování. Převzato z: codechef.com.
6. Programiz (2020). Dynamické programování. Převzato z: programiz.com.