Die Hauptunterschied zwischen Divide and Conquer und dynamischer Programmierung ist, dass die Divide and Conquer kombiniert die Lösungen der Teilprobleme, um die Lösung des Hauptproblems zu erhalten, während die dynamische Programmierung das Ergebnis der Teilprobleme verwendet, um die optimale Lösung des Hauptproblems zu finden.

Teile und Herrsche und dynamische Programmierung sind zwei Algorithmen oder Ansätze zur Lösung von Problemen. Der Divide-and-Conquer-Algorithmus teilt das Problem in Teilprobleme und kombiniert diese Lösungen, um die Lösung des ursprünglichen Problems zu finden. Die dynamische Programmierung löst die Teilprobleme jedoch nicht unabhängig. Es speichert die Antworten von Teilproblemen, um sie für ähnliche Probleme zu verwenden.

Teile und erobere, dynamische Programmierung

Was ist Divide and Conquer

Teile und herrsche teilt das Hauptproblem in kleine Teilprobleme auf. Die Teilprobleme werden immer wieder unterteilt. An einem Punkt wird es ein Stadium geben, in dem wir die Teilprobleme nicht weiter aufteilen können. Dann können wir jedes Teilproblem unabhängig voneinander lösen. Schließlich können wir die Lösungen aller Teilprobleme kombinieren, um die Lösung des Hauptproblems zu erhalten.

Es gibt drei Hauptschritte beim Teilen und Herrschen. Sie sind wie folgt.

Teilen (Pause) – Beinhaltet die Aufspaltung des Hauptproblems in eine Sammlung von Teilproblemen

Erobern (Lösen) – Beinhaltet die separate Lösung jedes Teilproblems

Kombinieren (Zusammenführen) – Verbindet die Lösungen der Teilprobleme, um die Lösung des Hauptproblems zu erhalten

Was ist dynamische Programmierung?

Die dynamische Programmierung unterteilt das Hauptproblem in kleinere Teilprobleme, löst die Teilprobleme jedoch nicht unabhängig. Es speichert die Ergebnisse der Teilprobleme, die beim Lösen ähnlicher Teilprobleme verwendet werden. Das Speichern der Ergebnisse von Teilproblemen wird als Auswendiglernen bezeichnet. Bevor das aktuelle Teilproblem gelöst wird, überprüft es die Ergebnisse der vorherigen Teilprobleme. Schließlich überprüft es die Ergebnisse aller Teilprobleme, um die beste Lösung oder die optimale Lösung zu finden. Diese Methode ist effektiv, da sie die Antworten nicht immer wieder berechnet. Üblicherweise wird zur Optimierung dynamische Programmierung verwendet.

Elemente der dynamischen Programmierung sind wie folgt.

Einfache Teilprobleme – Teilen Sie das ursprüngliche Problem in kleine Teilprobleme mit ähnlicher Struktur auf

Optimaler Unterbau des Problems – Die optimale Lösung des Hauptproblems liegt innerhalb der optimalen Lösung seiner Teilprobleme

Überlappende Teilprobleme – Situationen, in denen immer wieder die gleichen Teilprobleme gelöst werden

Unterschied zwischen Divide and Conquer und dynamischer Programmierung

Definition

Divide and Conquer ist ein Algorithmus, der ein Problem rekursiv in zwei oder mehr Teilprobleme desselben oder verwandten Typs zerlegt, bis es einfach genug wird, um direkt gelöst zu werden. Dynamische Programmierung ist jedoch ein Algorithmus, der hilft, eine Klasse von Problemen mit überlappenden Teilproblemen und optimalen Teilstruktureigenschaften effizient zu lösen.

Typ

Der Hauptunterschied zwischen Divide and Conquer und dynamischer Programmierung besteht darin, dass Divide and Conquer rekursiv ist, während dynamische Programmierung nicht rekursiv ist.

Teilprobleme

Beim Teilen und Herrschen sind die Teilprobleme unabhängig voneinander. Bei der dynamischen Programmierung sind die Teilprobleme jedoch voneinander abhängig. Daher ist dies ein weiterer wichtiger Unterschied zwischen Teilen und Herrschen und dynamischer Programmierung.

Zeitaufwand

Der Zeitverbrauch ist ein weiterer Unterschied zwischen Teilen und Herrschen und dynamischer Programmierung. Teile und herrsche löst jedes Teilproblem unabhängig voneinander. Daher ist es zeitaufwendiger. Die dynamische Programmierung hingegen verwendet die Antworten der vorherigen Teilprobleme. Somit ist es weniger zeitaufwendig.

Effizienz

Effizienz macht auch einen Unterschied zwischen Divide and Conquer und dynamischer Programmierung. Dynamische Programmierung ist effizienter als Teile und Herrsche.

Anwendungen

Merge-Sort, Quicksort und binäre Suche verwenden Divide and Conquer, während Matrixkettenmultiplikation und optimaler binärer Suchbaum dynamische Programmierung verwenden.

Abschluss

Der Hauptunterschied zwischen Divide and Conquer und dynamischer Programmierung besteht darin, dass die Division and Conquer die Lösungen der Teilprobleme kombiniert, um die Lösung des Hauptproblems zu erhalten, während die dynamische Programmierung das Ergebnis der Teilprobleme verwendet, um die optimale Lösung des Hauptproblems zu finden.

Referenz:

1. „DAA Divide and Conquer Einführung – Javatpoint.“ www.javatpoint.com, hier verfügbar.2. „Einführung in die dynamische Programmierung – Javatpoint.“ www.javatpoint.com, hier verfügbar.3. Dynamische Programmierung | Steps to Design & Applications |, Education 4u, 2. April 2018, hier verfügbar.4. „Dynamische Programmierung“, Programmiz. com, hier erhältlich.

Bild mit freundlicher Genehmigung:

1. „Merge sort algorithm diagram“ Von VineetKumar in der englischen Wikipedia – Von en.wikipedia nach Commons von Eric Bauman mit CommonsHelper (Public Domain) über Commons Wikimedia2 übertragen. „Fibonacci dynamische Programmierung“ Von de:Benutzer:Dcoatzee, verfolgt von Benutzer:Stannered – de:Bild:Fibonacci dynamische Programmierung.png (Public Domain) über Commons Wikimedia