Was ist der Unterschied zwischen Memoisierung und dynamischer Programmierung?

Was ist der Unterschied zwischen Memoisierung und dynamischer Programmierung? Ich denke, dynamische Programmierung ist eine Teilmenge der Memoisierung. Ist es richtig?

Relevanter Artikel zu Programming.Guide: Dynamische Programmierung vs. Memoisierung vs. Tabellierung

Was ist der Unterschied zwischen Memoisierung und dynamischer Programmierung?

Memoization ist ein Begriff, der eine Optimierungstechnik beschreibt, bei der Sie zuvor berechnete Ergebnisse zwischenspeichern und das zwischengespeicherte Ergebnis zurückgeben, wenn dieselbe Berechnung erneut benötigt wird.

Die dynamische Programmierung ist eine Technik zur iterativen Lösung rekursiver Probleme und kann angewendet werden, wenn sich die Berechnungen der Teilprobleme überschneiden.

Die dynamische Programmierung wird normalerweise mithilfe von Tabellierungen implementiert, kann jedoch auch mithilfe von Memoization implementiert werden. Wie Sie sehen können, ist keines eine "Teilmenge" des anderen.

Eine vernünftige Folgefrage lautet: Was ist der Unterschied zwischen Tabellierung (die typische dynamische Programmiertechnik) und Memoisierung?

Wenn Sie ein dynamisches Programmierproblem mithilfe einer Tabellierung lösen, lösen Sie das Problem "von unten nach oben ", dh indem Sie zuerst alle zugehörigen Unterprobleme lösen, indem Sie normalerweise eine n- dimensionale Tabelle ausfüllen . Basierend auf den Ergebnissen in der Tabelle wird dann die Lösung für das "obere" / ursprüngliche Problem berechnet.

Wenn Sie das Problem mithilfe der Memoisierung lösen, führen Sie eine Karte mit bereits gelösten Unterproblemen durch. Sie tun dies "von oben nach unten " in dem Sinne, dass Sie zuerst das "oben" -Problem lösen (das normalerweise nach unten zurückkehrt, um die Unterprobleme zu lösen).

Eine gute Folie von hier (Link ist jetzt tot, Folie ist aber immer noch gut):

• Wenn alle Teilprobleme mindestens einmal gelöst werden müssen, übertrifft ein dynamischer Bottom-Up-Programmieralgorithmus normalerweise einen von oben nach unten gespeicherten Algorithmus um einen konstanten Faktor
  • Kein Overhead für die Rekursion und weniger Overhead für die Tabellenpflege
  • Es gibt einige Probleme, bei denen das reguläre Muster der Tabellenzugriffe im Algorithmus für die dynamische Programmierung ausgenutzt werden kann, um den Zeit- oder Platzbedarf noch weiter zu reduzieren
• Wenn einige Teilprobleme im Teilproblembereich überhaupt nicht gelöst werden müssen, hat die gespeicherte Lösung den Vorteil, dass nur die Teilprobleme gelöst werden, die definitiv erforderlich sind

Zusätzliche Ressourcen:

• Wikipedia: Auswendiglernen , Dynamische Programmierung
• Verwandte SO Q / A: Memoisierungs- oder Tabellierungsansatz für die dynamische Programmierung

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

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

Memoization ist eine einfache Methode, um zuvor gelöste Lösungen zu verfolgen (häufig als Hash-Schlüssel-Wert-Paar implementiert, im Gegensatz zu Tabellierungen, die häufig auf Arrays basieren), damit sie nicht erneut berechnet werden, wenn sie erneut auftreten. Es kann sowohl in Bottom-Up- als auch in Top-Down-Methoden verwendet werden.

Siehe diese Diskussion über Memoisierung und Tabellierung.

Dynamische Programmierung ist also eine Methode, um bestimmte Problemklassen zu lösen, indem Wiederholungsrelationen / -rekursionen gelöst und zuvor gefundene Lösungen entweder durch Tabellierung oder Memoisierung gespeichert werden. Memoization ist eine Methode, um Lösungen für zuvor gelöste Probleme zu verfolgen. Sie kann mit jeder Funktion verwendet werden, die eindeutige deterministische Lösungen für einen bestimmten Satz von Eingaben bietet.

Dynamische Programmierung wird oft als Memoization bezeichnet!

