Dynamische Programmierung: Warum die Notwendigkeit einer optimalen Unterstruktur

Bei dynamischer Programmierung hat ein gegebenes Problem eine optimale Unterstruktureigenschaft , wenn eine optimale Lösung des gegebenen Problems durch Verwendung optimaler Lösungen seiner Unterprobleme erreicht werden kann.

Zum Beispiel hat das Problem des kürzesten Pfades folgende optimale Substruktureigenschaft: Wenn ein Knoten X auf dem kürzesten Weg von einem Quellenknoten U zu Zielknoten V liegt, dann ist der kürzeste Weg von U nach V eine Kombination der kürzeste Weg von U nach X und der kürzeste Weg von X nach V.

Das längste Pfadproblem hat jedoch nicht die Eigenschaft Optimal Substruktur. h. der längste Pfad zwischen zwei Knoten muss nicht der längste Pfad zwischen den Knoten zwischen den Knoten sein.

Zum Beispiel ist der längste Pfad q- & gt; r- & gt; t keine Kombination aus dem längsten Pfad von q nach r und dem längsten Pfad von r nach t, ​​da der längste Pfad von q zu r ist q- & gt; s- & gt; t- & gt; r.

Also hier: optimale Lösung für ein Problem enthält keine optimale Lösung für die Unterprobleme.

Für weitere Details können Sie

1. Längstes Pfadproblem von Wikipedia
2. Optimale Substruktur von wikipedia

Sie haben vollkommen Recht, dass die Definitionen ungenau sind. DP ist eine Technik, um algorithmische Beschleunigungen zu erhalten und nicht nur einen Algorithmus. Der Begriff "optimale Unterstruktur" ist ein vager Begriff. (Sie haben hier wieder Recht!) Jede Schleife kann als rekursive Funktion ausgedrückt werden: Jede Iteration löst ein Teilproblem für die nachfolgende. Ist jeder Algorithmus mit einer Schleife ein DP? Offensichtlich nicht.

Was die Leute unter "optimale Unterstruktur" und "überlappende Teilprobleme" verstehen, ist, dass die Ergebnisse von Teilproblemen oft genug genutzt werden, um die asymptotische Komplexität von Lösungen zu verringern. Mit anderen Worten, das Memo ist nützlich! In den meisten Fällen ist die subtile Implikation eine Abnahme von exponentieller zu polynomieller Zeit, O (n ^ k) zu O (n ^ p), p & lt; k oder ähnlich.

Beispiel: Es gibt eine exponentielle Anzahl von Pfaden zwischen zwei Knoten in einem dichten Graphen. DP findet den kürzesten Pfad, der nur eine Polynomzahl von ihnen betrachtet, weil die Memos in diesem Fall extrem nützlich sind.

Auf der anderen Seite kann der Reisende Verkäufer als Memo-Funktion ausgedrückt werden (zB siehe diese Diskussion ), wo die Memos einen Faktor von O ((1/2) ^ n) Zeit speichern lassen. Aber die Anzahl der TS-Pfade durch n Städte ist O (n!). Dies ist so viel größer, dass die asymptotische Laufzeit immer noch superexponentiell ist: O (n!) / O (2 ^ n) = O (n!). Solch ein Algorithmus wird im Allgemeinen kein dynamisches Programm genannt, obwohl er für kürzeste Wege dem gleichen Muster wie der DP folgt. Anscheinend ist es nur ein DP, wenn es ein schönes Ergebnis gibt!

Sie können das Problem des reisenden Verkäufers lösen, indem Sie bei jedem Schritt die nächste Stadt auswählen, aber es ist eine falsche Methode.

Die ganze Idee besteht darin, das Problem auf die relativ kleine Menge der Kandidaten für eine optimale Lösung zu beschränken und "rohe Gewalt" zu nutzen, um es zu lösen.

Es ist also besser, dass Lösungen des kleineren Teilproblems ausreichen, um das größere Problem zu lösen.

Dies wird durch eine Rekursion als Funktion der optimalen Lösung kleinerer Teilprobleme ausgedrückt.

Beantworten Sie diese Frage:

  

Ist es sonst möglich? Ich meine, hast du jemals einen Fall gesehen wo?   optimale Lösung für ein Problem enthält keine optimale Lösung für   Teilprobleme.

Nein, das ist nicht möglich und kann sogar bewiesen werden.

Sie können versuchen, dynamische Programmierung für jedes rekursive Problem zu implementieren, aber Sie erhalten kein besseres Ergebnis, wenn es keine optimale Substruktureigenschaft hat. Mit anderen Worten, die dynamische Programmiermethodik ist nicht nützlich, um ein Problem zu implementieren, das keine optimale Substruktureigenschaft aufweist.