Dynamické programovanie je metóda používaná v matematike a informatike na riešenie zložitých problémov ich rozdelením na jednoduchšie podproblémy. Tým, že sa každý podproblém rieši iba raz a výsledky sa ukladajú, vyhýba sa nadbytočným výpočtom, čo vedie k efektívnejším riešeniam širokého spektra problémov. Tento článok poskytuje podrobný prieskum konceptov dynamického programovania ilustrovaný príkladmi.

Dynamické programovanie

Obsah

• Čo je dynamické programovanie?
• Ako funguje dynamické programovanie?
• Príklady dynamického programovania
• Kedy použiť dynamické programovanie?
• Prístupy dynamického programovania
• Algoritmus dynamického programovania
• Výhody dynamického programovania
• Aplikácie dynamického programovania
• Naučte sa základy dynamického programovania
• Pokročilé koncepty dynamického programovania
• Problémy dynamického programovania

Čo je dynamické programovanie (DP)?

Dynamické programovanie (DP) je metóda používaná v matematike a informatike na riešenie zložitých problémov ich rozdelením na jednoduchšie podproblémy. Tým, že sa každý podproblém rieši iba raz a výsledky sa ukladajú, vyhýba sa nadbytočným výpočtom, čo vedie k efektívnejším riešeniam širokého spektra problémov.

Ako funguje dynamické programovanie (DP)?

• Identifikujte čiastkové problémy: Rozdeľte hlavný problém na menšie, nezávislé podproblémy.
• Riešenia predajní: Vyriešte každý podproblém a uložte riešenie do tabuľky alebo poľa.
• Vybudovanie riešení: Použite uložené riešenia na vytvorenie riešenia hlavného problému.
• Vyhnite sa redundancii: Uložením riešení DP zaisťuje, že každý podproblém je vyriešený iba raz, čím sa skracuje čas výpočtu.

Príklady dynamického programovania (DP)

Príklad 1: Zvážte problém nájdenia Fibonacciho sekvencie:

Fibonacciho sekvencia: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Prístup hrubou silou:

Ak chcete nájsť n-té Fibonacciho číslo pomocou prístupu hrubej sily, jednoducho by ste pridali (n-1). a (n-2). Fibonacciho čísla. To by fungovalo, ale bolo by to neefektívne pre veľké hodnoty n , pretože by to vyžadovalo výpočet všetkých predchádzajúcich Fibonacciho čísel.

Dynamický programovací prístup:

Fibonacciho séria využívajúca dynamické programovanie

• Podproblémy: F(0), F(1), F(2), F(3), …
• Riešenia predajní: Vytvorte tabuľku na uloženie hodnôt F(n) pri ich výpočte.
• Vybudovanie riešení: Pre F(n) vyhľadajte F(n-1) a F(n-2) v tabuľke a pridajte ich.
• Vyhnite sa redundancii: Tabuľka zabezpečuje, že každý podproblém (napr. F(2)) je vyriešený iba raz.

Pomocou DP môžeme efektívne vypočítať Fibonacciho sekvenciu bez toho, aby sme museli prepočítavať podproblémy.

Príklad 2: Najdlhšia spoločná podsekvencia (nájdenie najdlhšej podsekvencie, ktorá je spoločná pre dva reťazce)

Príklad 3: Najkratšia cesta v grafe (nájdenie najkratšej cesty medzi dvoma uzlami v grafe)

Príklad 4: Problém s batohom (zistenie maximálnej hodnoty položiek, ktoré je možné vložiť do batohu s danou kapacitou)

Kedy použiť dynamické programovanie (DP)?

Dynamické programovanie je optimalizačná technika používaná pri riešení problémov, ktorá pozostáva z nasledujúcich charakteristík:

1. Optimálna spodná štruktúra:

Optimálna subštruktúra znamená, že kombinujeme optimálne výsledky čiastkových problémov, aby sme dosiahli optimálny výsledok väčšieho problému.

Príklad:

Zvážte problém nájsť minimálne náklady cesta vo váženom grafe z a zdroj uzol do a destinácia uzol. Tento problém môžeme rozdeliť na menšie podproblémy:

