Ein Prinzip der dynamischen Programmierung, das besagt, dass eine optimale Strategie die Eigenschaft hat, dass unabhängig vom Anfangszustand und der ersten Entscheidung die verbleibenden Entscheidungen eine optimale Strategie für den aus der ersten Entscheidung resultierenden Zustand bilden; mit anderen Worten: optimale Lösungen besitzen eine optimale Teilstruktur.

Prinzip

Dass ein Problem in Teilprobleme zerlegt werden kann, deren optimale Lösungen sich so kombinieren lassen, dass ein globales Optimum entsteht, sofern die Zustandsdarstellung alle relevanten Informationen erfasst (Markov-Eigenschaft / optimale Teilstruktur).

Demonstration

Konkretes Beispiel: Kürzester Pfad in einem gerichteten azyklischen Graphen — der kürzeste Pfad von A nach D, der durch B führt, enthält den kürzesten Pfad von B nach D; dynamische Programmierung berechnet Entfernungen, indem sie kleinere Teilpfade löst und zusammensetzt.

Fehlanwendung

Anzunehmen, Bellmans Prinzip gelte, obwohl der Zustand nicht die gesamte notwendige Historie erfasst oder die Kosten von globalen Eigenschaften abhängen (nicht‑Markovsche oder wegabhängige Kosten), führt zu fehlerhafter Zerlegung und suboptimalen Ergebnissen.

Konsequenz

Wenn anwendbar, rechtfertigt es Algorithmen, die optimale Lösungen durch Lösen und Cachen von Teilproblemen aufbauen (dynamische Programmierung, Wertiteration in MDPs) und reduziert oft exponentielle Suche auf polynomiellen Aufwand.

Umkehrung

Die Umkehr ist ein Problem ohne optimale Teilstruktur: Globale optimale Lösungen lassen sich nicht aus optimalen Teilproblem-Lösungen zusammensetzen, dynamische Programmierung ist nicht anwendbar und lokal optimale Entscheidungen können global scheitern.

Abgrenzung

Gilt, wenn der Zustandsraum so definiert ist, dass zukünftige Kosten nur vom aktuellen Zustand und der Entscheidung abhängen und Kosten sich (z. B. additiv) so kombinieren lassen, dass Zusammensetzung möglich ist; schließt nicht‑Markovsche Abhängigkeiten, harte globale Einschränkungen oder nichtdekomponierbare Ziele aus.

Semantische Spannung

Spannung zwischen der Modellierung zur Wiederherstellung optimaler Teilstruktur (Erweiterung des Zustands zur Rückgewinnung der Eigenschaft) und den Kosten/der Komplexität dieser Modellierung; zwischen exakter dyn. Programmierung und approximativen/heuristischen Methoden, wenn strikte Optimalität nicht erreichbar ist.

Synthese

Bellmans Prinzip besagt: Wenn optimale Teilstruktur gilt — d. h. der Zustand enthält alle zukunftsrelevanten Informationen — reduziert sich globale Optimierung auf das Lösen und Zusammensetzen optimaler Teilprobleme, wodurch dynamische Programmierung möglich wird, jedoch bei wegabhängigen oder global beschränkten Problemen versagt.