Dynamische Programmierung verstehen, damit Sie sie effektiv nutzen können

Dieser Artikel bezieht sich nicht auf die Produktionsentwicklung, sondern auf die Programmierung. Ich bespreche dynamische Programmierung (DP) und wie man frühere Rechenerfahrungen effektiv nutzt. Ich hoffe, Sie finden es interessant.

Einführung in die dynamische Programmierung

Der Begriff „Dynamische Programmierung“ wurde erstmals in den 1950er Jahren von dem berühmten amerikanischen Mathematiker und einem der führenden Spezialisten für Computertechnologie, Richard Bellman, verwendet . Dynamic Programming (DP) ist eine Methode zur Lösung komplexer Aufgaben durch Zerlegung in kleinere Teilprobleme.

Die Art von Problemen, die DP lösen kann, muss zwei Kriterien erfüllen:

1. Optimaler Unterbau . Dynamische Programmierung bedeutet, dass die Lösung kleinerer Teilprobleme zur Lösung des ursprünglichen Teilproblems verwendet werden kann. Der optimale Unterbau ist das Hauptmerkmal des „Teile und herrsche“-Paradigmas.

Ein klassisches Implementierungsbeispiel ist der Merge-Sort-Algorithmus, bei dem wir das Problem rekursiv in die einfachsten Unterprobleme (Arrays der Größe 1) zerlegen und anschließend Berechnungen auf der Grundlage jedes einzelnen Problems durchführen. Die Ergebnisse werden zur Lösung der nächsten Schicht (größere Teilprobleme) verwendet, bis die erste Schicht erreicht ist.

2. Überlappende Teilprobleme . In der Informatik spricht man von überlappenden Teilproblemen eines Problems, wenn das Problem in Teilprobleme zerlegt werden kann, die mehrfach wiederverwendet werden können. Mit anderen Worten: Ausführen desselben Codes mit denselben Eingabedaten und denselben Ergebnissen. Ein klassisches Beispiel für dieses Problem ist die Berechnung eines N-ten Elements in einer Fibonacci-Folge, die wir uns im Folgenden ansehen werden.

Man könnte sagen, dass DP ein Sonderfall der Anwendung des Divide and Conquer-Paradigmas oder einer komplexeren Version davon ist. Das Muster eignet sich gut zur Lösung kombinatorischer Aufgaben, bei denen eine große Anzahl verschiedener Kombinationen berechnet wird, die N-Menge der Elemente jedoch häufig monoton und identisch ist.

Bei den Problemen der optimalen Unterstruktur und überlappenden Teilproblemen haben wir zahlreiche Wiederholungsberechnungen und -operationen, wenn wir einen Brute-Force-Ansatz anwenden. DP hilft uns, die Lösung zu optimieren und die Verdoppelung der Berechnungen zu vermeiden, indem es zwei Hauptansätze verwendet: Memoisierung und Tabellierung:

1. Die Memoisierung (Top-Down-Ansatz) wird durch Rekursion implementiert. Eine Aufgabe wird in kleinere Teilprobleme zerlegt, deren Ergebnisse in einen Speicher eingespeist und durch wiederholte Verwendung zur Lösung des ursprünglichen Problems zusammengefasst.

• Nachteile: Dieser Ansatz nutzt Stapelspeicher durch rekursive Methodenaufrufe
• Vorteile: Flexibilität gegenüber DP-Aufgaben.

2. Die Tabellierung (Bottom-up-Ansatz) wird mithilfe einer iterativen Methode implementiert. Teilprobleme vom kleinsten bis zum ersten werden nacheinander iterativ berechnet.

• Nachteile: eingeschränkter Anwendungsbereich. Dieser Ansatz erfordert ein anfängliches Verständnis der gesamten Abfolge der Teilprobleme. Bei manchen Problemen ist dies jedoch nicht machbar.
• Vorteile: effiziente Speichernutzung, da alles in einer einzigen Funktion ausgeführt wird.

Die Theorie mag langweilig und unverständlich klingen – schauen wir uns einige Beispiele an.

Problem: Fibonacci-Folge

Ein klassisches Beispiel für DP ist die Berechnung eines N-ten Elements in einer Fibonacci-Folge, wobei jedes Element die Summe der beiden vorhergehenden ist und das erste und zweite Element gleich 0 und 1 sind.

