Ein rekursives Optimierungsverfahren für mehrstufige Entscheidungsprobleme, das ein Problem in sich überlappende Teilprobleme zerlegt, einen Zustandsbegriff und das Optimalitätsprinzip nutzt, um den Wert eines Zustands durch Nachfolgerzustände auszudrücken, und optimale Strategien mittels Wert‑ oder Politikiteration, Memoisierung oder Rückwärtsinduktion berechnet.

Prinzip

Eine optimale Lösung eines mehrstufigen Problems lässt sich aus optimalen Lösungen seiner Teilprobleme zusammensetzen (Prinzip der Optimalität); daher führt die Berechnung einer Wertfunktion auf einem geeigneten Zustandsraum zu global optimalen Entscheidungen, wenn Stufenzerlegbarkeit und Markov‑Eigenschaft erfüllt sind.

Demonstration

Illustratives Beispiel: kürzeste Zeit auf einem gerichteten azyklischen Graphen. Situation: jeder Knoten ist eine Stufe, Kantengewichte sind Kosten. Erkennung: Kosten sind stufenweise additiv und zukünftige Kosten hängen nur vom aktuellen Knoten ab. Handlung: minimale Kosten zu Ziel für alle Knoten per Rückwärtsinduktion berechnen (Ergebnisse memoizieren). Folge: die gefundene Strategie liefert den kürzesten Pfad ohne vollständige Aufzählung aller Routen.

Fehlanwendung

Das Anwenden dynamischer Programmierung, obwohl der gewählte Zustand nicht alle relevanten Verläufe kodiert (Verletzung der Markov‑Eigenschaft) oder Teilprobleme nicht überlappen; dies kann zu falschen Entscheidungen oder exponentiellem Zustandswachstum führen, das den Nutzen aufhebt.

Konsequenz

Geregelt angewandt liefert dynamische Programmierung beweisbar optimale Strategien und spart durch Memoisierung Rechnungskosten; bei Fehlgebrauch entstehen falsche Optima oder unbeherrschbare Rechenaufwände (Fluch der Dimensionalität).

Umkehrung

Wenn Stufenzerlegbarkeit, Additivität der Kosten oder die Markov‑Eigenschaft fehlt (z. B. wenn zukünftige Kosten von gesamten Vergangenheitsverläufen abhängen oder nichtseparable Ziele vorliegen), muss die Methode durch Reformulierung, Approximation oder Erweiterung des Zustands ersetzt bzw. ergänzt werden.

Abgrenzung

Eindeutig innerhalb: endlicher Horizont Markov‑Entscheidungsprobleme mit additiven Stufenkosten und eindeutigen Zuständen. Grenzfall: stochastische, teilbeobachtbare Probleme, die eine Umwandlung in Glaubenszustände erfordern. Eindeutig außerhalb: einstufige Optimierung ohne sequentielle Struktur oder Probleme mit unbeschränkter Abhängigkeit von der Vergangenheit.

Semantische Spannung

Optimalität versus Rechnerbarkeit — exakte globale Optimalität durch vollständige Zustandsauflistung steht im Konflikt mit Speicher‑ und Rechenbegrenzungen, was oft Approximationen erzwingt.

Synthese

Dynamische Programmierung tauscht Problestruktur (Stufendecomposition und kompakte Zustandsdefinition) gegen Lösbarkeit: der Erfolg hängt maßgeblich von einer Zustandsdarstellung ab, die zukünftige Kosten markovisch macht und gleichzeitig das Zustandsvolumen beherrschbar hält.