Dynamische Programmierung grob

Dynamische Programmierung speichert Lösungen von Teilproblemen (Tabelle oder Memoization), wenn optimale Teilstruktur und überlappende Teilprobleme vorliegen.

Gegenstück zur naiven verzweigten Rekursion mit Mehrfacharbeit.

Überlappende Teilprobleme: House Robber [1].

$$V(s)=\max_a\bigl(c(s,a)+V(s^{\prime})\bigr)$$

Wo gebraucht

Knapsack, Edit Distance, Parsen, Routing mit Überlappung, viele ML-Decoding-Vorstufen. Memoization ist die Brücke aus der verzweigten Rekursion.

Vertiefung

Dynamische Programmierung speichert Ergebnisse kleiner Zustände, die in der Lösung grösserer Zustände mehrfach benötigt werden. Top-down-Memoisierung folgt der natürlichen Rekursion und berechnet nur erreichte Zustände. Bottom-up-Tabellierung legt eine Reihenfolge fest, in der alle Abhängigkeiten bereits vorliegen.

Die wichtigste Modellierungsarbeit ist die Zustandsdefinition. Sie muss genügend Information für zukünftige Entscheidungen enthalten, aber redundante Historie vermeiden. Übergang, Basiswerte und Auswertungsreihenfolge ergeben sich erst aus dieser Definition.

Schwierigkeitsstufen

1. Wiederkehrende Zustände in einem Rekursionsbaum erkennen.
2. Zustand und Übergang einer kleinen Optimierungsaufgabe formulieren.
3. Speicher durch Abhängigkeitsanalyse auf wenige Zeilen reduzieren.

Fallstricke

Memoisierung eines unvollständigen Schlüssels vermischt verschiedene Situationen. Bei Bottom-up-Verfahren führt eine falsche Füllreihenfolge dazu, dass Übergänge auf noch nicht berechnete Werte zugreifen.