DYNAMICKÉ PROGRAMOVANIE: VLASTNOSTI, PRÍKLAD, VÝHODY, NEVÝHODY - TECHNOLÓGIE - 2026

Dynamické programovanie je model algoritmus, ktorý rieši komplexný problém tým, rozdelením ju do podproblémy, ukladanie jeho výsledky, aby sa zabránilo nutnosti prepočítať výsledky.

Tento rozvrh sa používa, keď máte problémy, ktoré je možné rozdeliť na podobné subproblémy, aby sa ich výsledky mohli znovu použiť. Tento plán sa väčšinou používa na optimalizáciu.

Dynamické programovanie. Subproblems superponované v Fibonacciho sekvencii. Zdroj: Wikimedia commons, en: Používateľ: Dcoatzee, sledovaný používateľom: Stannered / Public domain

Pred vyriešením dostupného subproblému sa dynamický algoritmus pokúsi preveriť výsledky predtým vyriešených subproblémov. Riešenia problémov sú kombinované tak, aby sa dosiahlo najlepšie riešenie.

Namiesto toho, aby ste ten istý subproblem vypočítali znova a znova, môžete svoje riešenie uložiť do pamäte, keď sa s týmto subproblemom stretnete prvýkrát. Ak sa znova objaví počas riešenia iného subproblému, vykoná sa riešenie už uložené v pamäti.

Je to skvelý nápad na stanovenie času v pamäti, kde využitie ďalšieho priestoru môže zlepšiť čas potrebný na nájdenie riešenia.

Funkcie dynamického programovania

Pred použitím dynamického programovania musíte mať problém s nasledujúcimi základnými charakteristikami:

Optimálna spodná konštrukcia

Táto charakteristika vyjadruje, že optimalizačný problém možno vyriešiť kombináciou optimálnych riešení sekundárnych problémov, ktoré ho tvoria. Tieto optimálne subštruktúry sú opísané rekurziou.

Napríklad v grafe bude prezentovaná optimálna podštruktúra v najkratšej ceste r, ktorá prechádza z vrcholu s do vrcholu t:

To znamená, že touto najkratšou cestou môže byť prijatý akýkoľvek stredný vrchol. Ak je r skutočne najkratšia trasa, potom ju možno rozdeliť na podriadené trasy r1 (od s do i) a r2 (od i do t) takým spôsobom, že sa jedná o najkratšiu trasu medzi príslušnými vrcholmi.

Preto, aby sa našli najkratšie cesty, riešenie môže byť ľahko formulované rekurzívne, čo robí algoritmus Floyd-Warshall.

Prekrývajúce sa problémy

Priestor pomocného priestoru musí byť malý. To znamená, že akýkoľvek rekurzívny algoritmus, ktorý rieši problém, bude musieť namiesto toho, aby generoval nové, riešiť rovnaké sub-problémy znova a znova.

Napríklad na generovanie série Fibonacci možno túto rekurzívnu formuláciu zvážiť: Fn = F (n - 1) + F (n - 2), pričom ako základný prípad vezmeme F1 = F2 = 1. Potom budeme mať: F33 = F32 + F31 a F32 = F31 + F30.

Ako vidíte, F31 sa rozdeľuje na rekurzívne podstromy F33 aj F32. Aj keď celkový počet problémov je skutočne malý, ak prijmete rekurzívne riešenie, ako je toto, nakoniec budete znova a znova riešiť rovnaké problémy.

Toto sa berie do úvahy dynamickým programovaním, takže rieši každý subproblem iba raz. To možno dosiahnuť dvoma spôsobmi:

Prístup zhora nadol

Ak je možné riešenie akéhokoľvek problému rekurzívne formulovať pomocou riešenia jeho sub-problémov, a ak sa tieto sub-problémy prekrývajú, potom je možné tieto sub-problémy ľahko zapamätať alebo uložiť do tabuľky.

Zakaždým, keď sa vyhľadáva nové riešenie problému, tabuľka sa skontroluje, aby sa zistilo, či bolo predtým vyriešené. Ak je riešenie uložené, použije sa namiesto jeho opätovného výpočtu. V opačnom prípade bude tento problém vyriešený a riešenie sa uloží do tabuľky.

