Wie unterscheidet sich dynamische Programmierung von gierigen Algorithmen?

In das Buch, das ich mit Einführung in die Planung & Analyse von Algorithmendynamische Programmierung wird gesagt, um den Fokus auf die Prinzip der Optimalität"Eine optimale Lösung für eine Instanz des optimierungsproblems setzt sich aus optimalen Lösungen für Ihre subinstances".

In der Erwägung, dass die gierig Technik konzentriert sich auf den ausbau teilweise konstruiert Lösungen, bis Sie kommen mit einer Lösung für ein problem vollständig. Es wird dann gesagt, es muss die "beste lokale Wahl zwischen allen möglichen Entscheidungen auf, Schritt".

Da sowohl die Einbindung der lokalen Optimalität, ist nicht eine eine Teilmenge der anderen?

InformationsquelleAutor der Frage Irwin | 2012-12-04

  1. 42

    Dynamische Programmierung anwendbar ist, um Probleme mit der Eigenschaften:

    • überlappende Teilprobleme, und
    • optimale Unterkonstruktion.

    Optimale Unterkonstruktion bedeutet, dass Sie gierig lösen Teilprobleme und kombiniere die Lösungen zur Lösung des größeren Problems. Den Unterschied zwischen dynamischer Programmierung und greedy-algorithmen ist, dass Sie mit der dynamischen Programmierung gibt es überlappende Teilprobleme, und diese Teilprobleme gelöst sind, mit memoization. "Memoization" ist die Technik, wobei Lösungen zu Teilproblemen werden verwendet, um die Lösung anderer Teilprobleme schneller.

    Diese Antwort bekommen hat einige Aufmerksamkeit, so gebe ich einige Beispiele.

    Betrachten wir das problem "Making change mit Dollar, nickels und Pfennige." Dies ist eine gierige problem. Es stellt die optimale Unterstruktur, da Sie sich lösen können, für die Anzahl der Dollar. Dann lösen Sie für die Anzahl der nickels. Dann die Anzahl der Pfennige. Anschließend können Sie kombinieren die Lösungen dieser Teilprobleme effizient. Es ist nicht wirklich zeigen überlappende Teilprobleme da die Lösung jedes subproblem hilft nicht viel mit den anderen (vielleicht ein bisschen).

    Betrachten wir das problem "Fibonnaci zahlen." Es stellt die optimale Unterstruktur, da Sie sich lösen können, F(10) F(9) F(8) effizient (durch addition). Diese Teilprobleme überlappen, weil Sie beide teilen F(7). Wenn Sie memoize das Ergebnis von F(7), wenn Sie die Lösung F(8) können Sie lösen F(9) mehr schnell.

    Antwort auf den Kommentar über dynamische Programmierung zu tun, mit "zu überdenken, Entscheidungen": Dies ist natürlich nicht wahr, für jede lineare dynamische Programmierung Algorithmus wie das maximum-subarray problem oder die Fibonacci-problem vor.

    Im wesentlichen stellen Sie sich ein problem mit der optimalen Substruktur als gerichteten azyklischen Graphen, dessen Knoten repräsentieren Teilprobleme (wobei sich das ganze problem wird durch einen Knoten dargestellt, deren indegree ist null), und dessen gerichtete Kanten repräsentieren die Abhängigkeiten zwischen den Teilproblemen. Dann, eine gierige problem ist ein Baum (alle Knoten außer die Wurzel haben Einheit indegree). Eine dynamische Programmierung problem hat, einige Knoten mit indegree größer als eins. Dies verdeutlicht die überlappende Teilprobleme.

    InformationsquelleAutor der Antwort Neil G

  2. 11

    Der Unterschied ist, dass die dynamische Programmierung erfordert, dass Sie die Antwort erinnern, für die kleineren Staaten, während ein greedy-Algorithmus ist lokal in dem Sinne, dass alle notwendigen Informationen im aktuellen Zustand. Natürlich, es gibt eine gewisse Schnittmenge.

    InformationsquelleAutor der Antwort bcurcio

  3. 9

    Der entscheidende Unterschied ist, dass greedy-algorithmen Komponieren Lösungen "statisch" in dem Sinne, dass jeder lokale Wahl in der Lösung abgeschlossen werden kann, ohne zu wissen, etwas über die anderen lokalen Entscheidungen. Dynamische algorithmen, jedoch, erstellen Sie Gruppen von möglichen Lösungen zu Teilproblemen und erzeugt nur eine einzige Lösung für das Globale problem, wenn alle sub-Probleme berücksichtigt wurden. Die Wikipedia-Seite über gierige algorithmen bringt es gut:

    Der Wahl eines greedy-Algorithmus kann, hängt von Entscheidungen, die bisher aber nicht auf künftige Entscheidungen oder alle Lösungen für das subproblem. Es iterativ macht einem gierigen Wahl nach der anderen, Reduzierung der jedes gegebene problem in ein kleineres. In anderen Worten, ein greedy-Algorithmus nie überdenkt seine Entscheidungen. Dies ist der wesentliche Unterschied zu der dynamischen Programmierung, das ist erschöpfend und wird garantiert, um die Lösung zu finden. Nach jeder Phase, dynamische Programmierung, Entscheidungen auf der Basis aller Entscheidungen, die in der vorherigen Phase, und vielleicht überdenken die vorhergehenden algorithmischen Weg zur Lösung.

    InformationsquelleAutor der Antwort Kyle Strand

  4. 6

    DP-algorithmen nutzt die Tatsache, dass (einige Probleme) - eine optimale Lösung für ein problem der Größe n besteht aus einer optimalen Lösung für ein problem der Größe n'<nund verwendet diese, um die Lösung von unten nach oben, vom kleinsten problem bis zur gewünschten Größe.

    Passt es das gleiche Prinzip der Rekursion sehr gut (reduzieren das problem auf eine kleinere sub-problem, und rufen rekursiv), und in der Tat - DP-Lösungen sind oft vertreten wie eine rekursive Formel.

    Greedy-algorithmen suchen in einem lokalen zeigen und dabei einige Wahl mit den Daten an dieser Stelle. Für einige Probleme (kürzeste Pfad ohne negatve GEWICHTE zum Beispiel) - das lokale Wahl-führen zu einer optimalen Lösung.

    Ein gutes Beispiel für die Unterschiede zwischen den beiden Ansätzen ist für die shortest path problem:

    • Dijsktra-Algorithmus ist ein greedy-Ansatz (Bei jedem Schritt, wählen Sie den Knoten, der der Pfad zur aktuell minimiert - die Auswahl erfolgt gierig, basierend auf den lokalen Zustand des Algorithmus).
    • Bellman-Ford-Algorithmus ist ein DP-Lösung ("relax" ALLE Kanten effektiv verringert das problem)

    InformationsquelleAutor der Antwort amit

  5. 1

    Greedy-Methode:

    1. Greedy-Methode konzentriert sich auf den ausbau von teilweise konstruierten Lösungen.
    2. Es liefert viele Ergebnisse, wie praktikable Lösung.
    3. Effizienter

    Dynamische Programmierung:

    1. Konzentriert sich auf das Prinzip der Optimalität.
    2. Es bietet konkrete Antworten.
    3. Weniger effizient

    InformationsquelleAutor der Antwort Prashant Kumbharkar

  6. 0

    Den Unterschied zwischen DP und gierig ist die DP wird sich nach der global optimalen bei jedem subproblem, aber gierig wird, suchen nur nach der lokal optimalen. So, das zu diesem Szenario:

    Nehme an, Sie werden einen Berg zu besteigen, und Sie möchten, zu klettern so hoch wie möglich. Die Straße auf dem Berg hat mehrere Zweige, und an jeder Kreuzung, die Sie brauchen, um zu entscheiden, welcher Zweig zu nehmen, das ist das subproblem dieses klettern problem (das Ziel ist das gleiche, nur der Ausgangspunkt ist Verschieden)

    Für den greedy-Algorithmus, werden Sie immer wählen, je nachdem, niemand scheint mehr steil hinauf. Dies ist ein lokale optimale Entscheidung und es ist nicht gewährleistet, um zu dem besten Ergebnis führen

    Für die DP, an jeder Kreuzung, sollten Sie bereits wissen, ist die höchstgelegene jede Verzweigung führt Sie zu (angenommen, Ihre Bewertung Reihenfolge Umgekehrt, ein.k.eine vom Endpunkt zum Ausgangspunkt), und wählen Sie diejenige mit der größten Höhe. Diese Entscheidung baut auf das Globale optimum der Zukunft Teilprobleme und gibt es für Global optimal für dieses subproblem

    InformationsquelleAutor der Antwort NoSegfault

  7. -1

    Die Konzepte der gierig und dynamische Lösungen schließen sich nicht gegenseitig aus und ich denke, das verursacht eine Menge Verwirrung in den meisten Antworten. Ich glaube, amit Antwort betont auf die wichtigste Eigenschaft: eine greedy-Lösung ermöglicht Entscheidungen auf der Basis von lokalen Informationen. Als Folge einer greedy-Lösung bis Ende Mai finden ein lokalen optimale anstatt eine Globale.
    Dynamische Lösungen, brechen Sie ein problem in kleinere Teilprobleme und dann aggregieren, das Ergebnis zu erhalten, ist die Antwort für ein größeres komplexeres problem. So ist es möglich, dass ein problem sowohl dynamische und gierig? Die Antwort ist - ja, es ist möglich. Ein Beispiel wäre z.B. der Dijkstra-Algorithmus. Für diesen Algorithmus eine greedy-Wahl auf jedem Schritt, und doch reduzieren Sie das problem auf eine einfachere subproblem.

    Dennoch gibt es auch Beispiele von greedy-algorithmen sind nicht DP-s: sagen Sie Hügel klettern ist ein greedy-Algorithmus, der bricht nicht ein problem in mehrere Teilprobleme - es nur immer löst. Es gibt auch Beispiele von DPs, die nicht gierig sind - z.B. das berechnen der n-TEN Fibonacci-Zahl mit memoization ist nicht gierig.

    InformationsquelleAutor der Antwort Ivaylo Strandjev

Schreibe einen Kommentar