Der Bottom-up- Ansatz (zur dynamischen Programmierung) besteht darin, zuerst die "kleineren" Teilprobleme zu betrachten und dann die größeren Teilprobleme unter Verwendung der Lösung für die kleineren Probleme zu lösen.
Das Top-Down besteht darin, das Problem auf "natürliche Weise" zu lösen und zu überprüfen, ob Sie die Lösung für das Teilproblem zuvor berechnet haben.
Ich bin ein wenig verwirrt. Was ist der Unterschied zwischen diesen beiden?
Antworten:
Rekapitulieren
Bei der dynamischen Programmierung geht es darum, Ihre Berechnungen so zu ordnen, dass Doppelarbeit nicht neu berechnet wird. Sie haben ein Hauptproblem (die Wurzel Ihres Baums von Teilproblemen) und Unterprobleme (Teilbäume). Die Teilprobleme wiederholen sich typischerweise und überlappen sich .
Betrachten Sie zum Beispiel Ihr Lieblingsbeispiel für Fibonnaci. Dies ist der vollständige Baum der Teilprobleme, wenn wir einen naiven rekursiven Aufruf durchgeführt haben:
(Bei einigen anderen seltenen Problemen kann dieser Baum in einigen Zweigen unendlich sein, was eine Nichtbeendigung darstellt, und daher kann die Unterseite des Baums unendlich groß sein. Bei einigen Problemen wissen Sie möglicherweise nicht, wie der vollständige Baum vor Ihnen aussieht Daher benötigen Sie möglicherweise eine Strategie / einen Algorithmus, um zu entscheiden, welche Teilprobleme aufgedeckt werden sollen.)
Auswendiglernen, Tabellieren
Es gibt mindestens zwei Haupttechniken der dynamischen Programmierung, die sich nicht gegenseitig ausschließen:
Auswendiglernen - Dies ist ein Laissez-Faire-Ansatz: Sie gehen davon aus, dass Sie bereits alle Teilprobleme berechnet haben und keine Ahnung haben, wie die optimale Bewertungsreihenfolge lautet. In der Regel führen Sie einen rekursiven Aufruf (oder ein iteratives Äquivalent) von der Wurzel aus aus und hoffen entweder, dass Sie der optimalen Bewertungsreihenfolge nahe kommen, oder Sie erhalten einen Beweis dafür, dass Sie dabei helfen, die optimale Bewertungsreihenfolge zu erreichen. Sie würde sicherstellen , dass der rekursive Aufruf neu berechnet nie ein Teilproblem , weil Sie zwischenspeichern , die Ergebnisse und damit doppelte Unterbäume sind nicht neu berechnet.
fib(100)
, würden Sie dies einfach aufrufen, und es würde aufrufenfib(100)=fib(99)+fib(98)
, was aufrufen würdefib(99)=fib(98)+fib(97)
, ... etc ..., was aufrufen würdefib(2)=fib(1)+fib(0)=1+0=1
. Dann würde es sich endgültig auflösenfib(3)=fib(2)+fib(1)
, aber es muss nicht neu berechnet werdenfib(2)
, da wir es zwischengespeichert haben.Tabellierung - Sie können sich dynamische Programmierung auch als einen "Tabellenfüll" -Algorithmus vorstellen (obwohl diese 'Tabelle' normalerweise mehrdimensional ist, kann sie in sehr seltenen Fällen eine nichteuklidische Geometrie aufweisen *). Dies ist wie das Auswendiglernen, jedoch aktiver und umfasst einen zusätzlichen Schritt: Sie müssen im Voraus die genaue Reihenfolge auswählen, in der Sie Ihre Berechnungen durchführen. Dies sollte nicht bedeuten, dass die Reihenfolge statisch sein muss, sondern dass Sie viel flexibler sind als das Auswendiglernen.
fib(2)
,fib(3)
,fib(4)
... Cachen jeden Wert , so dass Sie die nächsten sind leicht mehr berechnen kann. Sie können sich das auch als Ausfüllen einer Tabelle vorstellen (eine andere Form des Caching).(An es ist allgemeinsten, in einem „dynamischen Programmierung“ Paradigma, würde ich sagen , dass der Programmierer den ganzen Baum hält, dannschreibt einen Algorithmus, der eine Strategie zur Bewertung von Teilproblemen implementiert, mit der die gewünschten Eigenschaften optimiert werden können (normalerweise eine Kombination aus Zeitkomplexität und Raumkomplexität). Ihre Strategie muss irgendwo mit einem bestimmten Teilproblem beginnen und kann sich möglicherweise basierend auf den Ergebnissen dieser Bewertungen anpassen. Im allgemeinen Sinne der "dynamischen Programmierung" könnten Sie versuchen, diese Teilprobleme zwischenzuspeichern, und generell versuchen, ein erneutes Aufrufen von Teilproblemen zu vermeiden, wobei eine subtile Unterscheidung möglicherweise bei Diagrammen in verschiedenen Datenstrukturen der Fall ist. Sehr oft sind diese Datenstrukturen im Kern wie Arrays oder Tabellen. Lösungen für Teilprobleme können weggeworfen werden, wenn wir sie nicht mehr brauchen.)
[Zuvor gab diese Antwort eine Erklärung zur Top-Down- und Bottom-Up-Terminologie ab. Es gibt eindeutig zwei Hauptansätze, die als Memoisierung und Tabellierung bezeichnet werden und möglicherweise mit diesen Begriffen in Konflikt stehen (wenn auch nicht vollständig). Der allgemeine Begriff, den die meisten Leute verwenden, ist immer noch "Dynamische Programmierung" und einige Leute sagen "Memoization", um sich auf diesen bestimmten Subtyp von "Dynamic Programming" zu beziehen. Diese Antwort lehnt es ab zu sagen, was von oben nach unten und von unten nach oben ist, bis die Community in wissenschaftlichen Arbeiten die richtigen Referenzen finden kann. Letztendlich ist es wichtig, die Unterscheidung und nicht die Terminologie zu verstehen.]
Vor-und Nachteile
Einfache Codierung
Das Auswendiglernen ist sehr einfach zu codieren (Sie können im Allgemeinen * eine "Memoizer" -Anmerkung oder eine Wrapper-Funktion schreiben, die dies automatisch für Sie erledigt) und sollte Ihre erste Vorgehensweise sein. Der Nachteil der Tabellierung ist, dass Sie eine Bestellung erstellen müssen.
* (Dies ist eigentlich nur einfach, wenn Sie die Funktion selbst schreiben und / oder in einer unreinen / nicht funktionierenden Programmiersprache codieren. Wenn beispielsweise jemand bereits eine vorkompilierte
fib
Funktion geschrieben hat, führt dies notwendigerweise rekursive Aufrufe an sich selbst aus Sie können die Funktion nicht auf magische Weise auswendig lernen, ohne sicherzustellen, dass diese rekursiven Aufrufe Ihre neue gespeicherte Funktion aufrufen (und nicht die ursprüngliche nicht gespeicherte Funktion).Rekursivität
Beachten Sie, dass sowohl von oben nach unten als auch von unten nach oben durch Rekursion oder iteratives Füllen von Tabellen implementiert werden kann, obwohl dies möglicherweise nicht natürlich ist.
Praktische Bedenken
Wenn der Baum beim Auswendiglernen sehr tief ist (z. B.
fib(10^6)
), wird Ihnen der Stapelspeicherplatz ausgehen, da jede verzögerte Berechnung auf den Stapel gelegt werden muss und Sie 10 ^ 6 davon haben.Optimalität
Beide Ansätze sind möglicherweise nicht zeitoptimal, wenn die Reihenfolge, in der Sie Teilprobleme besuchen (oder versuchen), nicht optimal ist, insbesondere wenn es mehr als eine Möglichkeit gibt, ein Teilproblem zu berechnen (normalerweise würde das Caching dies beheben, aber es ist theoretisch möglich, dass das Caching dies tut nicht in einigen exotischen Fällen). Das Auswendiglernen erhöht normalerweise Ihre Zeitkomplexität zu Ihrer Raumkomplexität (z. B. haben Sie bei der Tabellierung mehr Freiheit, Berechnungen wegzuwerfen, z. B. bei der Tabellierung mit Fib können Sie O (1) -Raum verwenden, bei der Memoisierung bei Fib wird jedoch O (N) verwendet. Stapelplatz).
Erweiterte Optimierungen
Wenn Sie auch extrem komplizierte Probleme haben, haben Sie möglicherweise keine andere Wahl, als eine Tabellierung durchzuführen (oder zumindest eine aktivere Rolle bei der Steuerung der Memoisierung zu übernehmen, wo Sie sie haben möchten). Auch wenn Sie sich in einer Situation befinden, in der die Optimierung absolut kritisch ist und Sie optimieren müssen, können Sie mithilfe der Tabellierung Optimierungen vornehmen, die Sie sonst durch Memoisierung nicht auf vernünftige Weise durchführen würden. Meiner bescheidenen Meinung nach taucht in der normalen Softwareentwicklung keiner dieser beiden Fälle jemals auf, daher würde ich nur Memoization ("eine Funktion, die ihre Antworten zwischenspeichert") verwenden, es sei denn, etwas (wie z. B. Stapelspeicher) macht eine Tabellierung erforderlich Um ein Ausblasen des Stapels zu vermeiden, können Sie 1) die Stapelgrößenbeschränkung in Sprachen erhöhen, die dies zulassen, oder 2) einen konstanten Faktor zusätzlicher Arbeit für die Virtualisierung Ihres Stapels (ick) aufwenden,
Kompliziertere Beispiele
Hier listen wir Beispiele von besonderem Interesse auf, die nicht nur allgemeine DP-Probleme sind, sondern interessanterweise Memoisierung und Tabellierung unterscheiden. Beispielsweise kann eine Formulierung viel einfacher sein als die andere, oder es kann eine Optimierung geben, die grundsätzlich eine Tabellierung erfordert:
quelle
python memoization decorator
. In einigen Sprachen können Sie ein Makro oder einen Code schreiben, der das Memoisierungsmuster kapselt. Das Memoisierungsmuster ist nichts anderes als "anstatt die Funktion aufzurufen, suchen Sie den Wert aus einem Cache (wenn der Wert nicht vorhanden ist, berechnen Sie ihn und fügen Sie ihn zuerst dem Cache hinzu)".fib(513)
. Die überladene Terminologie, die ich fühle, steht hier im Weg. 1) Sie können nicht mehr benötigte Teilprobleme jederzeit wegwerfen. 2) Sie können immer vermeiden, Teilprobleme zu berechnen, die Sie nicht benötigen. 3) 1 und 2 sind möglicherweise ohne eine explizite Datenstruktur zum Speichern von Teilproblemen viel schwieriger zu codieren, ODER schwieriger, wenn der Kontrollfluss zwischen Funktionsaufrufen wechseln muss (möglicherweise benötigen Sie Status oder Fortsetzungen).DP von oben nach unten und von unten nach oben sind zwei verschiedene Möglichkeiten, um dieselben Probleme zu lösen. Betrachten Sie eine gespeicherte (von oben nach unten) oder eine dynamische (von unten nach oben) Programmierlösung zur Berechnung von Fibonacci-Zahlen.
Ich persönlich finde das Auswendiglernen viel natürlicher. Sie können eine rekursive Funktion nehmen und sie durch einen mechanischen Prozess auswendig lernen (zuerst die Antwort im Cache suchen und wenn möglich zurückgeben, andernfalls rekursiv berechnen und dann vor der Rückkehr die Berechnung für die zukünftige Verwendung im Cache speichern), während Sie Bottom-up ausführen Für die dynamische Programmierung müssen Sie eine Reihenfolge codieren, in der Lösungen berechnet werden, sodass vor dem kleineren Problem, von dem es abhängt, kein "großes Problem" berechnet wird.
quelle
Ein wesentliches Merkmal der dynamischen Programmierung ist das Vorhandensein überlappender Teilprobleme . Das heißt, das Problem, das Sie zu lösen versuchen, kann in Teilprobleme unterteilt werden, und viele dieser Teilprobleme teilen Teilprobleme. Es ist wie "Teilen und Erobern", aber am Ende macht man viele, viele Male dasselbe. Ein Beispiel, das ich seit 2003 verwendet habe, um diese Dinge zu lehren oder zu erklären: Sie können Fibonacci-Zahlen rekursiv berechnen .
Verwenden Sie Ihre Lieblingssprache und versuchen Sie, sie auszuführen
fib(50)
. Es wird sehr, sehr lange dauern. Etwa so viel Zeit wie sichfib(50)
selbst! Es wird jedoch viel unnötige Arbeit geleistet.fib(50)
wird aufrufenfib(49)
undfib(48)
, aber dann werden beide aufrufenfib(47)
, obwohl der Wert der gleiche ist. Tatsächlichfib(47)
wird es dreimal berechnet: durch einen direkten Anruf vonfib(49)
, durch einen direkten Anruf vonfib(48)
und auch durch einen direkten Anruf von einem anderenfib(48)
, der durch die Berechnung vonfib(49)
... hervorgerufen wurde. Sie sehen, wir haben überlappende Teilprobleme .Tolle Neuigkeiten: Es ist nicht erforderlich, den gleichen Wert mehrmals zu berechnen. Wenn Sie es einmal berechnet haben, speichern Sie das Ergebnis im Cache und verwenden Sie das nächste Mal den zwischengespeicherten Wert! Dies ist die Essenz der dynamischen Programmierung. Sie können es "von oben nach unten", "Memoisierung" oder was auch immer Sie wollen nennen. Dieser Ansatz ist sehr intuitiv und sehr einfach zu implementieren. Schreiben Sie einfach zuerst eine rekursive Lösung, testen Sie sie in kleinen Tests, fügen Sie Memoization (Caching bereits berechneter Werte) hinzu und --- Bingo! --- du bist fertig.
Normalerweise können Sie auch ein äquivalentes iteratives Programm schreiben, das ohne Rekursion von unten nach oben funktioniert. In diesem Fall wäre dies der natürlichere Ansatz: Schleife von 1 bis 50, wobei alle Fibonacci-Zahlen berechnet werden.
In jedem interessanten Szenario ist die Bottom-up-Lösung normalerweise schwieriger zu verstehen. Sobald Sie es jedoch verstanden haben, erhalten Sie normalerweise ein viel klareres Gesamtbild der Funktionsweise des Algorithmus. In der Praxis empfehle ich, bei der Lösung nicht trivialer Probleme zuerst den Top-Down-Ansatz zu schreiben und ihn an kleinen Beispielen zu testen. Schreiben Sie dann die Bottom-up-Lösung und vergleichen Sie die beiden, um sicherzustellen, dass Sie dasselbe erhalten. Vergleichen Sie die beiden Lösungen im Idealfall automatisch. Schreiben Sie eine kleine Routine , die viele Tests erzeugen würde, im Idealfall - allekleine Tests bis zu einer bestimmten Größe --- und bestätigen, dass beide Lösungen das gleiche Ergebnis liefern. Verwenden Sie danach die Bottom-Up-Lösung in der Produktion, behalten Sie jedoch den auskommentierten Top-Bottom-Code bei. Dies erleichtert anderen Entwicklern das Verständnis dafür, was Sie tun: Bottom-up-Code kann ziemlich unverständlich sein, selbst wenn Sie ihn geschrieben haben und selbst wenn Sie genau wissen, was Sie tun.
In vielen Anwendungen ist der Bottom-up-Ansatz aufgrund des Overheads rekursiver Aufrufe etwas schneller. Ein Stapelüberlauf kann auch bei bestimmten Problemen ein Problem sein. Beachten Sie, dass dies sehr stark von den Eingabedaten abhängen kann. In einigen Fällen können Sie möglicherweise keinen Test schreiben, der einen Stapelüberlauf verursacht, wenn Sie die dynamische Programmierung nicht gut genug verstehen, aber eines Tages kann dies dennoch passieren.
Nun gibt es Probleme, bei denen der Top-Down-Ansatz die einzig mögliche Lösung ist, da der Problemraum so groß ist, dass nicht alle Teilprobleme gelöst werden können. Das "Caching" funktioniert jedoch immer noch in angemessener Zeit, da für Ihre Eingabe nur ein Bruchteil der zu lösenden Teilprobleme benötigt wird. Es ist jedoch zu schwierig, explizit zu definieren, welche Teilprobleme Sie lösen müssen, und daher einen Bottom zu schreiben. Lösung. Andererseits gibt es Situationen, in denen Sie wissen, dass Sie alle Teilprobleme lösen müssen. In diesem Fall fahren Sie fort und verwenden Bottom-Up.
Ich persönlich würde Top-Bottom für die Absatzoptimierung verwenden, auch bekannt als das Problem der Word-Wrap-Optimierung (schauen Sie sich die Knuth-Plass-Algorithmen für Zeilenumbrüche an; zumindest TeX verwendet sie, und einige Software von Adobe Systems verwendet einen ähnlichen Ansatz). Ich würde Bottom-up für die schnelle Fourier-Transformation verwenden .
quelle
Nehmen wir als Beispiel die Fibonacci-Serie
Ein anderer Weg, um es auszudrücken,
Bei den ersten fünf Fibonacci-Zahlen
Schauen wir uns nun als Beispiel den rekursiven Algorithmus der Fibonacci-Reihe an
Nun, wenn wir dieses Programm mit folgenden Befehlen ausführen
Wenn wir uns den Algorithmus genau ansehen, sind zur Erzeugung der fünften Zahl die dritte und die vierte Zahl erforderlich. Meine Rekursion beginnt also tatsächlich von oben (5) und geht dann bis zu den unteren / unteren Zahlen. Dieser Ansatz ist eigentlich ein Top-Down-Ansatz.
Um zu vermeiden, dass dieselbe Berechnung mehrmals durchgeführt wird, verwenden wir dynamische Programmiertechniken. Wir speichern zuvor berechnete Werte und verwenden sie wieder. Diese Technik wird Memoisierung genannt. Dynamische Programmierung bietet mehr als Memoisierung, die nicht zur Erörterung des aktuellen Problems erforderlich ist.
Von oben nach unten
Schreiben wir unseren ursprünglichen Algorithmus neu und fügen gespeicherte Techniken hinzu.
Und wir führen diese Methode wie folgt aus
Diese Lösung ist immer noch von oben nach unten, da der Algorithmus vom oberen Wert ausgeht und bei jedem Schritt nach unten geht, um unseren höchsten Wert zu erhalten.
Prost
Aber die Frage ist, können wir von unten beginnen, wie von der ersten Fibonacci-Zahl, und dann unseren Weg nach oben gehen. Schreiben wir es mit diesen Techniken um.
Wenn wir uns diesen Algorithmus ansehen, beginnt er tatsächlich mit niedrigeren Werten und geht dann nach oben. Wenn ich die 5. Fibonacci-Zahl brauche, berechne ich tatsächlich die 1., dann die 2. und 3. bis zur 5. Zahl. Diese Techniken werden eigentlich Bottom-up-Techniken genannt.
Die letzten beiden Algorithmen erfüllen die Anforderungen an die dynamische Programmierung. Aber einer ist von oben nach unten und ein anderer von unten nach oben. Beide Algorithmen haben eine ähnliche räumliche und zeitliche Komplexität.
quelle
Dynamische Programmierung wird oft als Memoization bezeichnet!
1.Memoisierung ist die Top-Down-Technik (lösen Sie das gegebene Problem, indem Sie es auflösen), und dynamische Programmierung ist eine Bottom-up-Technik (beginnen Sie mit der Lösung vom trivialen Teilproblem bis zum gegebenen Problem).
2.DP findet die Lösung ausgehend von den Basisfällen und arbeitet sich nach oben vor. DP löst alle Unterprobleme, weil es von unten nach oben funktioniert
DP hat das Potenzial, Brute-Force-Lösungen mit Exponentialzeit in Algorithmen mit Polynomzeit umzuwandeln.
DP kann viel effizienter sein, weil es iterativ ist
Um es einfacher zu machen, verwendet Memoization den Top-Down-Ansatz, um das Problem zu lösen, dh es beginnt mit dem Kernproblem (Hauptproblem), unterteilt es dann in Unterprobleme und löst diese Unterprobleme auf ähnliche Weise. Bei diesem Ansatz kann dasselbe Unterproblem mehrmals auftreten und mehr CPU-Zyklus verbrauchen, wodurch die Zeitkomplexität erhöht wird. Während bei der dynamischen Programmierung dasselbe Unterproblem nicht mehrmals gelöst wird, wird das vorherige Ergebnis zur Optimierung der Lösung verwendet.
quelle
Wenn Sie einfach sagen, dass der Top-Down-Ansatz die Rekursion verwendet, um Sub-Probleme immer wieder aufzurufen, verwenden Sie
als Bottom-Up-Ansatz die Single, ohne einen anzurufen, und daher ist sie effizienter.
quelle
Im Folgenden finden Sie die DP-basierte Lösung für das Problem "Entfernung bearbeiten" von oben nach unten. Ich hoffe, es hilft auch beim Verständnis der Welt der dynamischen Programmierung:
Sie können an die rekursive Implementierung bei Ihnen zu Hause denken. Es ist ziemlich gut und herausfordernd, wenn Sie so etwas noch nicht gelöst haben.
quelle
Top-Down : Verfolgen Sie den berechneten Wert bis jetzt und geben Sie das Ergebnis zurück, wenn die Grundbedingung erfüllt ist.
Bottom-Up : Das aktuelle Ergebnis hängt vom Ergebnis des Unterproblems ab.
quelle