Bei der Hypothese konzentrieren wir uns zunächst auf die Art der optimalen Unterstruktur, denn um einen Wert zu berechnen, müssen wir den vorhergehenden finden. Um den vorhergehenden Wert zu berechnen, müssen wir den davor liegenden Wert finden und so weiter. Die Art sich überschneidender Teilaufgaben wird im folgenden Diagramm veranschaulicht.

Für diese Aufgabe betrachten wir drei Fälle:

1. Unkomplizierter Ansatz: Was sind die Nachteile?
2. Eine optimierte Lösung mit Memoisierung
3. Eine optimierte Lösung mittels Tabellierung

Unkomplizierter/Brute-Force-Ansatz

Das erste, was Ihnen vielleicht einfällt, ist, die Rekursion einzugeben, die beiden vorhergehenden Elemente zusammenzufassen und ihr Ergebnis anzugeben.

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

Auf dem Bildschirm unten sehen Sie einen Stapel von Funktionsaufrufen, um das fünfte Element in der Sequenz zu berechnen.

Beachten Sie, dass die Funktion fib(1) fünfmal und fib(2) dreimal aufgerufen wird. Funktionen mit einer Signatur und denselben Parametern werden wiederholt gestartet und führen dasselbe aus. Wenn die N-Zahl erhöht wird, wächst der Baum nicht linear, sondern exponentiell, was zu einer kolossalen Verdoppelung der Berechnungen führt.

Mathematische Analyse:

Zeitkomplexität: O(2^n),

Raumkomplexität: O(n) -> proportional zur maximalen Tiefe des rekursiven Baums, da dies die maximale Anzahl von Elementen ist, die im Stapel impliziter Funktionsaufrufe vorhanden sein können.

Ergebnis: Dieser Ansatz ist äußerst ineffizient. Beispielsweise sind 1.073.741.824 Operationen erforderlich, um das 30. Element zu berechnen.

Auswendiglernen (Top-Down-Ansatz)

Bei diesem Ansatz unterscheidet sich die Implementierung nicht wesentlich von der vorherigen „Brute-Force“-Lösung, mit Ausnahme der Speicherzuweisung. Lassen Sie es das Variablenmemo sein, in dem wir die Ergebnisse der Berechnungen jeder abgeschlossenen fib()-Funktion in unserem Stapel sammeln.

Es sollte beachtet werden, dass es ausreichend gewesen wäre, ein Array von Ganzzahlen zu haben und über den Index darauf zu verweisen, aber aus Gründen der konzeptionellen Klarheit wurde eine Hash-Map erstellt.

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

Konzentrieren wir uns noch einmal auf den Funktionsaufrufstapel:

• Die erste abgeschlossene Funktion, die das Ergebnis in das Memo schreibt, ist die hervorgehobene fib(2) . Es gibt die Kontrolle an das markierte fib(3) zurück.
• Das hervorgehobene fib(3) findet seinen Wert nach der Zusammenfassung der Ergebnisse der fib(2) und fib(1) -Aufrufe, trägt seine Lösung in das Memo ein und gibt die Kontrolle an fib(4) zurück.
• Wir haben das Stadium der Wiederverwendung früherer Erfahrungen erreicht – wenn die Kontrolle an fib(4) zurückgegeben wird, wartet der fib(2) -Aufruf darauf, dass er an die Reihe kommt. fib(2) wiederum verwendet, anstatt ( fib(1) + fib(0) ) aufzurufen, die gesamte fertige Lösung aus dem Memo und gibt sie sofort zurück.
• fib(4) wird berechnet und gibt die Kontrolle an fib(5) zurück, das nur noch fib(3) starten muss. In der letzten Analogie gibt fib(3) ohne Berechnungen sofort einen Wert aus dem Memo zurück.

Wir können eine Verringerung der Anzahl der Funktionsaufrufe und Berechnungen beobachten. Wenn N erhöht wird, wird es außerdem exponentiell weniger Reduzierungen geben.

Mathematische Analyse:

Zeitkomplexität: O(n)

Raumkomplexität: O(n)

Ergebnis: Es gibt einen deutlichen Unterschied in der asymptotischen Komplexität. Dieser Ansatz hat es im Vergleich zur primitiven Lösung auf eine zeitliche Linearität reduziert und den Speicher nicht erhöht.

