Einführung in die dynamische Programmierung: Überlappende Teilprobleme und optimale Teilstruktur

Veröffentlicht: 2021-02-08

Inhaltsverzeichnis

Einführung

Nehmen wir an, wir hätten eine Aufgabe, um das Quadrat von 25 zu lösen. Wenn wir vor dieser Frage zum ersten Mal stehen, können wir sie entweder auf der Hand oder mit einem Taschenrechner lösen. Aber wenn wir diese Frage schon einmal gesehen oder gelöst haben, besteht die Möglichkeit, dass wir sie schnell beantworten, indem wir sie auswendig lernen.

Dies bringt uns zu dem Schluss, dass wir es beim nächsten Mal überspringen können, wenn wir uns daran erinnern können. Die dynamische Programmierung arbeitet nach einem ähnlichen Konzept, die Idee ist, sich das Ergebnis einer Berechnung zu merken und es bei Bedarf in der Zukunft zu verwenden.

Dieses einfache Verfahren der dynamischen Programmierung macht es zu einer starken Waffe für einen Programmierer, um den Kampf um effizienten Code zu gewinnen.

Nehmen wir zum Beispiel an, wir haben eine komplexe Fragestellung und uns fällt immer eine Lösung ein, die die Fragestellung in Teilprobleme aufteilt. Aber wir können in einer Situation stecken bleiben, in der wir ein Teilproblem mehrmals berechnen. Dort nutzen wir die dynamische Programmierung für eine optimale Lösung.

Die dynamische Programmierung hat zwei Konzepte:

  1. Überlappende Teilprobleme
  2. Optimaler Unterbau

Überlappende Teilprobleme

Ein klassisches Beispiel für das Verständnis des Konzepts der überlappenden Teilprobleme ist ein Programm zum Drucken der Fibonacci-Reihe.

Die Logik der Fibonacci-Reihe ist gegeben durch „fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)“. Und die nahtlose Ausführung dieser Funktion kann mit einer rekursiven Lösung mit einem Basisfall von fibonacci(0)=0 und fibonacci(1)=1 erfolgen.

öffentlich statisch int fibonacci(int n){
 wenn (n== 0 || n== 1 )
 gib n zurück;
 Rückgabe Fibonacci(n -1 )+Fibonacci(n -2 );
 }
 public static void main(String[] args){
 System.out.print( „4. Fibonacci-Zahl ist „ +fibonacci( 4 ));
 }

Angenommen, wir müssen die 4. Fibonacci-Ziffer drucken, dann geht der Rekursionsbaum wie folgt

fibonacci(4)

/ \

Fibonacci(3) + Fibonacci(2)

/ \ / \

Fibonacci(2) + Fibonacci(1) Fibonacci(1) + Fibonacci(0)

/ \

Fibonacci(1) + Fibonacci(0)

Beachten Sie, dass Fibonacci(4) die 5. Ziffer in der Fibonacci-Reihe ist, da wir bei Fibonacci(0) beginnen. Im obigen Rekursionsbaum sehen wir, dass fibonacci(2) zweimal wiederholt wird. Wir haben eine Duplizierung in einem Rekursionsbaum der Höhe 4 beobachtet, stellen Sie sich nun vor, wir hätten einen rekursiven Aufruf mit einer großen Anzahl, und anschließend wird es einen Rekursionsbaum mit einer großen Höhe geben. Und es wird viele solcher doppelten Berechnungen geben, die als überlappende Teilprobleme bekannt sind.

Wir haben zwei Methoden, um mit dieser (i) Tabellierung, (ii) Auswendiglernen umzugehen

Lassen Sie uns sie verstehen, indem wir ihre Implementierungen durchgehen.

Auswendiglernen

Das Lösen des Fibonacci-Problems mit der Memoisierungsmethode kann wie unten gezeigt durchgeführt werden