Prístup zdola nahor

Po rekurzívnom formulovaní riešenia problému z hľadiska jeho problémov je možné sa pokúsiť problém preformulovať vzostupne: najprv sa pokúsime vyriešiť tieto problémy a pomocou ich riešení dospieť k riešeniu väčších problémov.

To sa tiež spravidla robí vo forme tabuľky, pričom sa iteratívne generujú riešenia väčších a väčších čiastkových problémov pomocou riešení menších čiastkových problémov. Napríklad, ak hodnoty F31 a F30 sú už známe, hodnota F32 sa môže vypočítať priamo.

Porovnanie s inými technikami

Jednou významnou črtou problému, ktorý je možné vyriešiť dynamickým programovaním, je to, že by sa malo prekrývať problém. To odlišuje dynamické programovanie od techniky rozdelenia a dobývania, kde nie je potrebné ukladať najjednoduchšie hodnoty.

Je to podobné ako rekurzia, pretože pri výpočte základných prípadov je možné konečnú hodnotu určiť induktívne. Tento prístup zdola nahor funguje dobre, keď nová hodnota závisí iba od predtým vypočítaných hodnôt.

príklad

Minimálne kroky na dosiahnutie 1

Pre každé kladné celé číslo „e“ sa môže vykonať ktorýkoľvek z nasledujúcich troch krokov.

- Odčítajte číslo 1. (e = e-l).

- Ak je deliteľné 2, delí sa 2 (ak e% 2 == 0, potom e = e / 2).

- Ak je deliteľné 3, delí sa 3 (ak e% 3 == 0, potom e = e / 3).

Na základe vyššie uvedených krokov by sa mal zistiť minimálny počet týchto krokov na 1. Napríklad:

- Ak e = 1, výsledok: 0.

- Ak e = 4, výsledok: 2 (4/2 = 2/2 = 1).

- Keď e = 7, výsledok: 3 (7-1 = 6/3 = 2/2 = 1).

ohnisko

Dalo by sa uvažovať o tom, že vždy vyberieme taký krok, ktorý zníži n na minimum a bude pokračovať takhle, až kým nedosiahne 1. Je však možné vidieť, že táto stratégia tu nefunguje.

Napríklad, ak e = 10, kroky by boli: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 kroky). Optimálna forma je však: 10-1 = 9/3 = 3/3 = 1 (3 kroky). Preto sa musia vyskúšať všetky možné kroky, ktoré možno urobiť pre každú nájdenú hodnotu n, pričom sa vyberie minimálny počet týchto možností.

Všetko to začína rekurziou: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} ak e> 1, berúc ako základný prípad: F (1) = 0. Po opakovacej rovnici môžete začať kódovať rekurziu.

Je však zrejmé, že má prekrývajúce sa problémy. Ďalej optimálne riešenie pre daný vstup závisí od optimálneho riešenia jeho problémov.

Rovnako ako v pamäti, kde sú riešenia problémov, ktoré sú vyriešené, uložené na neskoršie použitie. Alebo ako v dynamickom programovaní začnete odspodu a prepracúvate sa k danému e. Potom oba kódy:

zapamätanie

Dynamické programovanie zdola nahor

výhoda

Jednou z hlavných výhod používania dynamického programovania je to, že urýchľuje spracovanie, pretože sa používajú referencie, ktoré boli predtým vypočítané. Keďže ide o rekurzívnu programovaciu techniku, znižuje riadky kódu v programe.

Výrazné algoritmy vs dynamické programovanie

Greedy algoritmy sú podobné dynamickému programovaniu v tom, že sú nástrojmi optimalizácie. Chamtivý algoritmus však hľadá optimálne riešenie v každom miestnom kroku. To znamená, že hľadá chamtivú voľbu v nádeji, že nájde globálne optimum.

Preto chamtivé algoritmy môžu urobiť predpoklad, ktorý v tom čase vyzerá optimálne, ale v budúcnosti sa stáva drahým a nezaručuje globálny optimál.

