Unterschied zwischen Rückverfolgung und dynamische Programmierung

Question

Ich habe gehört, der einzige Unterschied zwischen dynamischer Programmierung und Rückverfolgung ist DP erlaubt Überlappung von Teilproblemen. (fib (n) = fib (n-1) + fib (n-2)). Ist es richtig ? Gibt es noch andere Unterschiede? Auch möchte ich einige allgemeine Probleme kennen, die mit diesen Techniken gelöst werden.

Answer 1

Es gibt zwei typische Implementierungen von Programmieransatz Dynamisch: von unten nach oben und top-to-bottom.

Top-to-bottom Dynamische Programmierung ist nichts anderes als gewöhnliche Rekursion, verstärkt mit den Lösungen für die Zwischenteilprobleme auswendig zu lernen. Wenn ein gegebenes Teilproblem als zweite (dritte, vierte ...) Zeit auftritt, wird es nicht von Grund auf gelöst, sondern die zuvor gespeicherte Lösung wird sofort verwendet. Diese Technik ist unter dem Namen Memoisierung bekannt (kein 'r' vor 'i').

Dies ist eigentlich, was Ihr Beispiel mit Fibonacci-Sequenz veranschaulichen soll.Verwenden Sie einfach die rekursive Formel für Fibonacci-Sequenz, aber erstellen Sie die Tabelle fib(i) Werte auf dem Weg, und Sie erhalten einen Top-to-bottom-DP-Algorithmus für dieses Problem (so dass, wenn Sie beispielsweise fib(5) zweiten Mal berechnen müssen, Sie bekommen es von der Tabelle, anstatt es erneut zu berechnen).

In Von unten nach oben Dynamische Programmierung Der Ansatz basiert auch auf dem Speichern von Teillösungen im Speicher, aber sie werden in einer anderen Reihenfolge (von kleiner zu größer) gelöst, und die resultierende allgemeine Struktur des Algorithmus ist nicht rekursiv. LCS algorithm ist ein klassisches Bottom-to-Top-DP-Beispiel.

Bottom-to-Top-DP-Algorithmen sind in der Regel effizienter, aber im Allgemeinen schwieriger (und manchmal unmöglich) zu bauen, da es nicht immer einfach ist, welche primitiven Teilprobleme zu lösen das ganze ursprüngliche Problem, und welchen Weg Sie von kleinen Teilproblemen nehmen müssen, um auf die effizienteste Weise zur endgültigen Lösung zu kommen.

Answer 2

Dynamische Probleme erfordern auch "optimale Unterstruktur".

Laut Wikipedia:

Dynamische Programmierung ein Verfahren zur Lösung komplexer Probleme ist durch sie zu brechen in einfachere Stufen hinunter. Es ist anwendbar auf Probleme, die die Eigenschaften der überlappenden Unterprobleme zeigen, die nur geringfügig sind kleinere und optimale Unterstruktur.

Backtracking ist ein allgemeiner Algorithmus für die Suche nach all (oder einigen) -Lösungen für einige Rechenprobleme, dass inkrementell Kandidaten für die Lösungen bauen, und verzichtet auf jeden Teil Kandidaten c („zieht zurück“) so bald als bestimmt es, dass c c möglicherweise nicht zu einer gültigen Lösung abgeschlossen werden kann.

Für eine detaillierte Diskussion der "optimalen Unterstruktur" lesen Sie bitte the CLRS book.

Häufige Probleme für Rückzieher ich denken kann, sind:

1. Eight queen puzzle
2. Map coloring
3. Sodoku?

DP Probleme:

1. Diese website am MIT hat eine gute Sammlung von DP Probleme mit schönen animierten Erklärungen.
2. A chapter from a book von einem Professor in Berkeley.

Answer 3

DP ermöglicht die Lösung eines großen, rechenintensiven Problems, indem es in Teilprobleme zerlegt wird, deren Lösung nur die Kenntnis der unmittelbaren vorherigen Lösung erfordert. Sie werden eine sehr gute Idee bekommen, indem Sie Needleman-Wunsch aufheben und eine Probe lösen, weil es so einfach ist, die Anwendung zu sehen.

Backtracking scheint komplizierter zu sein, wenn der Lösungsbaum beschnitten wird, wenn bekannt ist, dass ein bestimmter Pfad kein optimales Ergebnis liefert.

Daher könnte man sagen, dass Backtracking für den Speicher optimiert, da DP annimmt, dass alle Berechnungen ausgeführt werden, und dann geht der Algorithmus zurück durch die kostengünstigsten Knoten.

Answer 4

Ein weiterer Unterschied könnte sein, dass dynamische Programmierprobleme normalerweise auf dem Prinzip der Optimalität beruhen. Das Prinzip der Optimalität besagt, dass eine optimale Reihenfolge der Entscheidung oder Auswahl jeder Untersequenz auch optimal sein muss.

Backtracking-Probleme sind normalerweise nicht optimal auf ihrem Weg! Sie können nur auf Probleme angewendet werden, die das Konzept der Teilkandidatenlösung zulassen.