1. Das Auswendiglernen ist die Top-Down-Technik (lösen Sie das gegebene Problem, indem Sie es auflösen), und die dynamische Programmierung ist eine Bottom-up-Technik (beginnen Sie mit dem Lösen vom trivialen Unterproblem 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

   Im Gegensatz zu Memoization, das nur die erforderlichen Unterprobleme löst

3. DP hat das Potenzial, Brute-Force-Lösungen mit Exponentialzeit in Algorithmen mit Polynomzeit umzuwandeln.

4. DP kann viel effizienter sein, weil es iterativ ist

   Im Gegenteil, Memoization muss den (oft erheblichen) Overhead aufgrund von Rekursion bezahlen.

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.

(1) Memoization und DP sind konzeptionell wirklich dasselbe. Denn: Betrachten Sie die Definition von DP: "überlappende Teilprobleme" "und optimale Unterstruktur". Das Auswendiglernen besitzt diese 2 vollständig.

(2) Das Auswendiglernen ist DP mit dem Risiko eines Stapelüberlaufs, wenn die Rekursion tief ist. DP Bottom Up hat dieses Risiko nicht.

(3) Memoization benötigt eine Hash-Tabelle. Also zusätzlicher Platz und etwas Suchzeit.

Um die Frage zu beantworten:

- Konzeptionell bedeutet (1), dass sie dasselbe sind.

- Wenn Sie (2) berücksichtigen, ist Memoisierung eine Teilmenge von DP, wenn Sie wirklich wollen, in dem Sinne, dass ein durch Memoisierung lösbares Problem durch DP lösbar ist, ein durch DP lösbares Problem jedoch möglicherweise nicht durch Memoisierung lösbar ist (weil es möglicherweise Überlauf stapeln).

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

Aus Wikipedia:

Auswendiglernen

Beim Rechnen ist das Auswendiglernen eine Optimierungstechnik, die hauptsächlich verwendet wird, um Computerprogramme zu beschleunigen, indem Funktionsaufrufe vermeiden, dass die Berechnung der Ergebnisse für zuvor verarbeitete Eingaben wiederholt wird.

Dynamische Programmierung

In der Mathematik und Informatik ist die dynamische Programmierung eine Methode zur Lösung komplexer Probleme, indem sie in einfachere Teilprobleme zerlegt werden.

Wenn wir ein Problem in kleinere / einfachere Teilprobleme aufteilen, stoßen wir häufig mehrmals auf dasselbe Teilproblem. Daher verwenden wir Memoization, um die Ergebnisse früherer Berechnungen zu speichern, damit wir sie nicht wiederholen müssen.

Bei der dynamischen Programmierung treten häufig Situationen auf, in denen die Verwendung von Memoization sinnvoll ist. Sie können jedoch beide Techniken verwenden, ohne unbedingt die andere zu verwenden.

Sowohl Memoization als auch Dynamic Programming lösen einzelne Teilprobleme nur einmal.

Die Memoisierung verwendet Rekursion und arbeitet von oben nach unten, während sich die dynamische Programmierung in die entgegengesetzte Richtung bewegt, um das Problem von unten nach oben zu lösen.

Unten ist eine interessante Analogie -

Top-down - Zuerst sagst du, ich werde die Welt übernehmen. Wie wirst du das machen? Sie sagen, ich werde zuerst Asien übernehmen. Wie wirst du das machen? Ich werde zuerst Indien übernehmen. Ich werde der oberste Minister von Delhi usw. usw.

Bottom-up - Sie sagen, ich werde der CM von Delhi. Dann werde ich Indien übernehmen, dann alle anderen Länder in Asien und schließlich werde ich die Welt übernehmen.

Ich möchte mit einem Beispiel gehen ;

Problem:

Sie steigen eine Treppe hinauf. Es dauert n Schritte, um nach oben zu gelangen.

Jedes Mal können Sie entweder 1 oder 2 Stufen erklimmen. Auf wie viele verschiedene Arten können Sie nach oben klettern?

Rekursion mit Auswendiglernen

Auf diese Weise beschneiden wir den Rekursionsbaum (Entfernen von überschüssigem Material von einem Baum oder Strauch) mit Hilfe eines Memo-Arrays und reduzieren die Größe des Rekursionsbaums auf nn.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Dynamische Programmierung

Wie wir sehen können, kann dieses Problem in Teilprobleme unterteilt werden und es enthält die optimale Unterstruktureigenschaft, dh seine optimale Lösung kann effizient aus optimalen Lösungen seiner Teilprobleme konstruiert werden. Wir können dieses Problem mithilfe dynamischer Programmierung lösen.

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Beispiele finden Sie unter https://leetcode.com/problems/climbing-stairs/

Denken Sie nur an zwei Möglichkeiten:

1. Wir zerlegen das größere Problem in kleinere Teilprobleme - Top-down-Ansatz.
2. Wir gehen vom kleinsten Teilproblem aus und erreichen das größere Problem - den Bottom-up-Ansatz.

Im Memoization gehen wir zu (1.), wo wir jeden Funktionsaufruf in einem Cache speichern und von dort zurückrufen . Es ist ein bisschen teuer, da es rekursive Aufrufe beinhaltet.

In der dynamischen Programmierung gehen wir zu (2.), wo wir eine Tabelle von unten nach oben pflegen, indem wir Teilprobleme unter Verwendung der in der Tabelle gespeicherten Daten lösen, die üblicherweise als dp-Tabelle bezeichnet werden.

Hinweis:

• Beide gelten für Probleme mit überlappenden Unterproblemen.

• Die Speicherung ist aufgrund des Overheads bei rekursiven Funktionsaufrufen vergleichsweise schlecht für DP.

• Die asymptotische Zeitkomplexität bleibt gleich.

In Dynamische Programmierung ,

• Kein Overhead für die Rekursion, weniger Overhead für die Pflege der Tabelle.
• Das reguläre Muster der Tabellenzugriffe kann verwendet werden, um den Zeit- oder Platzbedarf zu reduzieren.

In Memorization ,

• Einige Teilprobleme müssen nicht gelöst werden.