Tabellierung (Bottom-up-Ansatz)

Wie oben erwähnt, beinhaltet dieser Ansatz eine iterative Berechnung von einem kleineren zu einem größeren Teilproblem. Im Fall von Fibonacci sind die kleinsten „Unterprobleme“ das erste und zweite Element der Folge, 0 bzw. 1.

Wir sind uns der Beziehung der Elemente zueinander bewusst, die in der Formel ausgedrückt wird: fib(n) = fib(n-1) + fib(n-2) . Da wir die vorhergehenden Elemente kennen, können wir das nächste, das übernächste usw. leicht berechnen.

Indem wir die uns bekannten Werte zusammenfassen, können wir das nächste Element finden. Wir führen diese Operation zyklisch durch, bis wir den gewünschten Wert gefunden haben.

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

Mathematische Analyse:

Zeitkomplexität: O(n)

Raumkomplexität: O(1)

Ergebnis: Dieser Ansatz ist hinsichtlich der Geschwindigkeit genauso effektiv wie das Auswendiglernen, verbraucht jedoch konstant viel Speicher.

Problem: Einzigartige Binärbäume

Schauen wir uns ein komplexeres Problem an: Wir müssen die Anzahl aller strukturell eindeutigen Binärbäume ermitteln, die aus N Knoten erstellt werden können.

Ein Binärbaum ist eine hierarchische Datenstruktur, in der jeder Knoten nicht mehr als zwei Nachkommen hat. In der Regel wird der erste als übergeordneter Knoten bezeichnet und hat zwei untergeordnete Knoten – den linken und den rechten untergeordneten Knoten.

Nehmen wir an, wir müssen eine Lösung für N = 3 finden. Es gibt 5 strukturell eindeutige Bäume für die drei Knoten. Wir können sie in unserem Kopf zählen, aber wenn das N erhöht wird, würden die Variationen immens eskalieren und es wäre unmöglich, sie in unserem Kopf zu visualisieren.

Diese Aufgabe könnte der Kombinatorik zugeschrieben werden. Lassen Sie uns herausfinden, welche Kombinationen gebildet werden können und wie wir ein Muster für ihre Bildung finden können.

1. Jeder Baum beginnt am obersten Knoten (Scheitelpunkt des Baums). Der Baum dehnt sich dann in die Tiefe aus.
2. Jeder Knoten ist der Anfang eines neuen untergeordneten Baums (Teilbaums), wie auf dem Bildschirm angezeigt. Der linke Teilbaum ist grün gefärbt, der rechte Teilbaum rot. Jeder hat seinen eigenen Scheitelpunkt.

Schauen wir uns ein Beispiel einer Aufgabe an, bei der auf konzeptioneller Ebene N = 6 ist. Wir nennen unsere Berechnungsfunktion numOfUniqueTrees(n: Int) .

In unserem Beispiel sind 6 Knoten angegeben, von denen einer nach dem zuvor erwähnten Prinzip den Scheitelpunkt des Baums bildet und die anderen 5 den Rest bilden.

Von nun an interagieren wir mit den verbleibenden Knoten. Dies kann auf verschiedene Arten erfolgen. Beispielsweise indem alle fünf Knoten verwendet werden, um den linken Teilbaum zu bilden, oder indem alle fünf Knoten an den rechten Teilbaum gesendet werden. Oder indem wir die Knoten in zwei Teile teilen – 2 links und 3 rechts (siehe Bildschirm unten), haben wir eine begrenzte Anzahl solcher Varianten.

Um das Ergebnis numOfUniqueTrees(6) zu erreichen, müssen wir alle Varianten zur Verteilung unserer Knoten berücksichtigen. Sie sind in der Tabelle aufgeführt:

Die Tabelle zeigt 6 verschiedene Verteilungen der Knoten. Wenn wir herausfinden, wie viele einzigartige Bäume für jede Verteilung generiert werden können, und diese zusammenzählen, erhalten wir unser Endergebnis.

Wie finde ich die Anzahl der zu verteilenden eindeutigen Bäume?

Wir haben zwei Parameter: Linke Knoten und Rechte Knoten (linke und rechte Spalte in der Tabelle).

Das Ergebnis ist gleich: numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) .

Warum? Auf der linken Seite werden wir X einzigartige Bäume haben, und für jeden können wir auf der rechten Seite Y einzigartige Variationen von Bäumen platzieren. Wir multiplizieren diese, um das Ergebnis zu erhalten.

Lassen Sie uns also Variationen für die erste Verteilung herausfinden (5 links, 0 rechts).

numOfUniqueTrees(5) * numOfUniqueTrees(0) , da wir rechts keine Knoten haben. Das Ergebnis ist numOfUniqueTrees(5) – die Anzahl der eindeutigen Teilbäume auf der linken Seite mit einer konstanten rechten Seite.

Berechnung von numOfUniqueTrees(5) .

Jetzt haben wir das kleinste Teilproblem. Wir werden damit genauso vorgehen wie mit dem größeren. In diesem Stadium ist das Merkmal der DP-Aufgaben klar – optimale Unterstruktur, rekursives Verhalten.

Ein Knoten (der grüne Knoten) wird an den Scheitelpunkt gesendet. Wir verteilen die verbleibenden (vier) Knoten analog zu früheren Erfahrungen (4:0), (3:1), (2:2), (1:3), (0:4).

Wir berechnen die erste Verteilung (4:0). Nach früherer Analogie ist es gleich numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) .

Berechnung von numOfUniqueTrees(4) . Wenn wir dem Scheitelpunkt einen Knoten zuweisen, bleiben noch 3 übrig.

Verteilungen (3:0), (2:1), (1:2), (0:3).

Für 2 Knoten gibt es nur zwei eindeutige Binärbäume, für 1 einen. Zuvor haben wir bereits erwähnt, dass es 5 Variationen einzigartiger Binärbäume für drei Knoten gibt.

Als Ergebnis sind die Verteilungen (3:0), (0:3) gleich 5, (2:1), (1:2) – 2. Wenn wir 5 + 2 + 2 + 5 zusammenfassen, erhalten wir 14 . numOfUniqueTrees(4) = 14.

Tragen wir das Ergebnis der Berechnung entsprechend der Memoisierungserfahrung in die Variable memo ein. Wann immer wir Variationen für vier Knoten finden müssen, berechnen wir diese nicht erneut, sondern verwenden frühere Erfahrungen wieder.

Kehren wir zur Berechnung (5:0) zurück, die der Summe der Verteilungen (4:0), (3:1), (2:2), (1:3), (0:4) entspricht. Wir wissen, dass (4:0) = 14. Wenden wir uns dem Memo zu: (3:1) = 5, (2:2) = 4 (2 Variationen links * 2 rechts), (1:3) = 5, (0:4) = 14. Wenn wir diese zusammenfassen, erhalten wir 42, numOfUniqueTrees(5) = 42.

Kehren wir zur Berechnung von numOfUniqueTrees(6) zurück, die der Summe der Verteilungen entspricht.

(5:0) = 42, (4:1) = 14, (3:2) =10 (5 links * 2 rechts), (2:3) = 10, (1:4) = 14, (0: 5) = 42. Wenn wir diese zusammenfassen, erhalten wir 132, numOfUniqueTrees(5) = 132 .

Aufgabe gelöst!

Ergebnis: Beachten wir die überlappenden Unterprobleme in der Lösung mit N = 6. In der einfachen Lösung würde numOfUniqueTrees(3) 18 Mal aufgerufen (Bildschirm unten). Mit zunehmendem N würde die Anzahl der Wiederholungen derselben Berechnung weitaus größer sein.

Ich möchte hervorheben, dass die Anzahl der eindeutigen Bäume für (5 links, 0 rechts) und (0 links, 5 rechts) gleich sein wird. Nur in einem Fall befinden sie sich links und im anderen Fall rechts. Dies funktioniert auch für (4 links, 1 rechts) und (1 links, 4 rechts).

Die Memoisierung als Ansatz der dynamischen Programmierung hat es uns ermöglicht, die Lösung für eine so komplexe Aufgabe zu optimieren.

Implementierung

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

Abschluss

In manchen Fällen kann die Lösung von Aufgaben mithilfe der dynamischen Programmierung eine enorme Zeitersparnis bringen und dazu führen, dass der Algorithmus mit maximaler Effizienz arbeitet.

Vielen Dank, dass Sie diesen Artikel bis zum Ende gelesen haben. Gerne beantworte ich Ihre Fragen.

Gepostet von Ayat Rakhishev