• Nájsť minimálne náklady cesta z zdroj uzol každému medziprodukt uzol.
• Nájsť minimálne náklady cesta z každého medziprodukt uzol na destinácia uzol.

Riešenie väčšieho problému (nájdenie cesty s minimálnymi nákladmi zo zdrojového uzla do cieľového uzla) možno zostaviť z riešení týchto menších čiastkových problémov.

2. Prekrývajúce sa čiastkové problémy:

V rôznych častiach problému sa opakovane riešia rovnaké podproblémy.

Príklad:

Zvážte problém s výpočtom Fibonacciho séria . Na výpočet Fibonacciho čísla v indexe n , musíme vypočítať Fibonacciho čísla v indexoch n-1 a n-2 . To znamená, že čiastkový problém výpočtu Fibonacciho čísla na indexe n-1 sa používa dvakrát pri riešení väčšieho problému výpočtu Fibonacciho čísla v indexe n .

Prístupy dynamického programovania (DP)

Dynamické programovanie je možné dosiahnuť dvoma spôsobmi:

1. Prístup zhora nadol (zapamätanie):

V prístupe zhora nadol, známom aj ako zapamätanie , začneme s konečným riešením a rekurzívne ho rozložíme na menšie podproblémy. Aby sme sa vyhli nadbytočným výpočtom, ukladáme výsledky vyriešených čiastkových úloh do memoizačnej tabuľky.

Poďme si rozobrať prístup zhora nadol:

• Začína sa konečným riešením a rekurzívne ho rozdeľuje na menšie čiastkové problémy.
• Ukladá riešenia čiastkových problémov do tabuľky, aby sa predišlo nadbytočným výpočtom.
• Vhodné, keď je počet čiastkových problémov veľký a mnohé z nich sa znovu používajú.

2. Prístup zdola nahor (tabuľka):

V prístupe zdola nahor, známom aj ako tabelácia , začíname od najmenších čiastkových problémov a postupne sa dostávame ku konečnému riešeniu. Výsledky vyriešených podproblémov ukladáme do tabuľky, aby sme sa vyhli nadbytočným výpočtom.

Poďme si rozobrať prístup zdola nahor:

• Začína sa od najmenších čiastkových problémov a postupne sa dostáva ku konečnému riešeniu.
• Vyplní tabuľku riešeniami podproblémov zdola nahor.
• Vhodné, keď je počet podproblémov malý a optimálne riešenie možno priamo vypočítať z riešení menších podproblémov.

Dynamické programovanie (DP) Algoritmus

Dynamické programovanie je algoritmická technika, ktorá rieši zložité problémy tak, že ich rozdelí na menšie čiastkové problémy a ich riešenia uloží pre budúce použitie. Je obzvlášť účinný pri problémoch, ktoré obsahujú prekrývajúce sa čiastkové problémy a optimálna spodná konštrukcia.

Bežné algoritmy, ktoré používajú dynamické programovanie:

• Najdlhšia spoločná sekvencia (LCS): Nájde najdlhšiu spoločnú podsekvenciu medzi dvoma reťazcami.
• Najkratšia cesta v grafe: Nájde najkratšiu cestu medzi dvoma uzlami v grafe.
• Problém s batohom: Určuje maximálnu hodnotu položiek, ktoré je možné umiestniť do batohu s danou kapacitou.
• Násobenie maticového reťazca: Optimalizuje poradie násobenia matíc, aby sa minimalizoval počet operácií.
• Fibonacciho sekvencia: Vypočíta n-té Fibonacciho číslo.

Výhody dynamického programovania (DP)

Dynamické programovanie má širokú škálu výhod, medzi ktoré patria:

• Zabraňuje viacnásobnému prepočítavaniu rovnakých čiastkových problémov, čo vedie k výraznej úspore času.
• Zabezpečuje nájdenie optimálneho riešenia zvážením všetkých možných kombinácií.
• Rozdeľuje zložité problémy na menšie, lepšie zvládnuteľné podproblémy.

Aplikácie dynamického programovania (DP)

