Was ist der Unterschied zwischen Memoisierung und dynamischer Programmierung?

Question

Was ist der Unterschied zwischen Memoisierung und dynamischer Programmierung? Ich denke, dass die dynamische Programmierung eine Untermenge der Memoisierung ist. Ist das richtig?

Answer 1

Einschlägiger Artikel auf Programming.Guide: Dynamische Programmierung vs. Memoisierung vs. Tabellierung

---

Was ist der Unterschied zwischen Memoisierung und dynamischer Programmierung?

Memoisierung ist ein Begriff, der eine Optimierungstechnik beschreibt, bei der Sie zuvor berechnete Ergebnisse zwischenspeichern und das zwischengespeicherte Ergebnis zurückgeben, wenn die gleiche Berechnung erneut erforderlich ist.

Dynamische Programmierung ist eine Technik zur iterativen Lösung von rekursiven Problemen, die anwendbar ist, wenn sich die Berechnungen der Teilprobleme überschneiden.

Die dynamische Programmierung ist typischerweise mit Hilfe der Tabellierung implementiert, kann aber auch mit Hilfe der Memoisierung implementiert werden. Wie Sie sehen, ist also keines von beiden eine "Teilmenge" des anderen.

---

Eine sinnvolle Folgefrage ist: Was ist der Unterschied zwischen Tabellierung (der typischen dynamischen Programmiertechnik) und Memoisierung?

Wenn Sie ein Problem der dynamischen Programmierung mit Hilfe der Tabellierung lösen, lösen Sie das Problem " von unten nach oben ", d.h. durch die Lösung aller zusammenhängenden Teilprobleme zuerst, typischerweise durch das Ausfüllen eines n -dimensionale Tabelle. Auf der Grundlage der Ergebnisse in der Tabelle wird dann die Lösung des "oberen" / ursprünglichen Problems berechnet.

Wenn Sie das Problem mit Hilfe der Memoisierung lösen, tun Sie dies, indem Sie eine Karte der bereits gelösten Teilprobleme pflegen. Sie tun es " von oben nach unten " in dem Sinne, dass man zuerst das "obere" Problem löst (das normalerweise nach unten rekursiert, um die Unterprobleme zu lösen).

Eine gute Folie aus ici (der Link ist jetzt tot, das Dia ist aber noch gut):

• Wenn alle Teilprobleme mindestens einmal gelöst werden müssen, ist ein dynamischer Bottom-up-Programmieralgorithmus in der Regel besser als ein memoisierter Top-down-Algorithmus.
  • Kein Overhead für Rekursion und weniger Overhead für Tabellenpflege
  • Es gibt einige Probleme, bei denen das regelmäßige Muster der Tabellenzugriffe im dynamischen Programmierungsalgorithmus ausgenutzt werden kann, um den Zeit- oder Platzbedarf noch weiter zu reduzieren
• Wenn einige Teilprobleme im Teilproblemraum überhaupt nicht gelöst werden müssen, hat die memoisierte Lösung den Vorteil, dass nur die Teilprobleme gelöst werden, die unbedingt erforderlich sind

Zusätzliche Ressourcen:

• Wikipedia: Memoisierung , Dynamische Programmierung
• Verwandte SO Q/A: Memoisierung oder Tabellierung bei der dynamischen Programmierung

Answer 2

Dynamische Programmierung ist ein algorithmisches Paradigma komplexes Problem löst, indem es in Teilprobleme zerlegt wird und die Ergebnisse von Teilproblemen speichert, um zu vermeiden, dass dieselben Ergebnisse erneut berechnet werden müssen.

http://www.geeksforgeeks.org/dynamic-programming-set-1/

Die Memoisierung ist eine einfache Methode, um bereits gelöste Lösungen zu verfolgen (oft als Hash-Schlüssel-Wert-Paar implementiert, im Gegensatz zur Tabellierung, die oft auf Arrays basiert), so dass sie nicht neu berechnet werden, wenn sie wieder auftauchen. Sie kann sowohl in Bottom-up- als auch in Top-down-Methoden verwendet werden.

Siehe diese Diskussion zu Memoisierung vs. Tabellierung.

