Mit Google fortfahren
Dynamische Programmierung einfach erklärt
Dynamische Programmierung (DP) löst ein großes Problem mithilfe kleinerer Teilprobleme. Sie speichert deren Ergebnisse und verwendet sie später wieder. Das spart besonders dann Zeit, wenn dieselben Teilprobleme mehrfach auftreten.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Wann passt dynamische Programmierung?
Stell dir vor, ein Algorithmus beantwortet dieselbe kleine Frage immer wieder. DP merkt sich die erste Antwort und ruft sie bei der nächsten Wiederholung nur noch ab.
Eine wichtige Eigenschaft sind wiederkehrende Teilprobleme:
Überlappende Teilprobleme
Während der Lösung treten dieselben Teilprobleme mehrfach auf. Ein gespeichertes Ergebnis kann deshalb mehrfach genutzt werden.
Bei Optimierungsproblemen kommt eine weitere Eigenschaft hinzu:
Optimale Teilstruktur
Bei einem Optimierungsproblem lässt sich eine optimale Gesamtlösung aus optimalen Lösungen passender Teilprobleme zusammensetzen.
Die Eigenschaften müssen zum gewählten Zustand passen. Das bloße Zerlegen eines Problems reicht nicht: Die gespeicherten Antworten müssen später tatsächlich nützlich sein. Bei Problemen wie den Fibonacci-Zahlen steht keine Optimierung im Mittelpunkt; dort genügt eine geeignete Beziehung zwischen wiederkehrenden Teilproblemen.
Wie entsteht ein DP-Algorithmus?
Der wichtigste Entwurfsschritt ist der Zustand. Er beschreibt genau, welche Frage ein gespeicherter Tabellenwert beantwortet.
Gehe in dieser Reihenfolge vor:
- Definiere den Zustand: Was bedeutet ein Eintrag?
- Bestimme die Basisfälle, also direkt bekannte kleinste Fälle.
- Formuliere die Übergangsregel: Aus welchen kleineren Zuständen entsteht der nächste?
- Lege eine Reihenfolge fest, in der alle benötigten Vorgänger schon berechnet sind.
- Lies am Zielzustand das Ergebnis ab.
- Speichere bei Bedarf zusätzlich Vorgänger, wenn du nicht nur den optimalen Wert, sondern auch die konkrete Lösung brauchst.
Beim Rasterproblem kann ein Zustand lauten: „minimaler Preis vom Start bis zu dieser Zelle“. Für eine innere Zelle sind der Wert oberhalb und der Wert links davon die Vorgänger. Erst wenn beide bekannt sind, wird die Zelle berechnet.
Ein Tabellenfeld ist erst dann verständlich, wenn du seinen Zustand in einem vollständigen Satz erklären kannst.
Wie macht DP Fibonacci schneller?
Die Fibonacci-Folge beginnt mit $f_0=0$ und $f_1=1$. Danach gilt:
$$f_{i+2}=f_i+f_{i+1}$$
Eine naive rekursive Funktion berechnet für $n>1$ sowohl $f_{n-1}$ als auch $f_{n-2}$. Dabei entstehen Wiederholungen: Bei $f_4$ wird beispielsweise $f_2$ zweimal berechnet. Mit wachsendem $n$ wächst die Zahl der Aufrufe exponentiell.
Bottom-up beginnt bei den Basisfällen und füllt die Werte der Reihe nach:
| Index $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| $f_i$ | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
Gesucht ist $f_6$.
- Starte mit $f_0=0$ und $f_1=1$.
- Addiere jeweils die beiden vorherigen Werte: $f_2=0+1=1$, $f_3=1+1=2$ und $f_4=1+2=3$.
- Fahre fort: $f_5=2+3=5$ und $f_6=3+5=8$.
- Ergebnis: Die Fibonacci-Zahl mit Index 6 ist $8$.
Jeder benötigte Wert wird genau einmal erzeugt. Die Laufzeit ist daher $O(n)$ statt exponentiell.
Für den Ergebniswert allein brauchst du nicht die ganze Tabelle. Da jeder neue Wert nur von den beiden Vorgängern abhängt, genügen zwei gespeicherte Zahlen. Das ist eine problembezogene Speicheroptimierung.
Top-down oder Bottom-up?
Beide Varianten verwenden gespeicherte Teilergebnisse, aber sie starten an unterschiedlichen Stellen.
| Variante | Start | Vorgehen | Speicher |
|---|---|---|---|
| Top-down mit Memoisierung | Gesamtproblem | Rekursiv nur benötigte Teilprobleme lösen und Ergebnisse zwischenspeichern | Cache und Aufrufstapel |
| Bottom-up | Basisfälle | Tabelle in einer gültigen Abhängigkeitsreihenfolge füllen | Tabelle; manchmal auf wenige Vorgänger reduzierbar |
Memoisierung bedeutet: Eine rekursive Funktion prüft zuerst den Cache. Ist das Ergebnis schon vorhanden, gibt sie es direkt zurück. Andernfalls berechnet und speichert sie es.
Keine Variante ist immer überlegen. Der passende Weg hängt von den tatsächlich benötigten Zuständen, ihren Abhängigkeiten und dem Speicherbedarf ab.
Warum kann Greedy im Raster scheitern?
Im Raster startest du oben links und gehst nur nach rechts oder unten. Jedes Feld trägt einen Kostenwert. Für den Vergleich sind zwei vollständige Pfadsummen gegeben.
Der Greedy-Weg, der jeweils das unmittelbar billigere Nachbarfeld wählt, kostet:
$$3+7+9+4+2+1+2=28$$
Der optimale Weg kostet dagegen:
$$3+10+3+1+3+1+2=23$$
Die lokal teurere frühe Wahl mit Kosten $10$ führt später zu günstigeren Feldern. Eine lokal beste Entscheidung garantiert hier also keine global beste Lösung.
Für DP speichert jede Zelle die minimalen Kosten vom Start bis zu ihr. Bei einer inneren Zelle gilt in Worten:
Zellkosten plus der kleinere gespeicherte Wert von oben oder links.
Oberste Zeile und linke Spalte haben jeweils nur einen möglichen Vorgänger und werden zuerst gefüllt. Ob der Kostenwert der Startzelle mitgezählt wird, muss für alle verglichenen Wege einheitlich festgelegt werden.
Eine Zelle kostet $7$. Der günstigste Weg zum oberen Vorgänger kostet $3$, zum linken $15$.
- Vergleiche die Vorgänger: $3<15$.
- Wähle den oberen Vorgänger.
- Addiere die Zellkosten: $3+7=10$.
Der minimale Preis bis zu dieser Zelle beträgt $10$.
Wie prüfst du einen eigenen DP-Entwurf?
Nutze diese Entscheidungshilfe:
- Wiederholen sich dieselben Teilfragen?
- Kannst du jeden Zustand eindeutig benennen?
- Sind die Basisfälle korrekt und direkt lösbar?
- Verwendet die Übergangsregel nur passende kleinere Zustände?
- Stehen diese Zustände beim Berechnen bereits fest?
- Liefert der Zielzustand wirklich die gesuchte Antwort?
- Ist der zusätzliche Speicher den Laufzeitgewinn wert?
DP kann viel Rechenzeit sparen, benötigt aber oft Speicher für viele Zustände. Bei sehr vielen Zuständen kann auch ein DP-Algorithmus aufwendig bleiben. Eine unpassende Zustandswahl macht die Tabelle groß oder ihre Einträge nutzlos.
Eine DP-Tabelle kann eindimensional sein wie bei Fibonacci oder zweidimensional wie bei Rasterwegen und dem Rucksackproblem. Ihre Form folgt dem Zustand, nicht einer festen DP-Regel.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Dynamische Programmierung
- Voraussetzungen
- wiederkehrende Teilprobleme
- bei Optimierung: optimale Teilstruktur
- Entwurf
- Zustand und Basisfälle
- Übergangsregel und Reihenfolge
- Umsetzung
- Top-down mit Memoisierung
- Bottom-up mit Tabelle
- Bewertung
- Laufzeitgewinn
- Speicherbedarf
- Voraussetzungen