Der Hauptunterschied zwischen der Greedy-Methode und der dynamischen Programmierung besteht darin, dass die durch die Greedy-Methode getroffene Entscheidung (Wahl) hängt von den bisher getroffenen Entscheidungen (Wahl) ab und beruht nicht auf zukünftigen Entscheidungen oder allen Lösungen der Teilprobleme. Andererseits trifft die dynamische Programmierung Entscheidungen auf der Grundlage aller Entscheidungen, die in der vorherigen Phase getroffen wurden, um das Problem zu lösen.

Ein Algorithmus ist eine systematische Abfolge von Schritten zur Lösung eines Problems. Greedy-Methode und dynamische Programmierung sind zwei Algorithmen. Beide werden verwendet, um Optimierungsprobleme zu lösen.

Gierige Methode, dynamische Programmierung

Was ist die gierige Methode?

Bei der gierigen Methode wird aus mehreren Barwerten die beste Option gefunden. Bei dieser Methode betrachten wir die erste Stufe und entscheiden über die Ausgabe, ohne die zukünftigen Ausgaben zu berücksichtigen. Mit anderen Worten, der Greedy-Algorithmus löst das Problem, indem er die beste Option zu diesem bestimmten Zeitpunkt in Betracht zieht.

Der Greedy-Algorithmus funktioniert, wenn das Problem zwei Eigenschaften enthält, als Greedy-Choice-Eigenschaft und optimale Unterstruktur. Es ist möglich, eine global optimale Lösung zu finden, indem eine lokal optimale Lösung erstellt wird. Mit anderen Worten, das Erstellen gieriger Entscheidungen hilft, die optimale Lösung zu finden. Daher wird diese Eigenschaft als Greedy-Choice-Eigenschaft bezeichnet. Außerdem enthalten optimale Lösungen optimale Teillösungen. Daher wird diese Eigenschaft als optimale Unterstruktur bezeichnet.

Was ist dynamische Programmierung?

Bei der dynamischen Programmierung wird das Hauptproblem in kleine Teilprobleme unterteilt. Die Methode speichert die Ergebnisse von Teilproblemen und wendet sie auf ähnliche Teilprobleme an. Hier wird das Speichern der Antworten von Teilproblemen als Auswendiglernen bezeichnet. Es überprüft die Antworten von Teilproblemen und kommt schließlich zu einem Ergebnis, um die optimale oder beste Lösung zu finden. Da die dynamische Programmierung die vorherigen Antworten überprüft und die mehrfache Berechnung derselben Antwort vermeidet, ist sie effizienter.

Bei der dynamischen Programmierung liegt die optimale Lösung des Hauptproblems innerhalb der optimalen Lösung seiner Teilprobleme. Wenn es Situationen gibt, in denen immer wieder dieselben Teilprobleme auftreten, spricht man von überlappenden Teilproblemen.

Unterschied zwischen gieriger Methode und dynamischer Programmierung

Definition

Die Greedy-Methode ist ein Algorithmus, der der Problemlösungsheuristik folgt, in jedem Geschäft die lokal optimale Wahl zu treffen, um ein globales Optimum zu finden. Dynamische Programmierung hingegen ist ein Algorithmus, der hilft, eine Klasse von Problemen mit überlappenden Teilproblemen und optimalen Teilstruktureigenschaften effizient zu lösen. Diese Definitionen erklären den Hauptunterschied zwischen Greedy Method und Dynamic Programming.

Effizienz

Darüber hinaus besteht ein wesentlicher Unterschied zwischen der Greedy-Methode und der dynamischen Programmierung in ihrer Effizienz. Die Greedy-Methode ist weniger effizient, während die dynamische Programmierung effizienter ist.

Verfahren

Entscheidung fällen

Die Methode der Entscheidungsfindung ist ein weiterer Unterschied zwischen der Greedy-Methode und der dynamischen Programmierung. Die Greedy-Methode trifft Entscheidungen unter Berücksichtigung der ersten Phase, während die dynamische Programmierung Entscheidungen in jeder Phase trifft.

Abschluss

Die durch die Greedy-Methode getroffene Entscheidung (Wahl) hängt von den bisher getroffenen Entscheidungen (Wahl) ab und beruht nicht auf zukünftigen Entscheidungen oder allen Lösungen der Teilprobleme. Die dynamische Programmierung trifft jedoch Entscheidungen auf der Grundlage aller Entscheidungen, die in der vorherigen Phase getroffen wurden, um das Problem zu lösen. Das ist der Hauptunterschied zwischen Greedy Method und Dynamic Programming.

Referenz:

1. „Einführung in die dynamische Programmierung – Javatpoint.“ www.javatpoint.com, hier verfügbar.2. Dynamische Programmierung | Steps to Design & Applications |, Education 4u, 2. April 2018, hier verfügbar.3. „Einführung in gierige Algorithmen – Javatpoint.“ www.javatpoint.com, hier verfügbar.4. "Gieriger Algorithmus." Wikipedia, Wikimedia Foundation, 9. Oktober 2018, hier verfügbar.

Bild mit freundlicher Genehmigung:

1. „Greedy-search-path-example“ Von Swfung8 – Eigene Arbeit (CC BY-SA 3.0) über Commons Wikimedia2. „Fibonacci dynamische Programmierung“ Von de:Benutzer:Dcoatzee, verfolgt von Benutzer:Stannered – de:Bild:Fibonacci dynamische Programmierung.png (Domini públic) über Commons Wikimedia