Dynamische Programmierung ist also eine Methode zur Lösung bestimmter Problemklassen durch das Lösen von Rekursionsbeziehungen/Rekursionen und das Speichern zuvor gefundener Lösungen entweder durch Tabellierung oder Memoisierung. Die Memoisierung ist eine Methode, um Lösungen für zuvor gelöste Probleme zu speichern, und kann mit jeder Funktion verwendet werden, die eindeutige deterministische Lösungen für eine bestimmte Menge von Eingaben hat.

Answer 3

Sowohl bei der Memoisierung als auch bei der dynamischen Programmierung wird jedes Teilproblem nur einmal gelöst.

Die Memoisierung verwendet Rekursionen und arbeitet von oben nach unten, während die dynamische Programmierung in die entgegengesetzte Richtung geht und das Problem von unten nach oben löst.

Nachstehend eine interessante Analogie -

Top-down - Erst sagst du, ich werde die Welt erobern. Wie wollen Sie das tun? Du sagst, ich werde zuerst Asien übernehmen. Wie willst du das anstellen? Ich werde zuerst Indien erobern. Ich werde der Oberste Minister von Delhi werden, usw. usw.

Bottom-up - Du sagst, ich werde der Ministerpräsident von Delhi werden. Dann werde ich Indien übernehmen, dann alle anderen Länder in Asien und schließlich werde ich die Welt erobern.

Answer 4

Dynamische Programmierung wird oft als Memoisierung bezeichnet!

1. Die Memoisierung ist eine Top-Down-Technik (man beginnt mit der Lösung des gegebenen Problems, indem man es zerlegt) und die dynamische Programmierung ist eine Bottom-Up-Technik (man beginnt mit der Lösung des trivialen Teilproblems und nähert sich dem gegebenen Problem an)

2. DP findet die Lösung, indem es mit dem Basisfall/den Basisfällen beginnt und sich nach oben arbeitet. DP löst alle Teilprobleme, weil es von unten nach oben arbeitet

   Im Gegensatz zur Memoisierung, bei der nur die benötigten Teilprobleme gelöst werden

3. DP hat das Potenzial, exponentiell schnelle Brute-Force-Lösungen in polynomiell schnelle Algorithmen zu verwandeln.

4. DP kann viel effizienter sein, weil seine iterative

   Im Gegenteil, Memoization muss für den (oft erheblichen) Overhead aufgrund der Rekursion bezahlen.

Um es einfacher auszudrücken, Memoization verwendet den Top-Down-Ansatz, um das Problem zu lösen, d.h. es beginnt mit dem Hauptproblem und zerlegt es dann in Teilprobleme, die auf ähnliche Weise gelöst werden. Bei diesem Ansatz kann dasselbe Teilproblem mehrfach auftreten und mehr CPU-Zyklen verbrauchen, wodurch sich die Zeitkomplexität erhöht. Bei der dynamischen Programmierung hingegen wird das gleiche Teilproblem nicht mehrfach gelöst, sondern das vorherige Ergebnis wird zur Optimierung der Lösung verwendet.

Answer 5

(1) Memoisierung und DP, konzeptionell ist eigentlich dasselbe. Denn: Betrachten Sie die Definition von DP: "überlappende Teilprobleme" "und optimale Unterstruktur". Die Memoisierung besitzt diese 2 Eigenschaften vollständig.

(2) Memoization ist DP mit dem Risiko des Stack Overflows, wenn die Rekursion tief ist. Bei DP bottom up besteht dieses Risiko nicht.

(3) Die Memoisierung benötigt eine Hashtabelle. Also zusätzlicher Platz und etwas Zeit zum Nachschlagen.

Um also die Frage zu beantworten:

- Konzeptionell (1) bedeutet, dass es sich um dieselbe Sache handelt.

-Wenn man (2) berücksichtigt, ist Memoisierung eine Teilmenge von DP, in dem Sinne, dass ein Problem, das mit Memoisierung lösbar ist, auch mit DP lösbar ist, aber ein Problem, das mit DP lösbar ist, ist möglicherweise nicht mit Memoisierung lösbar (weil es zu einem Stapelüberlauf kommen kann).

-Unter Berücksichtigung von (3) weisen sie geringe Leistungsunterschiede auf.