Lektion 5.1

Teilprobleme erkennen und Ergebnisse wiederverwenden

16 min Lesezeit
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.

Definition

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 kk den Zustand. Wir schreiben T(k)T(k) für die Anzahl der Schrittfolgen, mit denen genau kk 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.

Beispiel

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 T(0)=1T(0)=1. Für eine Stufe bleibt nur ein Einerschritt, also T(1)=1T(1)=1.

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 k≥2k\ge 2 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 k−1k-1 beziehungsweise k−2k-2 Stufen.

T(k)=T(k−1)+T(k−2)(k≥2)T(k)=T(k-1)+T(k-2)\qquad(k\ge 2)

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.

Beispiel

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 kk0123456
Schrittfolgen T(k)T(k)11235813

Die Antwort auf die Ausgangsfrage ist also 13. Für den letzten Eintrag rechnen wir T(6)=T(5)+T(4)=8+5=13T(6)=T(5)+T(4)=8+5=13. 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.

Definition

Überlappende Teilprobleme

Würden wir T(6)T(6) ohne Speicher rekursiv berechnen, also durch wiederholte Aufrufe derselben Regel, bräuchten wir T(5)T(5) und T(4)T(4). Für T(5)T(5) wird aber ebenfalls T(4)T(4) 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 T(4)T(4) genügt für alle Stellen, die nach T(4)T(4) 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.

Satz

Warum die Tabellenwerte stimmen

Für jede nichtnegative ganze Stufenzahl kk liefert die Tabelle genau die Anzahl der erlaubten Schrittfolgen.

Häufige Fehler

Die Rechenregel allein beschreibt noch keinen Algorithmus

Die Formel T(k)=T(k−1)+T(k−2)T(k)=T(k-1)+T(k-2) sagt noch nicht, wo die Berechnung endet und in welcher Reihenfolge Werte entstehen. Ohne Anfangswerte könnte man immer weiter nach kleineren Werten fragen.

Richtig ist

Nenne den Zustand, die Bedeutung jedes Werts, die Anfangswerte, die Übergangsregel und eine Reihenfolge. Hier beginnt die Tabelle mit T(0)=T(1)=1T(0)=T(1)=1 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 T(0)=T(1)=1T(0)=T(1)=1 und T(k)=T(k−1)+T(k−2)T(k)=T(k-1)+T(k-2).

  • 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

Aufgabe 1Numerisch

Wie viele Schrittfolgen führen mit Einser- und Zweierschritten über genau sieben Stufen?

Aufgabe 2Multiple Choice

Warum dürfen wir die Anzahlen für die beiden letzten Schritte addieren?

Aufgabe 3Freitext

Zwei Zweierschritte direkt hintereinander sind jetzt verboten. Warum genügt die Stufenzahl allein nicht mehr als Zustand? Beschreibe einen ausreichenden Zustand.

Aufgabe 4Numerisch

Eine vollständige Tabelle enthält alle Zustände von 0 bis 20 einschließlich. Wie viele Einträge hat sie?