Dynamische Programmierung ist eine Technik, die Probleme in Teilprobleme aufteilt und das Ergebnis für zukünftige Zwecke speichert, sodass wir das Ergebnis nicht erneut berechnen müssen. Die Teilprobleme werden optimiert, um die Gesamtlösung zu optimieren, was als optimale Unterstruktureigenschaft bezeichnet wird. Der Haupteinsatzzweck der dynamischen Programmierung ist die Lösung von Optimierungsproblemen. Optimierungsprobleme bedeuten hier, dass wir versuchen, die minimale oder maximale Lösung eines Problems herauszufinden. Die dynamische Programmierung garantiert, die optimale Lösung eines Problems zu finden, wenn die Lösung existiert.
Die Definition der dynamischen Programmierung besagt, dass es sich dabei um eine Technik zur Lösung eines komplexen Problems handelt, bei der man zunächst in eine Sammlung einfacherer Teilprobleme aufbricht, jedes Teilproblem nur einmal löst und die Lösungen dann speichert, um sich wiederholende Berechnungen zu vermeiden.
Lassen Sie uns diesen Ansatz anhand eines Beispiels verstehen.
Betrachten Sie ein Beispiel der Fibonacci-Reihe. Die folgende Reihe ist die Fibonacci-Reihe:
partielle Ableitungen in Latex
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
Die Zahlen in der obigen Reihe werden nicht zufällig berechnet. Mathematisch könnten wir jeden der Begriffe mit der folgenden Formel schreiben:
F(n) = F(n-1) + F(n-2),
Mit den Basiswerten F(0) = 0 und F(1) = 1. Um die anderen Zahlen zu berechnen, folgen wir der obigen Beziehung. Beispielsweise ist F(2) die Summe f(0) Und f(1), was gleich 1 ist.
Wie können wir F(20) berechnen?
Der F(20)-Term wird mithilfe der n-ten Formel der Fibonacci-Reihe berechnet. Die folgende Abbildung zeigt, wie F(20) berechnet wird.
Datenstrukturen Java
Wie wir in der obigen Abbildung sehen können, wird F(20) als Summe von F(19) und F(18) berechnet. Beim dynamischen Programmieransatz versuchen wir, das Problem in ähnliche Teilprobleme zu unterteilen. Wir verfolgen diesen Ansatz im obigen Fall, in dem F(20) in die ähnlichen Teilprobleme, d. h. F(19) und F(18), aufgeteilt wird. Wenn wir die Definition der dynamischen Programmierung noch einmal zusammenfassen, heißt es, dass das ähnliche Teilproblem nicht mehr als einmal berechnet werden sollte. Dennoch wird im obigen Fall das Teilproblem zweimal berechnet. Im obigen Beispiel wird F(18) zweimal berechnet; In ähnlicher Weise wird auch F(17) zweimal berechnet. Diese Technik ist jedoch sehr nützlich, da sie ähnliche Teilprobleme löst. Wir müssen jedoch beim Speichern der Ergebnisse vorsichtig sein, da wir nicht besonders darauf achten, das einmal berechnete Ergebnis zu speichern, da dies zu einer Verschwendung von Ressourcen führen kann.
Wenn wir im obigen Beispiel F(18) im rechten Teilbaum berechnen, führt dies zu einem enormen Ressourcenverbrauch und verringert die Gesamtleistung.
Die Lösung des oben genannten Problems besteht darin, die berechneten Ergebnisse in einem Array zu speichern. Zuerst berechnen wir F(16) und F(17) und speichern ihre Werte in einem Array. F(18) wird durch Summieren der Werte von F(17) und F(16) berechnet, die bereits in einem Array gespeichert sind. Der berechnete Wert von F(18) wird in einem Array gespeichert. Der Wert von F(19) wird anhand der Summe von F(18) und F(17) berechnet und ihre Werte sind bereits in einem Array gespeichert. Der berechnete Wert von F(19) wird in einem Array gespeichert. Der Wert von F(20) kann durch Addition der Werte von F(19) und F(18) berechnet werden, und die Werte von F(19) und F(18) werden in einem Array gespeichert. Der endgültig berechnete Wert von F(20) wird in einem Array gespeichert.
Wie funktioniert der dynamische Programmieransatz?
Im Folgenden sind die Schritte aufgeführt, denen die dynamische Programmierung folgt:
- Es zerlegt das komplexe Problem in einfachere Teilprobleme.
- Es findet die optimale Lösung für diese Teilprobleme.
- Es speichert die Ergebnisse von Teilproblemen (Memoisierung). Der Vorgang des Speicherns der Ergebnisse von Teilproblemen wird als Auswendiglernen bezeichnet.
- Sie werden wiederverwendet, sodass dasselbe Teilproblem mehr als einmal berechnet wird.
- Berechnen Sie abschließend das Ergebnis des komplexen Problems.
Die oben genannten fünf Schritte sind die Grundschritte der dynamischen Programmierung. Die dynamische Programmierung ist anwendbar, die Eigenschaften hat wie:
Bienenstockarchitektur
Diese Probleme haben überlappende Teilprobleme und optimale Unterstrukturen. Optimale Unterstruktur bedeutet hier, dass die Lösung von Optimierungsproblemen durch einfache Kombination der optimalen Lösung aller Teilprobleme erhalten werden kann.
Im Fall der dynamischen Programmierung würde sich die räumliche Komplexität erhöhen, da wir die Zwischenergebnisse speichern, aber die zeitliche Komplexität würde sinken.
JFX-Java-Tutorial
Ansätze der dynamischen Programmierung
Es gibt zwei Ansätze zur dynamischen Programmierung:
- Top-Down-Ansatz
- Bottom-up-Ansatz
Top-Down-Ansatz
Der Top-Down-Ansatz folgt der Memorisierungstechnik, während der Bottom-Up-Ansatz der Tabellierungsmethode folgt. Hier entspricht das Auswendiglernen der Summe aus Rekursion und Caching. Unter Rekursion versteht man den Aufruf der Funktion selbst, während Caching die Speicherung der Zwischenergebnisse bedeutet.
Vorteile
- Es ist sehr einfach zu verstehen und umzusetzen.
- Es löst die Teilprobleme nur dann, wenn es erforderlich ist.
- Es ist einfach zu debuggen.
Nachteile
Es verwendet die Rekursionstechnik, die mehr Speicher im Aufrufstapel belegt. Wenn die Rekursion zu tief ist, kommt es manchmal zu einem Stapelüberlauf.
Es belegt mehr Speicher, was die Gesamtleistung beeinträchtigt.
Lassen Sie uns die dynamische Programmierung anhand eines Beispiels verstehen.
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)>