Na druhej strane, dynamické programovanie nájde optimálne riešenie pre subproblémy a potom urobí informovanú voľbu kombinovaním výsledkov týchto subproblémov, aby skutočne našli najoptimálnejšie riešenie.

nevýhody

- Na uloženie vypočítaného výsledku každého subproblemu je potrebné veľa pamäte bez toho, aby bolo možné zaručiť, že uložená hodnota bude použitá alebo nie.

- Výstupná hodnota sa mnohokrát počas vykonávania ukladá bez toho, aby sa v nasledujúcich problémoch použila. To vedie k zbytočnému využívaniu pamäte.

- V dynamickom programovaní sa funkcie nazývajú rekurzívne. Tým sa neustále zvyšuje pamäť zásobníka.

Rekurzia verzus dynamické programovanie

Ak máte na spustenie kódu obmedzenú pamäť a rýchlosť spracovania nie je problémom, môžete použiť rekurziu. Napríklad, ak vyvíjate mobilnú aplikáciu, na spustenie aplikácie je pamäť veľmi obmedzená.

Ak chcete, aby program bežal rýchlejšie a nemáte žiadne obmedzenia pamäte, je lepšie použiť dynamické programovanie.

aplikácia

Dynamické programovanie je efektívny spôsob riešenia problémov, ktoré by sa inak mohli javiť ako mimoriadne ťažké vyriešiť v primeranom čase.

Algoritmy založené na paradigme dynamického programovania sa používajú v mnohých oblastiach vedy, vrátane mnohých príkladov umelej inteligencie, od plánovania riešenia problémov po rozpoznávanie reči.

Algoritmy založené na dynamickom programovaní

Dynamické programovanie je pomerne efektívne a funguje veľmi dobre pre celý rad problémov. Mnoho algoritmov možno považovať za chamtivé aplikácie algoritmov, ako napríklad:

- Fibonacciho čísla.

- Veže v Hanoji.

- Všetky páry kratších trás cez Floyd-Warshall.

- Problém s batohom.

- Plánovanie projektu.

- Najkratšia cesta cez Dijkstra.

- Riadenie letu a riadenie robotiky.

- Problémy s matematickou optimalizáciou.

- Časovo vymedzené užívanie nehnuteľností: naplánujte úlohu tak, aby sa maximalizovalo využitie procesora.

Fibonacciho číselné rady

Fibonacciho čísla sú čísla nájdené v nasledujúcej sekvencii: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 atď.

V matematickej terminológii je sekvencia Fn Fibonacciho čísel definovaná podľa vzorca pre opakovanie: F (n) = F (n -1) + F (n -2), kde F (0) = 0 a F ( 1) = 1.

Prístup zhora nadol

V tomto príklade sa vyhľadávacie pole so všetkými počiatočnými hodnotami inicializuje s -1. Vždy, keď je potrebné riešenie čiastkového problému, najprv sa prehľadá táto matica vyhľadávania.

Ak je tam vypočítaná hodnota, bude táto hodnota vrátená. V opačnom prípade sa výsledok vypočíta tak, že sa uloží do vyhľadávacieho poľa, aby sa dal neskôr znova použiť.

Prístup zdola nahor

V tomto prípade sa pre rovnaké série Fibonacci najskôr vypočíta f (0), potom f (1), f (2), f (3) atď. Preto sa riešenia problémov riešia zdola nahor.

Referencie

1. Vineet Choudhary (2020). Úvod do dynamického programovania. Prevzaté z: developerinsider.co.
2. Alex Allain (2020). Dynamické programovanie v C ++. Programovanie v C. Prevzaté z: cprogramming.com.
3. Po akadémii (2020). Idea dynamického programovania. Prevzaté z: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamické programovanie a rekurzia - rozdiel, výhody s príkladom. Zásobník VVN. Prevzaté z: csestack.org.
5. Kód šéfkuchár (2020). Výukový program pre dynamické programovanie. Prevzaté z: codechef.com.
6. Programiz (2020). Dynamické programovanie. Prevzaté z: programiz.com.