Was ist dynamische Programmierung ?
Wie unterscheidet es sich von Rekursion, Memoisierung usw.?
Ich habe den Wikipedia-Artikel darüber gelesen , aber ich verstehe ihn immer noch nicht wirklich.
algorithm
dynamic-programming
smac89
quelle
quelle
Antworten:
Dynamische Programmierung ist, wenn Sie das Wissen der Vergangenheit nutzen, um die Lösung eines zukünftigen Problems zu vereinfachen.
Ein gutes Beispiel ist das Lösen der Fibonacci-Sequenz für n = 1.000.002.
Dies wird ein sehr langer Prozess sein, aber was ist, wenn ich Ihnen die Ergebnisse für n = 1.000.000 und n = 1.000.001 gebe? Plötzlich wurde das Problem leichter zu bewältigen.
Dynamische Programmierung wird häufig bei Zeichenfolgenproblemen verwendet, z. B. beim Problem der Zeichenfolgenbearbeitung. Sie lösen eine Teilmenge (n) des Problems und verwenden diese Informationen dann, um das schwierigere ursprüngliche Problem zu lösen.
Mit der dynamischen Programmierung speichern Sie Ihre Ergebnisse im Allgemeinen in einer Art Tabelle. Wenn Sie die Antwort auf ein Problem benötigen, verweisen Sie auf die Tabelle und prüfen, ob Sie bereits wissen, um was es sich handelt. Wenn nicht, verwenden Sie die Daten in Ihrer Tabelle, um sich einen Sprung in die Antwort zu geben.
Das Cormen-Algorithmus-Buch enthält ein großartiges Kapitel über dynamische Programmierung. UND es ist kostenlos bei Google Books! Schau es dir hier an.
quelle
Dynamische Programmierung ist eine Technik, mit der vermieden wird, dass in einem rekursiven Algorithmus das gleiche Teilproblem mehrfach berechnet wird.
Nehmen wir das einfache Beispiel der Fibonacci-Zahlen: Finden der n- ten Fibonacci-Zahl, definiert durch
F n = F n-1 + F n-2 und F 0 = 0, F 1 = 1
Rekursion
Der offensichtliche Weg, dies zu tun, ist rekursiv:
Dynamische Programmierung
Die Rekursion führt viele unnötige Berechnungen durch, da eine bestimmte Fibonacci-Zahl mehrmals berechnet wird. Eine einfache Möglichkeit, dies zu verbessern, besteht darin, die Ergebnisse zwischenzuspeichern:
Ein besserer Weg, dies zu tun, besteht darin, die Rekursion insgesamt zu beseitigen, indem die Ergebnisse in der richtigen Reihenfolge ausgewertet werden:
Wir können sogar konstanten Platz nutzen und nur die notwendigen Teilergebnisse auf dem Weg speichern:
Wie wende ich dynamische Programmierung an?
Die dynamische Programmierung funktioniert im Allgemeinen bei Problemen mit einer inhärenten Reihenfolge von links nach rechts, wie z. B. Zeichenfolgen, Bäume oder ganzzahlige Sequenzen. Wenn der naive rekursive Algorithmus nicht mehrmals dasselbe Teilproblem berechnet, hilft die dynamische Programmierung nicht weiter.
Ich habe eine Sammlung von Problemen erstellt, um die Logik besser zu verstehen: https://github.com/tristanguigue/dynamic-programing
quelle
if n in cache
wie im Beispiel von oben nach unten oder fehlt mir etwas?Memoization ist das Speichern von vorherigen Ergebnissen eines Funktionsaufrufs (eine echte Funktion gibt bei gleichen Eingaben immer dasselbe zurück). Es macht keinen Unterschied für die algorithmische Komplexität, bevor die Ergebnisse gespeichert werden.
Rekursion ist die Methode einer Funktion, die sich selbst aufruft, normalerweise mit einem kleineren Datensatz. Da die meisten rekursiven Funktionen in ähnliche iterative Funktionen konvertiert werden können, spielt dies auch für die algorithmische Komplexität keine Rolle.
Dynamische Programmierung ist der Prozess, bei dem einfach zu lösende Teilprobleme gelöst und daraus die Antwort erstellt werden. Die meisten DP-Algorithmen befinden sich in der Laufzeit zwischen einem Greedy-Algorithmus (falls vorhanden) und einem exponentiellen Algorithmus (alle Möglichkeiten auflisten und den besten finden).
quelle
Es ist eine Optimierung Ihres Algorithmus, die die Laufzeit verkürzt.
Während ein Greedy-Algorithmus normalerweise als naiv bezeichnet wird , weil er möglicherweise mehrmals über denselben Datensatz ausgeführt wird, vermeidet die dynamische Programmierung diese Gefahr durch ein tieferes Verständnis der Teilergebnisse, die gespeichert werden müssen, um die endgültige Lösung zu erstellen.
Ein einfaches Beispiel ist das Durchlaufen eines Baums oder einer Grafik nur durch die Knoten, die zur Lösung beitragen würden, oder das Einfügen der bisher gefundenen Lösungen in eine Tabelle, damit Sie nicht immer wieder dieselben Knoten durchlaufen müssen.
Hier ist ein Beispiel für ein Problem, das für die dynamische Programmierung geeignet ist, von UVAs Online-Richter: Edit Steps Ladder.
Ich werde kurz auf den wichtigen Teil der Analyse dieses Problems eingehen, der aus dem Buch Programmierherausforderungen stammt. Ich schlage vor, dass Sie es sich ansehen.
Eine ganz besondere Analyse dessen, was erforderlich ist, um die optimalsten Teilergebnisse zu erzielen, macht die Lösung zu einer "dynamischen".
Hier ist eine alternative, vollständige Lösung für dasselbe Problem. Es ist auch eine "dynamische", obwohl seine Ausführung anders ist. Ich schlage vor, dass Sie überprüfen, wie effizient die Lösung ist, indem Sie sie dem Online-Richter von UVA vorlegen. Ich finde es erstaunlich, wie effizient ein so schweres Problem angegangen wurde.
quelle
Die Schlüsselbits der dynamischen Programmierung sind "überlappende Unterprobleme" und "optimale Unterstruktur". Diese Eigenschaften eines Problems bedeuten, dass eine optimale Lösung aus den optimalen Lösungen für seine Unterprobleme besteht. Beispielsweise weisen Probleme mit kürzesten Wegen eine optimale Unterstruktur auf. Der kürzeste Weg von A nach C ist der kürzeste Weg von A zu einem Knoten B, gefolgt vom kürzesten Weg von diesem Knoten B nach C.
Um ein Problem mit dem kürzesten Weg zu lösen, gehen Sie genauer vor:
Da wir von unten nach oben arbeiten, haben wir bereits Lösungen für die Unterprobleme, wenn es darum geht, sie zu verwenden, indem wir sie auswendig lernen.
Denken Sie daran, dass dynamische Programmierprobleme sowohl überlappende Unterprobleme als auch eine optimale Unterstruktur aufweisen müssen. Das Erzeugen der Fibonacci-Sequenz ist kein dynamisches Programmierproblem. Es verwendet Memoization, weil es überlappende Unterprobleme hat, aber keine optimale Unterstruktur (weil es kein Optimierungsproblem gibt).
quelle
Dynamische Programmierung
Definition
Dynamische Programmierung (DP) ist eine allgemeine Algorithmus-Entwurfstechnik zum Lösen von Problemen mit überlappenden Unterproblemen. Diese Technik wurde in den 1950er Jahren vom amerikanischen Mathematiker „Richard Bellman“ erfunden.
Schlüsselidee
Die Schlüsselidee besteht darin, Antworten auf überlappende kleinere Unterprobleme zu speichern, um eine Neuberechnung zu vermeiden.
Dynamische Programmiereigenschaften
quelle
Ich bin auch sehr neu in der dynamischen Programmierung (ein leistungsfähiger Algorithmus für bestimmte Arten von Problemen).
In den einfachsten Worten denken Sie einfach an dynamische Programmierung als rekursiven Ansatz unter Verwendung der Vorkenntnisse
Vorwissen ist hier am wichtigsten. Behalten Sie die Lösung der bereits vorhandenen Unterprobleme im Auge.
Betrachten Sie dieses grundlegendste Beispiel für dp aus Wikipedia
Finden der Fibonacci-Sequenz
Lassen Sie uns den Funktionsaufruf mit say n = 5 abbrechen
Insbesondere wurde fib (2) dreimal von Grund auf neu berechnet. In größeren Beispielen werden viel mehr Werte von fib oder Unterproblemen neu berechnet, was zu einem exponentiellen Zeitalgorithmus führt.
Versuchen wir es jetzt, indem wir den Wert, den wir bereits in einer Datenstruktur gefunden haben, beispielsweise eine Karte, speichern
Hier speichern wir die Lösung von Unterproblemen in der Karte, falls wir sie noch nicht haben. Diese bereits berechnete Technik zum Speichern von Werten wird als Memoization bezeichnet.
Versuchen Sie schließlich für ein Problem zunächst, die Zustände zu finden (mögliche Unterprobleme und überlegen Sie sich den besseren Rekursionsansatz, damit Sie die Lösung des vorherigen Unterproblems in weitere verwenden können).
quelle
Dynamische Programmierung ist eine Technik zum Lösen von Problemen mit überlappenden Unterproblemen. Ein dynamischer Programmieralgorithmus löst jedes Unterproblem nur einmal und speichert dann seine Antwort in einer Tabelle (Array). Vermeiden Sie die Arbeit, die Antwort jedes Mal neu zu berechnen, wenn das Unterproblem auftritt. Die Grundidee der dynamischen Programmierung lautet: Vermeiden Sie es, dasselbe Material zweimal zu berechnen, indem Sie normalerweise eine Tabelle mit bekannten Ergebnissen von Unterproblemen führen.
Die sieben Schritte bei der Entwicklung eines dynamischen Programmieralgorithmus sind wie folgt:
quelle
6. Convert the memoized recursive algorithm into iterative algorithm
ein obligatorischer Schritt? Dies würde bedeuten, dass seine endgültige Form nicht rekursiv ist?Kurz gesagt, der Unterschied zwischen Rekursionsmemoisierung und dynamischer Programmierung
Dynamische Programmierung verwendet, wie der Name schon sagt, den zuvor berechneten Wert, um die nächste neue Lösung dynamisch zu erstellen
Anwendung der dynamischen Programmierung: Wenn Ihre Lösung auf einer optimalen Unterstruktur und einem überlappenden Unterproblem basiert, ist in diesem Fall die Verwendung des zuvor berechneten Werts hilfreich, damit Sie ihn nicht neu berechnen müssen. Es ist ein Bottom-up-Ansatz. Angenommen, Sie müssen fib (n) berechnen. In diesem Fall müssen Sie nur den zuvor berechneten Wert von fib (n-1) und fib (n-2) addieren.
Rekursion: Unterteilen Sie Ihr Problem grundsätzlich in kleinere Teile, um es problemlos zu lösen. Beachten Sie jedoch, dass eine Neuberechnung nicht vermieden wird, wenn derselbe Wert zuvor in einem anderen Rekursionsaufruf berechnet wurde.
Memoisierung: Grundsätzlich wird das Speichern des alten berechneten Rekursionswerts in der Tabelle als Memoisierung bezeichnet, wodurch eine Neuberechnung vermieden wird, wenn er bereits durch einen vorherigen Aufruf berechnet wurde, sodass jeder Wert einmal berechnet wird. Bevor wir berechnen, prüfen wir, ob dieser Wert bereits berechnet wurde oder nicht, wenn er bereits berechnet wurde. Dann geben wir ihn aus der Tabelle zurück, anstatt ihn neu zu berechnen. Es ist auch ein Top-Down-Ansatz
quelle
Hier ist ein einfaches Python - Code Beispiel
Recursive
,Top-down
,Bottom-up
Ansatz für Fibonacci - Reihe:Rekursiv: O (2 n )
Von oben nach unten: O (n) Effizient für größere Eingaben
Bottom-up: O (n) Zur Vereinfachung und für kleine Eingabegrößen
quelle