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,   . Dynamic Programming (DP) ist eine Methode zur Lösung komplexer Aufgaben durch Zerlegung in kleinere Teilprobleme.  verwendet  Die Art von Problemen, die DP lösen kann, muss zwei Kriterien erfüllen:    . 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. 1. Optimaler Unterbau  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.    . 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. 2. Überlappende Teilprobleme  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:    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. 1. Die Memoisierung (Top-Down-Ansatz)    Dieser Ansatz nutzt Stapelspeicher durch rekursive Methodenaufrufe Nachteile:    Flexibilität gegenüber DP-Aufgaben. Vorteile:    wird mithilfe einer iterativen Methode implementiert. Teilprobleme vom kleinsten bis zum ersten werden nacheinander iterativ berechnet. 2. Die Tabellierung (Bottom-up-Ansatz)    eingeschränkter Anwendungsbereich. Dieser Ansatz erfordert ein anfängliches Verständnis der gesamten Abfolge der Teilprobleme. Bei manchen Problemen ist dies jedoch nicht machbar. Nachteile:    effiziente Speichernutzung, da alles in einer einzigen Funktion ausgeführt wird. Vorteile:  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:  Unkomplizierter Ansatz: Was sind die Nachteile?  Eine optimierte Lösung mit Memoisierung  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   fünfmal und   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. fib(1) fib(2)   Mathematische Analyse:    O(2^n), Zeitkomplexitä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. Raumkomplexität:    Dieser Ansatz ist äußerst ineffizient. Beispielsweise sind 1.073.741.824 Operationen erforderlich, um das 30. Element zu berechnen. Ergebnis:  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   . Es gibt die Kontrolle an das markierte   zurück. fib(2) fib(3)  Das hervorgehobene   findet seinen Wert nach der Zusammenfassung der Ergebnisse der   und   -Aufrufe, trägt seine Lösung in das Memo ein und gibt die Kontrolle an   zurück. fib(3) fib(2) fib(1) fib(4)  Wir haben das Stadium der Wiederverwendung früherer Erfahrungen erreicht – wenn die Kontrolle an   zurückgegeben wird, wartet der   -Aufruf darauf, dass er an die Reihe kommt.   wiederum verwendet, anstatt (   ) aufzurufen, die gesamte fertige Lösung aus dem Memo und gibt sie sofort zurück. fib(4) fib(2) fib(2) fib(1) + fib(0)    wird berechnet und gibt die Kontrolle an   zurück, das nur noch   starten muss. In der letzten Analogie gibt   ohne Berechnungen sofort einen Wert aus dem Memo zurück. fib(4) fib(5) fib(3) fib(3)  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)    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. Ergebnis:  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:   . Da wir die vorhergehenden Elemente kennen, können wir das nächste, das übernächste usw. leicht berechnen. fib(n) = fib(n-1) + fib(n-2)  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)    Dieser Ansatz ist hinsichtlich der Geschwindigkeit genauso effektiv wie das Auswendiglernen, verbraucht jedoch konstant viel Speicher. Ergebnis:  Problem: Einzigartige Binärbäume  Schauen wir uns ein komplexeres   an: Wir müssen die Anzahl aller strukturell eindeutigen Binärbäume ermitteln, die aus N Knoten erstellt werden können. Problem  Ein   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. Binärbaum  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.  Jeder Baum beginnt am obersten Knoten (Scheitelpunkt des Baums). Der Baum dehnt sich dann in die Tiefe aus.  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   zu erreichen, müssen wir alle Varianten zur Verteilung unserer Knoten berücksichtigen. Sie sind in der Tabelle aufgeführt:  numOfUniqueTrees(6)  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).    , da wir rechts keine Knoten haben. Das Ergebnis ist   – die Anzahl der eindeutigen Teilbäume auf der linken Seite mit einer konstanten rechten Seite.  numOfUniqueTrees(5) * numOfUniqueTrees(0) numOfUniqueTrees(5)  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   . Wenn wir dem Scheitelpunkt einen Knoten zuweisen, bleiben noch 3 übrig. numOfUniqueTrees(4)  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 .   = 14. numOfUniqueTrees(4)  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,   = 42. numOfUniqueTrees(5)  Kehren wir zur Berechnung von   zurück, die der Summe der Verteilungen entspricht. numOfUniqueTrees(6)  (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   18 Mal aufgerufen (Bildschirm unten). Mit zunehmendem N würde die Anzahl der Wiederholungen derselben Berechnung weitaus größer sein.  numOfUniqueTrees(3)  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

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

inDrive.Tech

Dieses Audio ist in der Originalsprache der Geschichte produziert!

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

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

HackerNoon Decoded 2024: Celebrating Our Data Science Community!

HackerNoon Decoded 2024: Wir feiern unsere Produktmanagement-Community!

Meet Deepgram: HackerNoon Company of the Week

HackerNoon Decoded 2024: Wir feiern unsere Remote-Work-Community!

HackerNoon Decoded 2024: Celebrating Our Data Science Community!

HackerNoon Decoded 2024: Wir feiern unsere Produktmanagement-Community!

Meet Deepgram: HackerNoon Company of the Week

HackerNoon Decoded 2024: Wir feiern unsere Remote-Work-Community!

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps