Unterschied zwischen Divide and Conquer Algo und Dynamic Programming

Was ist der Unterschied zwischen Divide and Conquer-Algorithmen und dynamischen Programmieralgorithmen? Wie unterscheiden sich die beiden Begriffe? Ich verstehe den Unterschied zwischen ihnen nicht.

Bitte nehmen Sie ein einfaches Beispiel, um den Unterschied zwischen den beiden zu erklären und zu erklären, aus welchem ​​Grund sie ähnlich zu sein scheinen.

Teilen und erobern

Divide and Conquer funktioniert, indem das Problem in Unterprobleme unterteilt wird, jedes Unterproblem rekursiv erobert und diese Lösungen kombiniert werden.

Dynamische Programmierung

Dynamische Programmierung ist eine Technik zum Lösen von Problemen mit überlappenden Teilproblemen. Jedes Unterproblem wird nur einmal gelöst und das Ergebnis jedes Unterproblems wird in einer Tabelle (im Allgemeinen als Array oder Hash-Tabelle implementiert) für zukünftige Referenzen gespeichert. Diese Unterlösungen können verwendet werden, um die ursprüngliche Lösung zu erhalten, und die Technik zum Speichern der Unterproblemlösungen ist als Memoisierung bekannt.

Sie können daran denken DP = recursion + re-use

Ein klassisches Beispiel, um den Unterschied zu verstehen, wäre, beide Ansätze zur Ermittlung der n-ten Fibonacci-Zahl zu sehen. Überprüfen Sie dieses Material vom MIT.

Teilen und Erobern Ansatz

Dynamischer Programmieransatz

Der andere Unterschied zwischen Teilen und Erobern und dynamischer Programmierung könnte sein:

Teilen und erobern:

1. Arbeitet mehr an den Unterproblemen und hat daher mehr Zeitverbrauch.
2. Beim Teilen und Erobern sind die Unterprobleme unabhängig voneinander.

Dynamische Programmierung:

1. Löst die Unterprobleme nur einmal und speichert sie dann in der Tabelle.
2. Bei der dynamischen Programmierung sind die Unterprobleme nicht unabhängig.

Manchmal rufen Sie beim rekursiven Programmieren die Funktion mehrmals mit denselben Parametern auf, was nicht erforderlich ist.

Das berühmte Beispiel Fibonacci-Zahlen:

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

Lassen Sie uns F (5) ausführen:

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

Also haben wir gerufen: 1 mal F (4) 2 mal F (3) 3 mal F (2) 2 mal F (1)

Dynamischer Programmieransatz: Wenn Sie eine Funktion mit demselben Parameter mehrmals aufrufen, speichern Sie das Ergebnis in einer Variablen, um beim nächsten Mal direkt darauf zuzugreifen. Der iterative Weg:

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

Nennen wir noch einmal F (5):

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

Wie Sie sehen, greifen Sie bei jedem Mehrfachaufruf einfach auf die entsprechende Variable zu, um den Wert abzurufen, anstatt ihn neu zu berechnen.

Dynamische Programmierung bedeutet übrigens nicht, einen rekursiven Code in einen iterativen Code umzuwandeln. Sie können die Unterergebnisse auch in einer Variablen speichern, wenn Sie einen rekursiven Code wünschen. In diesem Fall wird die Technik als Memoisierung bezeichnet. In unserem Beispiel sieht es so aus:

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

Die Beziehung zu Divide and Conquer besteht also darin, dass D & D-Algorithmen auf Rekursion beruhen. Und einige Versionen von ihnen haben diesen "Mehrfachfunktionsaufruf mit demselben Parameterproblem". Suchen Sie nach "Matrixkettenmultiplikation" und "längster gemeinsamer Teilsequenz" für solche Beispiele, bei denen DP benötigt wird, um die T (n) von D & D algo zu verbessern.

Dynamische Programmierung und Divide-and-Conquer-Ähnlichkeiten

Aus meiner Sicht kann ich sagen, dass dynamische Programmierung eine Erweiterung des Paradigmas der Teilung und Eroberung ist .

Ich würde sie nicht als etwas völlig anderes behandeln. Weil beide arbeiten, indem sie ein Problem rekursiv in zwei oder mehr Unterprobleme desselben oder verwandten Typs aufteilen, bis diese einfach genug werden, um direkt gelöst zu werden. Die Lösungen für die Unterprobleme werden dann kombiniert, um eine Lösung für das ursprüngliche Problem zu erhalten.

Warum haben wir dann immer noch andere Paradigmennamen und warum habe ich dynamische Programmierung als Erweiterung bezeichnet? Dies liegt daran, dass der dynamische Programmieransatz nur dann auf das Problem angewendet werden kann, wenn das Problem bestimmte Einschränkungen oder Voraussetzungen aufweist . Und danach erweitert die dynamische Programmierung den Divide and Conquer-Ansatz um Memoization- oder Tabellierungstechniken .

Lass uns Schritt für Schritt gehen ...

Dynamische Programmiervoraussetzungen / -einschränkungen

Wie wir gerade entdeckt haben, gibt es zwei Schlüsselattribute, die das Problem teilen und überwinden muss, damit die dynamische Programmierung anwendbar ist:

• Optimale Unterstruktur  - Eine optimale Lösung kann aus optimalen Lösungen ihrer Teilprobleme konstruiert werden

• Überlappende Teilprobleme  - Das Problem kann in Teilprobleme unterteilt werden, die mehrmals wiederverwendet werden, oder ein rekursiver Algorithmus für das Problem löst das gleiche Teilproblem immer wieder, anstatt immer neue Teilprobleme zu generieren

Sobald diese beiden Bedingungen erfüllt sind, können wir sagen, dass dieses Teilungs- und Eroberungsproblem unter Verwendung eines dynamischen Programmieransatzes gelöst werden kann.

Dynamische Programmiererweiterung für Teilen und Erobern

Der dynamische Programmieransatz erweitert den Divide and Conquer-Ansatz um zwei Techniken ( Memoisierung und Tabellierung ), die beide dazu dienen, Teilproblemlösungen zu speichern und wiederzuverwenden, die die Leistung drastisch verbessern können. Zum Beispiel hat die naive rekursive Implementierung der Fibonacci-Funktion eine zeitliche Komplexität, O(2^n)bei der die DP-Lösung dasselbe nur mit der O(n)Zeit tut .

Das Speichern (Top-Down-Cache-Füllen) bezieht sich auf die Technik des Zwischenspeicherns und Wiederverwendens zuvor berechneter Ergebnisse. Die gespeicherte fibFunktion würde also so aussehen:

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)

        mem[n] = result
    return mem[n]
}

Die Tabellierung (Bottom-Up-Cache-Füllung) ist ähnlich, konzentriert sich jedoch auf das Füllen der Cache-Einträge. Die Berechnung der Werte im Cache erfolgt am einfachsten iterativ. Die Tabellenversion von fibwürde folgendermaßen aussehen:

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

Weitere Informationen zum Speichern und Vergleichen von Tabellen finden Sie hier .

Die Hauptidee, die Sie hier verstehen sollten, ist, dass das Zwischenspeichern von Teilproblemlösungen möglich wird, da unser Teilungs- und Eroberungsproblem überlappende Unterprobleme aufweist, und somit das Auswendiglernen / Tabellieren in die Szene vordringt.

Also, was ist der Unterschied zwischen DP und DC?

Da wir jetzt mit den DP-Voraussetzungen und ihren Methoden vertraut sind, sind wir bereit, alles, was oben erwähnt wurde, in einem Bild zusammenzufassen.

Wenn Sie Codebeispiele anzeigen möchten, finden Sie hier eine ausführlichere Erläuterung, in der Sie zwei Algorithmusbeispiele finden: Binäre Suche und Mindestbearbeitungsabstand (Levenshtein-Abstand), die den Unterschied zwischen DP und DC veranschaulichen.

