Teilprobleme erkennen und Ergebnisse wiederverwenden
Lesen anpassen
Nach dieser Lektion kannst du
Ein großes Problem durch eindeutig beschriebene Teilprobleme ausdrücken.
Wiederholte Berechnungen von unabhängigen Teilproblemen unterscheiden.
Eine Rekurrenz, ihre Anfangswerte und eine gültige Rechenreihenfolge begründen.
Vorausgesetzt: Laufzeit messen: Operationen zählen und O-Notation
Eine Treppe hat sechs Stufen. Du darfst bei jedem Schritt eine oder zwei Stufen nehmen. Wie viele verschiedene Schrittfolgen führen nach oben? Nur das Ziel zählt nicht: Die Folge „eins, zwei“ unterscheidet sich von „zwei, eins“.
Du könntest alle Möglichkeiten aufschreiben. Bei einer viel längeren Treppe wäre diese Liste aber schnell unübersichtlich. Statt jede vollständige Folge einzeln zu betrachten, schauen wir auf ihren letzten Schritt. Wer oben ankommt, stand unmittelbar davor entweder eine oder zwei Stufen unter dem Ziel.
Damit wird aus einer Frage über sechs Stufen eine Frage über fünf und vier Stufen. Diese kleineren Fragen kommen beim Weiterzerlegen immer wieder vor. Dynamische Programmierung nutzt genau das: Ein Teilproblem wird einmal gelöst, sein Ergebnis gespeichert und anschließend wiederverwendet.
Zustand und Teilproblem
Ein Teilproblem ist eine kleinere, genau beschriebene Frage, aus deren Antwort wir die ursprüngliche Antwort berechnen können. Ein Zustand ist die Information, mit der wir ein solches Teilproblem eindeutig benennen.
Hier beschreibt die Zahl den Zustand. Wir schreiben für die Anzahl der Schrittfolgen, mit denen genau Stufen überwunden werden. Alle Treppen in diesem Modell erlauben dieselben Schritte; die Vorgeschichte verändert die erlaubten nächsten Schritte nicht.
Eine Zustandsbeschreibung ist nur dann ausreichend, wenn zwei Aufrufe mit demselben Zustand wirklich dieselbe Antwort haben. Wären beispielsweise zwei Zweierschritte hintereinander verboten, müssten wir zusätzlich wissen, ob der letzte Schritt ein Zweierschritt war.
Von kleinen Treppen zur allgemeinen Regel
Von kleinen Treppen zur allgemeinen Regel
Für null Stufen gibt es genau eine Schrittfolge: die leere Folge, bei der du nichts tust. Daher setzen wir . Für eine Stufe bleibt nur ein Einerschritt, also .
Für zwei Stufen gibt es „eins, eins“ und „zwei“. Für drei Stufen gibt es „eins, eins, eins“, „eins, zwei“ und „zwei, eins“.
Bei teilen wir alle gültigen Folgen in zwei Gruppen: Folgen mit einem Einerschritt am Ende und Folgen mit einem Zweierschritt am Ende. Entfernen wir den letzten Schritt, bleiben genau die Lösungen für beziehungsweise Stufen.
Die Gruppen überschneiden sich nicht, weil eine Folge nicht gleichzeitig mit einem Einerschritt und einem Zweierschritt enden kann. Zusammen enthalten sie alle Möglichkeiten. Deshalb addieren wir ihre Anzahlen. Eine Regel, die Werte auf kleinere Werte zurückführt, heißt Rekurrenz.
Eine Tabelle statt einer Liste aller Folgen
Eine Tabelle statt einer Liste aller Folgen
Wir beginnen mit den beiden Anfangswerten und rechnen von links nach rechts. Jeder neue Wert ist die Summe der beiden vorherigen Werte.
| Stufen | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Schrittfolgen | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
Die Antwort auf die Ausgangsfrage ist also 13. Für den letzten Eintrag rechnen wir . Wir haben keine der 13 vollständigen Schrittfolgen auflisten müssen.
Die Tabelle ist zugleich eine Darstellung der Abhängigkeiten: Ein Eintrag verwendet nur die beiden Einträge links von ihm. Diese Anordnung liefert eine Rechenreihenfolge, in der jeder benötigte Wert bereits vorliegt.
Überlappende Teilprobleme
Würden wir ohne Speicher rekursiv berechnen, also durch wiederholte Aufrufe derselben Regel, bräuchten wir und . Für wird aber ebenfalls benötigt. Dieselbe Frage würde mehrfach vollständig bearbeitet.
Das nennt man überlappende Teilprobleme. Die Verzweigungen einer rekursiven Berechnung können viele Wiederholungen enthalten, obwohl es nur wenige verschiedene Zustände gibt. Ein gespeicherter Wert von genügt für alle Stellen, die nach fragen.
Nicht jede Zerlegung ist deshalb dynamische Programmierung. Beim gewöhnlichen Mergesort werden zwei getrennte Hälften sortiert; dort ist das Wiederverwenden identischer Teilprobleme nicht die zentrale Idee.
Warum die Tabellenwerte stimmen
Für jede nichtnegative ganze Stufenzahl liefert die Tabelle genau die Anzahl der erlaubten Schrittfolgen.
Für und haben wir die Möglichkeiten vollständig gezählt. Nehmen wir an, die Werte für kleinere Stufenzahlen stimmen. Jede Folge zu endet mit genau einem der beiden erlaubten Schritte.
Das Entfernen dieses Schritts ordnet die Folgen eindeutig einer Lösung für oder zu. Umgekehrt wird jede solche kleinere Lösung durch Anhängen des passenden Schritts zu einer gültigen Folge für . Die Addition zählt daher jede Folge genau einmal. Damit stimmt auch der nächste Tabellenwert. Dieses Argument lässt sich bis zum gewünschten Ziel fortsetzen.
Die Rechenregel allein beschreibt noch keinen Algorithmus
Die Rechenregel allein beschreibt noch keinen Algorithmus
Die Formel sagt noch nicht, wo die Berechnung endet und in welcher Reihenfolge Werte entstehen. Ohne Anfangswerte könnte man immer weiter nach kleineren Werten fragen.
Nenne den Zustand, die Bedeutung jedes Werts, die Anfangswerte, die Übergangsregel und eine Reihenfolge. Hier beginnt die Tabelle mit und wächst anschließend nach rechts. Negative Stufenzahlen werden bei dieser Auswertung gar nicht aufgerufen.
Zusammenfassung
Ein Zustand muss alle Informationen enthalten, die die Antwort auf ein Teilproblem bestimmen.
Für Treppen mit Einser- und Zweierschritten gilt und .
Die Rekurrenz folgt aus einer vollständigen Aufteilung nach dem letzten Schritt.
Überlappende Teilprobleme werden einmal gelöst und anschließend aus dem Speicher gelesen.
Anfangswerte und Rechenreihenfolge gehören ebenso zum Verfahren wie die Formel.
Übungen
Wie viele Schrittfolgen führen mit Einser- und Zweierschritten über genau sieben Stufen?
Warum dürfen wir die Anzahlen für die beiden letzten Schritte addieren?
Zwei Zweierschritte direkt hintereinander sind jetzt verboten. Warum genügt die Stufenzahl allein nicht mehr als Zustand? Beschreibe einen ausreichenden Zustand.
Eine vollständige Tabelle enthält alle Zustände von 0 bis 20 einschließlich. Wie viele Einträge hat sie?