Dynamické programovanie je technika, ktorá rozdeľuje problémy na čiastkové problémy a ukladá výsledok pre budúce účely, aby sme výsledok nemuseli znova počítať. Podproblémy sú optimalizované tak, aby optimalizovali celkové riešenie, ktoré je známe ako optimálna vlastnosť subštruktúry. Hlavným využitím dynamického programovania je riešenie optimalizačných problémov. Optimalizačné problémy tu znamenajú, že keď sa snažíme nájsť minimálne alebo maximálne riešenie problému. Dynamické programovanie zaručuje nájdenie optimálneho riešenia problému, ak riešenie existuje.
Definícia dynamického programovania hovorí, že ide o techniku riešenia zložitého problému tak, že sa najprv rozdelí na kolekciu jednoduchších čiastkových problémov, každý čiastkový problém sa vyrieši len raz a potom sa ich riešenia uložia, aby sa predišlo opakovaným výpočtom.
Poďme pochopiť tento prístup na príklade.
Zoberme si príklad Fibonacciho série. Nasledujúca séria je séria Fibonacci:
otvorte súbor pomocou java
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
Čísla vo vyššie uvedených sériách nie sú vypočítané náhodne. Matematicky by sme mohli napísať každý z výrazov pomocou nižšie uvedeného vzorca:
F(n) = F(n-1) + F(n-2),
So základnými hodnotami F(0) = 0 a F(1) = 1. Pri výpočte ostatných čísel postupujeme podľa vyššie uvedeného vzťahu. Napríklad F(2) je súčet f(0) a f(1), čo sa rovná 1.
Ako môžeme vypočítať F(20)?
Člen F(20) sa vypočíta pomocou n-tého vzorca Fibonacciho radu. Nasledujúci obrázok ukazuje, ako sa vypočíta F(20).
mb na gb
Ako môžeme vidieť na obrázku vyššie, F(20) sa vypočíta ako súčet F(19) a F(18). V prístupe dynamického programovania sa snažíme rozdeliť problém na podobné podproblémy. Tento prístup sledujeme vo vyššie uvedenom prípade, keď F(20) do podobných podproblémov, t.j. F(19) a F(18). Ak si zrekapitulujeme definíciu dynamického programovania, hovorí, že podobný podproblém by sa nemal počítať viackrát. Napriek tomu sa vo vyššie uvedenom prípade podproblém počíta dvakrát. Vo vyššie uvedenom príklade sa F(18) vypočíta dvakrát; podobne aj F(17) sa vypočítava dvakrát. Táto technika je však celkom užitočná, pretože rieši podobné podproblémy, ale pri ukladaní výsledkov musíme byť opatrní, pretože nám nezáleží na ukladaní výsledku, ktorý sme raz vypočítali, potom to môže viesť k plytvaniu zdrojmi.
Ak vo vyššie uvedenom príklade vypočítame F(18) v pravom podstrome, vedie to k obrovskému využívaniu zdrojov a znižuje celkový výkon.
Riešením vyššie uvedeného problému je uložiť vypočítané výsledky do poľa. Najprv vypočítame F(16) a F(17) a ich hodnoty uložíme do poľa. F(18) sa vypočíta sčítaním hodnôt F(17) a F(16), ktoré sú už uložené v poli. Vypočítaná hodnota F(18) sa uloží do poľa. Hodnota F(19) sa vypočíta pomocou súčtu F(18) a F(17) a ich hodnoty sú už uložené v poli. Vypočítaná hodnota F(19) je uložená v poli. Hodnotu F(20) možno vypočítať sčítaním hodnôt F(19) a F(18) a hodnoty F(19) aj F(18) sú uložené v poli. Konečná vypočítaná hodnota F(20) je uložená v poli.
Ako funguje prístup dynamického programovania?
Nasledujú kroky, ktorými sa riadi dynamické programovanie:
- Rozdeľuje komplexný problém na jednoduchšie podproblémy.
- Nájde optimálne riešenie týchto čiastkových problémov.
- Ukladá výsledky čiastkových problémov (zapamätanie). Proces ukladania výsledkov čiastkových problémov je známy ako memorovanie.
- Opätovne ich používa, takže rovnaký čiastkový problém sa vypočíta viackrát.
- Nakoniec vypočítajte výsledok zložitého problému.
Vyššie uvedených päť krokov sú základné kroky pre dynamické programovanie. Je použiteľné dynamické programovanie, ktoré má vlastnosti ako:
premenné typu java
Tie problémy, ktoré majú prekrývajúce sa podproblémy a optimálne podštruktúry. Optimálna subštruktúra tu znamená, že riešenie optimalizačných problémov možno získať jednoduchou kombináciou optimálneho riešenia všetkých čiastkových problémov.
V prípade dynamického programovania by sa priestorová zložitosť zvýšila pri ukladaní medzivýsledkov, no časová zložitosť by sa znížila.
Prístupy dynamického programovania
Existujú dva prístupy k dynamickému programovaniu:
- Prístup zhora nadol
- Prístup zdola nahor
Prístup zhora nadol
Prístup zhora nadol sa riadi technikou zapamätania, prístup zdola nahor sa riadi tabuľkovou metódou. Tu sa zapamätanie rovná súčtu rekurzie a ukladania do vyrovnávacej pamäte. Rekurzia znamená volanie samotnej funkcie, zatiaľ čo ukladanie do vyrovnávacej pamäte znamená ukladanie medzivýsledkov.
Výhody
Počet sql odlišný
- Je to veľmi jednoduché na pochopenie a implementáciu.
- Podproblémy rieši len vtedy, keď je to potrebné.
- Je ľahké ladiť.
Nevýhody
Používa techniku rekurzie, ktorá zaberá viac pamäte v zásobníku hovorov. Niekedy, keď je rekurzia príliš hlboká, nastane stav pretečenia zásobníka.
Zaberá viac pamäte, čo znižuje celkový výkon.
Poďme pochopiť dynamické programovanie na príklade.
int fib(int n) { if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); } < pre> <p>In the above code, we have used the recursive approach to find out the Fibonacci series. When the value of 'n' increases, the function calls will also increase, and computations will also increase. In this case, the time complexity increases exponentially, and it becomes 2<sup>n</sup>.</p> <p>One solution to this problem is to use the dynamic programming approach. Rather than generating the recursive tree again and again, we can reuse the previously calculated value. If we use the dynamic programming approach, then the time complexity would be O(n).</p> <p>When we apply the dynamic programming approach in the implementation of the Fibonacci series, then the code would look like:</p> <pre> static int count = 0; int fib(int n) { if(memo[n]!= NULL) return memo[n]; count++; if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); memo[n]="sum;" } < pre> <p>In the above code, we have used the memorization technique in which we store the results in an array to reuse the values. This is also known as a top-down approach in which we move from the top and break the problem into sub-problems.</p> <h3>Bottom-Up approach</h3> <p>The bottom-up approach is also one of the techniques which can be used to implement the dynamic programming. It uses the tabulation technique to implement the dynamic programming approach. It solves the same kind of problems but it removes the recursion. If we remove the recursion, there is no stack overflow issue and no overhead of the recursive functions. In this tabulation technique, we solve the problems and store the results in a matrix.</p> <p>There are two ways of applying dynamic programming:</p> <ul> <tr><td>Top-Down</td> </tr><tr><td>Bottom-Up</td> </tr></ul> <p>The bottom-up is the approach used to avoid the recursion, thus saving the memory space. The bottom-up is an algorithm that starts from the beginning, whereas the recursive algorithm starts from the end and works backward. In the bottom-up approach, we start from the base case to find the answer for the end. As we know, the base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts from the base cases, so we will start from 0 and 1.</p> <p> <strong>Key points</strong> </p> <ul> <li>We solve all the smaller sub-problems that will be needed to solve the larger sub-problems then move to the larger problems using smaller sub-problems.</li> <li>We use for loop to iterate over the sub-problems.</li> <li>The bottom-up approach is also known as the tabulation or table filling method.</li> </ul> <p> <strong>Let's understand through an example.</strong> </p> <p>Suppose we have an array that has 0 and 1 values at a[0] and a[1] positions, respectively shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-2.webp" alt="Dynamic Programming"> <p>Since the bottom-up approach starts from the lower values, so the values at a[0] and a[1] are added to find the value of a[2] shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-3.webp" alt="Dynamic Programming"> <p>The value of a[3] will be calculated by adding a[1] and a[2], and it becomes 2 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-4.webp" alt="Dynamic Programming"> <p>The value of a[4] will be calculated by adding a[2] and a[3], and it becomes 3 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-5.webp" alt="Dynamic Programming"> <p>The value of a[5] will be calculated by adding the values of a[4] and a[3], and it becomes 5 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-6.webp" alt="Dynamic Programming"> <p>The code for implementing the Fibonacci series using the bottom-up approach is given below:</p> <pre> int fib(int n) { int A[]; A[0] = 0, A[1] = 1; for( i=2; i<=n; i++) { a[i]="A[i-1]" + a[i-2] } return a[n]; < pre> <p>In the above code, base cases are 0 and 1 and then we have used for loop to find other values of Fibonacci series.</p> <p> <strong>Let's understand through the diagrammatic representation.</strong> </p> <p>Initially, the first two values, i.e., 0 and 1 can be represented as:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-7.webp" alt="Dynamic Programming"> <p>When i=2 then the values 0 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-8.webp" alt="Dynamic Programming"> <p>When i=3 then the values 1and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-9.webp" alt="Dynamic Programming"> <p>When i=4 then the values 2 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-10.webp" alt="Dynamic Programming"> <p>When i=5, then the values 3 and 2 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-11.webp" alt="Dynamic Programming"> <p>In the above case, we are starting from the bottom and reaching to the top.</p> <hr></=n;></pre></0)></pre></0)>