Ich gehe davon aus, dass Sie bereits Wikipedia und andere akademische Ressourcen dazu gelesen haben, daher werde ich keine dieser Informationen recyceln. Ich muss auch darauf hinweisen, dass ich keineswegs ein Informatikexperte bin, aber ich werde meine zwei Cent für mein Verständnis dieser Themen teilen ...

Dynamische Programmierung

Zerlegt das Problem in diskrete Teilprobleme. Der rekursive Algorithmus für die Fibonacci-Sequenz ist ein Beispiel für die dynamische Programmierung, da er nach fib (n) auflöst, indem zuerst nach fib (n-1) gelöst wird. Um das ursprüngliche Problem zu lösen, wird ein anderes Problem gelöst.

Teilen und erobern

Diese Algorithmen lösen normalerweise ähnliche Teile des Problems und setzen sie am Ende zusammen. Mergesort ist ein klassisches Beispiel für Teilen und Erobern. Der Hauptunterschied zwischen diesem Beispiel und dem Fibonacci-Beispiel besteht darin, dass in einem Mergesort die Aufteilung (theoretisch) willkürlich sein kann und Sie immer noch zusammenführen und sortieren, unabhängig davon, wie Sie sie aufteilen. Es muss dieselbe Menge an Arbeit geleistet werden, um das Array zusammenzuführen, unabhängig davon, wie Sie es aufteilen. Das Lösen nach fib (52) erfordert mehr Schritte als das Lösen nach fib (2).

Ich betrachte es Divide & Conquerals rekursiven Ansatz und Dynamic Programmingals Tabellenfüllung.

Beispielsweise Merge Sorthandelt es sich um einen Divide & ConquerAlgorithmus, bei dem Sie in jedem Schritt das Array in zwei Hälften aufteilen, die beiden Hälften rekursiv aufrufen Merge Sortund sie dann zusammenführen.

Knapsackist ein Dynamic ProgrammingAlgorithmus, während Sie eine Tabelle füllen, die optimale Lösungen für Teilprobleme des gesamten Rucksacks darstellt. Jeder Eintrag in der Tabelle entspricht dem Maximalwert, den Sie in einem Beutel mit Gewicht bei den Artikeln 1-j tragen können.

Teilen und Erobern umfasst drei Schritte auf jeder Rekursionsstufe:

1. Teilen Sie das Problem in Teilprobleme.
2. Erobern Sie die Teilprobleme, indem Sie sie rekursiv lösen.
3. Kombinieren Sie die Lösung für Teilprobleme zur Lösung für das ursprüngliche Problem.
   
   • Es ist ein Top-Down- Ansatz.
     
   • Es arbeitet mehr an Teilproblemen und hat daher mehr Zeitaufwand.
   • z.B. Der n-te Term der Fibonacci-Reihe kann in O (2 ^ n) -Zeitkomplexität berechnet werden.
     
     

Die dynamische Programmierung umfasst die folgenden vier Schritte:

1. Charakterisieren Sie die Struktur optimaler Lösungen.
2. Definieren Sie rekursiv die Werte optimaler Lösungen.
3. Berechnen Sie den Wert optimaler Lösungen.
4. Erstellen Sie eine optimale Lösung aus berechneten Informationen .

• Es ist ein Bottom-up- Ansatz.
• Weniger Zeitaufwand als Teilen und Erobern, da wir die zuvor berechneten Werte verwenden, anstatt sie erneut zu berechnen.
• z.B. Der n-te Term der Fibonacci-Reihe kann in O (n) -Zeitkomplexität berechnet werden.
  
  

Betrachten wir zum leichteren Verständnis Teilen und Erobern als Brute-Force-Lösung und deren Optimierung als dynamische Programmierung.

NB Divide and Conquer-Algorithmen mit überlappenden Teilproblemen können nur mit dp optimiert werden.