statisches int[]-Memo;
öffentlich statisch int fibonacci(int n){
if(Memo[n]!=-1)
Rückvermerk[n];
if(n==0 || n==1){
memo[n]=n;
gib n zurück;
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
Rückvermerk[n];
}
public static void main(String[] args){
memo=neu int[5];
for(int i=0;i<=4;i++)
memo[i]=-1;
System.out.println(„4. Fibonacci-Zahl ist „+fibonacci(4));
}

Im obigen Code erstellen wir eine Protokolldatei oder eine Nachschlagetabelle und speichern die Werte der berechneten Ergebnisse. Da wir alle berechneten Werte gespeichert haben, können wir sie bei Bedarf in Zukunft verwenden, wodurch doppelte Berechnungen und sich überschneidende Teilprobleme vermieden werden.

Die gesamte Logik ähnelt der rekursiven Lösung, aber der einzige Unterschied, den wir gemacht haben, ist, dass wir sie im Memo-Array notieren, bevor wir den Wert an die Hauptmethode zurückgeben. Die einzige Einschränkung für diesen Algorithmus besteht darin, dass wir einen zusätzlichen Raum der Größe O(n) benötigen, aber wir optimieren die vorherige rekursive Lösung.

Tabellierung

Diese Methode unterscheidet sich ein wenig von der obigen Lösung. Memoization folgt der gleichen rekursiven Lösung. Aber in der Tabellierung folgen wir einer iterativen Lösung. Dies wird auch als Bottom-up-Ansatz bezeichnet. Betrachten wir die Umsetzung des Bottom-up-Ansatzes.

öffentlich statisch int fibonacci(int n){
 int table[]=new int[n+ 1 ];
 für (int i= 0 ;i<=n;i++){
 wenn (i== 0 || i== 1 )
 Tabelle[i]=i;
 sonst {
 Tabelle[i]=Tabelle[i -1 ]+Tabelle[i -2 ];
 }
 }
 Rückgabetabelle [n];
 }
 public static void main(String[] args){
 System.out.println( „4. Fibonacci-Zahl ist „ +fibonacci( 4 ));
 }

Da wir wissen, dass fibonacci(n)=fibonacci(n-1)+fibonacci(n-2) ist, haben wir bei der Memoisierung mit dem Funktionsaufruf fibonacci(4) begonnen, und dann haben wir festgestellt, dass wir seinen Wert nicht berechnet haben, also haben wir habe seine Werte berechnet und dann gespeichert.

Eine ähnliche Situation wird bei weiteren rekursiven Aufrufen wie fibonacci(3), fibonacci(2) auftreten. Das lässt viele rekursive Aufrufe im Rekursionsstack warten, aber wir überspringen sowieso die Duplizierung der sich überschneidenden Teilprobleme.

Wir haben auch eine Möglichkeit, Fibonacci iterativ von 0 bis zum n-ten Element zu berechnen und dann das n-te Fibonacci-Element zurückzugeben. Dies haben wir im obigen Code implementiert. Auch dieser Code hat den gleichen Platzbedarf O(n).

Checkout: Fähigkeiten, um ein Full-Stack-Entwickler zu werden

Optimaler Unterbau

In diesem Konzept können wir nur dann eine optimale Lösung für ein Problem erhalten, wenn wir die entsprechenden Teilprobleme optimal gelöst haben.

Und ein klassisches Beispiel für dieses Konzept ist das Betrachten einer Traversierung zwischen Knoten in einem Graphen.

Nehmen wir an, wir haben mehrere Wurzeln von Telangana bis Delhi. Und wenn wir die kürzeste Route haben, die durch Nagpur und Gwalior führt. Dann muss der kürzeste Weg von Nagpur nach Delhi Delhi durch Gwalior führen. Jetzt können wir unser Problem in Unterprobleme aufteilen, nämlich Telangana bis Nagpur, Nagpur bis Gwalior, Gwalior bis Delhi.

Und ein klassisches Beispiel für diese Eigenschaft ist die längste gemeinsame Teilfolge in beiden Strings. Eine Teilsequenz unterscheidet sich von einer Teilzeichenfolge. In einer Untersequenz müssen die Zeichen in der ursprünglichen Zeichenfolge nicht aufeinanderfolgen.

Die Idee ist also, es zu lösen, indem man seine Teilprobleme optimal löst. Sei n die Länge der längsten gemeinsamen Teilfolge.

Wenn n=LCS(Kartoffel, Tätowierung), dann n=LCS(Kartoffel,Tätowierung)+1 (wenn die letzten Zeichen gleich sind), sonst n=Maximum(LCS(Kartoffel,Tätowierung), LCS(Kartoffel, Tätowierung).

static int lcs(String s1, String s2, int m, int n ){
 int dp[][] = neu int[m+ 1 ][n+ 1 ];
 for (int i= 0 ; i<=m; i++){
 for (int j= 0 ; j<=n; j++){
 wenn (i == 0 || j == 0 )
 dp[i][j] = 0 ;
 Sonst wenn (s1.charAt(i -1 ) == s2.charAt(j -1 ))
 dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
 anders
 dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
 }
 }
 gib dp[m][n] zurück;
 }
 public static void main(String[] args){
 System.out.println( „Länge der längsten gemeinsamen Teilsequenz ist „ +lcs( „potato“ , „tattoo“ , 6 , 6 ));
 }

Im obigen Code haben wir unsere Logik mithilfe der Tabellierungsmethode implementiert und die Länge der längsten gemeinsamen Teilsequenz berechnet, die in beiden Zeichenfolgen vorhanden ist.

Lesen Sie auch: Full-Stack-Entwicklergehalt in Indien

Lernen Sie Softwareentwicklungskurse online von den besten Universitäten der Welt. Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.

Fazit

Jetzt, da Sie sich bewusst sind, dass Sie eine der leistungsstarken Techniken verwenden, um den Kampf um effizienten Code zu gewinnen, versuchen Sie, dynamische Programmierung für andere Probleme zu implementieren, und beginnen Sie, Ihre Fähigkeit zu verbessern, eine Frage mithilfe dynamischer Programmierung zu codieren.

Zusammenfassend lässt sich sagen, dass die Full-Stack-Entwicklerkurse hochqualifizierte Experten sind, die mit allem umgehen können, was mit der Webentwicklung zu tun hat. Diese Full-Stack-Entwicklerfähigkeiten unterscheiden sie von Frontend- und Backend-Entwicklern.

Was ist dynamische Programmierung?

Ein Computerprogramm enthält viele sich wiederholende Codes. Dies ist ineffizient und kann die Leistung beeinträchtigen. In diesem Fall wird dynamische Programmierung verwendet. Dynamische Programmierung ist eine Methode zur Lösung eines komplexen Problems, indem es in einfachere Unterprobleme zerlegt wird, jedes dieser Unterprobleme nur einmal gelöst wird und ihre Lösungen in Tabellen gespeichert werden, die dann nachgeschlagen werden, wenn später ein ähnliches Unterproblem auftritt die Lösung des komplexen Problems. Dynamische Programmieralgorithmen werden verwendet, um verschiedene Arten von Optimierungsproblemen in den Bereichen Betriebsforschung, statistische Schätzung, Mustererkennung, künstliche Intelligenz, maschinelles Lernen, Computerbiologie und andere Bereiche zu lösen.

Was ist ein überlappendes Teilproblem bei der dynamischen Programmierung?

Das überlappende Teilproblem ist ein Konzept, das verwendet wird, wenn Teilprobleme Lösungen haben, die auch in anderen Teilproblemen verwendet werden. Diese Überlappung führt dazu, dass dieselbe Teilaufgabe mehr als einmal gelöst wird. Das Problem besteht darin, einen Weg zu finden, die Teilaufgabe nur einmal zu lösen, und diese Lösung zu verwenden, um die Lösungen anderer Teilprobleme zu erhalten. Dynamische Programmieralgorithmen lösen dieses Problem durch Memoisierung. Memoization ist eine Technik, bei der wir Lösungen für Teilprobleme speichern, damit wir sie nicht noch einmal lösen müssen.

Was ist die optimale Unterstruktur in der dynamischen Programmierung?

Optimale Unterstruktur impliziert, dass die optimale Lösung eines Problems mit einer optimalen Lösung eines kleineren Problems innerhalb derselben Problemdefinition zusammenhängt. Eine optimale Unterkonstruktion ist eine zusätzliche Anforderung, die benötigt wird, um Probleme zu lösen oder zu beweisen, dass es keine Lösung gibt. Bei optimalem Unterbau können wir viele Probleme NP-schwer nachweisen. Ein allgemeiner Ansatz zum Lösen von DP-Problemen besteht darin, eine dynamische Programmiermatrix zu verwenden, um die optimale Lösung von Teilproblemen zu speichern. Eine dynamische Programmiermatrix kann verwendet werden, um alle DP-Probleme mit optimaler Unterstruktur ungleich Null zu lösen.