Dynamické programování je technika, která rozděluje problémy na dílčí problémy a ukládá výsledek pro budoucí účely, takže výsledek nemusíme znovu počítat. Dílčí problémy jsou optimalizovány tak, aby optimalizovaly celkové řešení známé jako optimální vlastnost substruktury. Hlavním využitím dynamického programování je řešení optimalizačních problémů. Optimalizační problémy zde znamenají, že když se snažíme najít minimální nebo maximální řešení problému. Dynamické programování zaručuje nalezení optimálního řešení problému, pokud řešení existuje.
Definice dynamického programování říká, že se jedná o techniku řešení složitého problému tak, že se nejprve prolomí sbírka jednodušších dílčích problémů, každý dílčí problém se vyřeší pouze jednou a poté se jejich řešení uloží, aby se předešlo opakovaným výpočtům.
Pojďme tento přístup pochopit na příkladu.
Zvažte příklad Fibonacciho řady. Následující série je série Fibonacci:
ostrov java
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
Čísla ve výše uvedené řadě nejsou náhodně vypočtena. Matematicky bychom mohli napsat každý z výrazů pomocí níže uvedeného vzorce:
F(n) = F(n-1) + F(n-2),
Se základními hodnotami F(0) = 0 a F(1) = 1. Pro výpočet ostatních čísel postupujeme podle výše uvedeného vztahu. Například F(2) je součet f(0) a f(1), což se rovná 1.
Jak můžeme vypočítat F(20)?
Člen F(20) bude vypočítán pomocí n-tého vzorce Fibonacciho řady. Níže uvedený obrázek ukazuje, jak se vypočítá F(20).
mb na gb
Jak můžeme vidět na obrázku výše, F(20) se vypočítá jako součet F(19) a F(18). V přístupu dynamického programování se snažíme rozdělit problém na podobné podproblémy. Tento přístup sledujeme ve výše uvedeném případě, kdy F(20) do podobných dílčích problémů, tj. F(19) a F(18). Pokud zrekapitulujeme definici dynamického programování, říká, že podobný podproblém by neměl být počítán více než jednou. Přesto se ve výše uvedeném případě podproblém počítá dvakrát. Ve výše uvedeném příkladu se F(18) vypočítá dvakrát; podobně se F(17) také počítá dvakrát. Tato technika je však docela užitečná, protože řeší podobné dílčí problémy, ale při ukládání výsledků musíme být opatrní, protože nám nezáleží na ukládání výsledku, který jsme vypočítali jednou, pak to může vést k plýtvání zdroji.
Pokud ve výše uvedeném příkladu spočítáme F(18) v pravém podstromu, pak to vede k obrovskému využití zdrojů a snižuje celkový výkon.
Řešením výše uvedeného problému je uložit vypočítané výsledky do pole. Nejprve spočítáme F(16) a F(17) a jejich hodnoty uložíme do pole. F(18) se vypočítá sečtením hodnot F(17) a F(16), které jsou již uloženy v poli. Vypočtená hodnota F(18) je uložena v poli. Hodnota F(19) se vypočítá pomocí součtu F(18) a F(17) a jejich hodnoty jsou již uloženy v poli. Vypočítaná hodnota F(19) je uložena v poli. Hodnotu F(20) lze vypočítat sečtením hodnot F(19) a F(18) a hodnoty F(19) a F(18) jsou uloženy v poli. Konečná vypočítaná hodnota F(20) je uložena v poli.
Jak funguje přístup dynamického programování?
Následují kroky, které dynamické programování následuje:
- Rozkládá složitý problém na jednodušší podproblémy.
- Najde optimální řešení těchto dílčích problémů.
- Ukládá výsledky dílčích problémů (memoizace). Proces ukládání výsledků dílčích problémů je známý jako zapamatování.
- Znovu je použije, takže stejný dílčí problém je vypočítán více než jednou.
- Nakonec vypočítejte výsledek složité úlohy.
Výše uvedených pět kroků jsou základní kroky pro dynamické programování. Je použitelné dynamické programování, které má vlastnosti jako:
platné identifikátory v jazyce Java
Ty problémy, které mají překrývající se dílčí problémy a optimální podstruktury. Optimální podstruktura zde znamená, že řešení optimalizačních problémů lze získat jednoduchou kombinací optimálního řešení všech dílčích problémů.
V případě dynamického programování by se prostorová složitost zvýšila, protože ukládáme mezivýsledky, ale snížila by se časová složitost.
Přístupy dynamického programování
Existují dva přístupy k dynamickému programování:
sada c++
- Přístup shora dolů
- Přístup zdola nahoru
Přístup shora dolů
Přístup shora dolů se řídí technikou zapamatování, zatímco přístup zdola nahoru se řídí metodou tabulací. Zde se zapamatování rovná součtu rekurze a ukládání do mezipaměti. Rekurze znamená volání samotné funkce, zatímco ukládání do mezipaměti znamená ukládání mezivýsledků.
Výhody
- Je to velmi snadné pochopit a implementovat.
- Řeší dílčí problémy pouze tehdy, když je to vyžadováno.
- Je snadné ladit.
Nevýhody
Využívá techniku rekurze, která zabírá více paměti v zásobníku volání. Někdy, když je rekurze příliš hluboká, nastane stav přetečení zásobníku.
Zabírá více paměti, což snižuje celkový výkon.
Pojďme pochopit dynamické programování na příkladu.
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)>