Dynamické programovanie má širokú škálu aplikácií, vrátane:

• Optimalizácia: Problém s batohom, problém s najkratšou cestou, problém s maximálnym podpolím
• Počítačová veda: Najdlhšia spoločná podsekvencia, vzdialenosť úprav, párovanie reťazcov
• Operačný výskum: Riadenie zásob, plánovanie, alokácia zdrojov

Teraz preskúmame komplexný plán na zvládnutie dynamického programovania.

Naučte sa základy dynamického programovania (DP)

• Čo je zapamätanie? Kompletný návod
• Tabuľka verzus memoizácia
• Optimálna vlastnosť spodnej stavby
• Vlastnosť prekrývajúcich sa podproblémov
• Ako vyriešiť problém dynamického programovania?

• Fibonacciho čísla
• n-té katalánske číslo
• Čísla zvonov (počet spôsobov, ako rozdeliť sadu)
• Binomický koeficient
• Problém s výmenou mincí
• Problém podmnožiny súčtu
• Vypočítajte nCr % p
• Rezanie tyče
• Algoritmus maľovania plotu
• Najdlhšia spoločná sekvencia
• Najdlhšia rastúca následná sekvencia
• Najdlhšia podsekvencia taká, že rozdiel medzi susedmi je jedna
• Maximálna veľkosť štvorcovej podmatice so všetkými 1
• Cesta minimálnych nákladov
• Minimálny počet skokov na dosiahnutie konca
• Najdlhší spoločný podreťazec (riešenie DP optimalizované pre priestor)
• Spočítajte spôsoby, ako sa dostať na n-tý schodík pomocou kroku 1, 2 alebo 3
• Spočítajte všetky možné cesty od ľavého horného rohu po pravý spodný okraj matice mXn
• Jedinečné cesty v mriežke s prekážkami

2. Stredné problémy dynamického programovania (DP)

• Algoritmus Floyda Warshalla
• Bellman-Fordov algoritmus
• 0-1 Problém s batohom
• Tlač položiek v 0/1 batohu
• Neohraničený batoh (opakovanie položiek povolené)
• Puzzle na kvapkanie vajíčok
• Problém zlomu slov
• Problém krytu vertexu
• Problém so stohovaním dlaždíc
• Problém stohovania krabičiek
• Problém s oddielmi
• Problém obchodného cestujúceho | Sada 1 (naivné a dynamické programovanie)
• Najdlhšia palindromická sekvencia
• Najdlhšia spoločná rastúca podsekvencia (LCS + LIS)
• Nájdite všetky rozdielne súčty podmnožín (alebo podsekvencií) poľa
• Vážené plánovanie úloh
• Počítajte odchýlky (permutácia taká, že žiadny prvok sa neobjaví na svojej pôvodnej pozícii)
• Minimálne vloženia na vytvorenie palindrómu
• Zhoda vzoru zástupných znakov
• Spôsoby usporiadania guľôčok tak, aby susedné gule boli rôznych typov

3. Ťažké problémy dynamického programovania (DP)

• Rozdelenie palindrómu
• Problém zalamovania slov
• Problém maliarovej priečky
• Program na riešenie problémov s mostom a pochodňou
• Násobenie maticového reťazca
• Tlač zátvoriek v probléme násobenia maticového reťazca
• Obdĺžnik maximálneho súčtu v 2D matici
• Maximálny zisk nákupom a predajom podielu najviac k-krát
• Minimálne náklady na triedenie reťazcov pomocou operácií obrátenia rôznych nákladov
• Počet AP (aritmetická progresia) subsekvencií v poli
• Úvod do dynamického programovania na stromoch
• Maximálna výška stromu, keď sa ktorýkoľvek uzol môže považovať za koreň
• Najdlhší opakujúci sa a neprekrývajúci sa podreťazec

Rýchle odkazy:

• Naučte sa dátovú štruktúru a algoritmy | Príručka DSA
• 20 najčastejších otázok na pohovor o dynamickom programovaní
• „Problémy s cvičením“ dynamického programovania
• „Kvíz“ o dynamickom programovaní