Dynamische Programmierung und Memoization in C#

Problem

Der Ladeplan

Ein Kurier fährt einen Elektroroller auf einer Strecke von n km. An jedem Kilometer gibt es eine Ladestation, und der Akku hält höchstens 2 km. Von jedem Halt aus fährt der Kurier also 1 oder 2 km weiter bis zum nächsten. An jeder Station, an der er hält, zahlt er ihre Gebühr. Die Gebühren sind verschieden, und die App muss den günstigsten Plan finden.

Die erste Lösung denkt rückwärts. Der letzte Halt ist km n. Davor war der Kurier bei km n − 1 oder bei km n − 2. Das Günstigste bis n ist also die Gebühr bei n plus das Günstigere von beiden: das Günstigste bis n − 1 und das Günstigste bis n − 2. Das ist Rekursion, wie in der Lektion „Rekursion“. Die Gebühren sind in Cent, und der Zähler sagt, wie oft die Funktion aufgerufen wurde:

static long calls = 0;

static int[] Fees(int n)
{
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int Cheapest(int[] fee, int i)
{
    calls++;
    if (i <= 1)
    {
        return fee[i];
    }
    int oneBack = Cheapest(fee, i - 1);
    int twoBack = Cheapest(fee, i - 2);
    return fee[i] + Math.Min(oneBack, twoBack);
}

foreach (int km in new[] { 10, 30 })
{
    calls = 0;
    int cost = Cheapest(Fees(km), km);
    Console.WriteLine($"{km} km: {cost} Cent, {calls} Aufrufe");
}

10 km: 381 Cent, 177 Aufrufe
30 km: 1217 Cent, 2692537 Aufrufe

Die Antwort stimmt, aber für 30 km wurde die Funktion 2.692.537-mal aufgerufen. Für 50 km wären es 40.730.022.147 Aufrufe: Bei einer Milliarde Aufrufe pro Sekunde ist das mehr als eine halbe Minute, und eine Kurierstrecke kann 100 km lang sein.

Die Idee

Dieselbe Frage, millionenfach gestellt

Warum so viele? Verfolge, wer wen fragt. Das Günstigste bis km 30 fragt nach km 29 und km 28. Km 29 fragt nach 28 und 27. Km 28 wird zweimal gefragt, und jedes Mal wird es von Grund auf berechnet, samt allem darunter. Weiter unten häufen sich die Wiederholungen: Km 27 wird dreimal gefragt, km 26 fünfmal.

Das saubere Beispiel dafür sind die Fibonacci-Zahlen: Jede ist die Summe der zwei vorigen, 0, 1, 1, 2, 3, 5, 8 … Die Funktion hat dieselbe Form, die zwei kleineren und eine Summe:

static long Fib(int n)
{
    calls++;
    if (n <= 1)
    {
        return n;
    }
    return Fib(n - 1) + Fib(n - 2);
}

Fib(30) = 832040, 2692537 Aufrufe

Die Zahl der Aufrufe ist bis auf die letzte Ziffer dieselbe, weil der Aufrufbaum derselbe ist. Und der Plan ist nur eine von vielen Stellen mit diesem Baum.

Solche Teilprobleme heißen überlappend: Dasselbe kleinere Problem wird von mehreren größeren gebraucht. Bei Teile und herrsche ist es nicht so. Mergesort teilt die Bestellungen in zwei Hälften, die keine einzige Bestellung gemeinsam haben, und jedes Stück wird einmal gelöst. Hier wird „das Günstigste bis km 28“ von km 29 und von km 30 gebraucht.

Sieh es dir an

Der Baum und der Speicher

Der ganze Aufrufbaum für 6 km, dann dasselbe mit Speicher. Achte darauf, welche Kästchen sich wiederholen und was mit ihnen passiert, sobald ihre Antwort gemerkt ist:

static int CheapestMemo(int[] fee, int i, int[] memo)
{
    if (i <= 1)
    {
        return fee[i];
    }
    if (memo[i] != -1)
    {
        return memo[i];
    }
    int oneBack = CheapestMemo(fee, i - 1, memo);
    int twoBack = CheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.Min(oneBack, twoBack);
    return memo[i];
}

static int Cheapest(int[] fee, int i)
{
    if (i <= 1)
    {
        return fee[i];
    }
    int oneBack = Cheapest(fee, i - 1);
    int twoBack = Cheapest(fee, i - 2);
    return fee[i] + Math.Min(oneBack, twoBack);
}

static int CheapestTable(int[] fee)
{
    int n = fee.Length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++)
    {
        int cheaper = Math.Min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

static int CheapestPair(int[] fee)
{
    int twoBack = fee[0];
    int oneBack = fee[1];
    for (int i = 2; i < fee.Length; i++)
    {
        int here = fee[i] + Math.Min(oneBack, twoBack);
        twoBack = oneBack;
        oneBack = here;
    }
    return oneBack;
}

Schritt für Schritt, in Worten

Jedes Kästchen ist ein Aufruf Cheapest(k): der günstigste Weg bis km k. Cheapest(6) fragt nach 5 und 4, und jeder von ihnen fragt nach zwei kleineren.
Der Baum endet bei km 1 und 0, wo die Antwort die Gebühr selbst ist. Für 6 km sind das 25 Aufrufe.
Immer wieder dieselben Fragen: Cheapest(4) zweimal, Cheapest(3) dreimal, Cheapest(2) fünfmal. Die Teilprobleme überlappen sich.
Mit Speicher: Die Aufrufe laufen in derselben Reihenfolge, und wenn eine Antwort zum ersten Mal berechnet ist, kommt sie unten in memo.
Beim zweiten Mal steht die Antwort schon in memo (grün): Der ganze Teilbaum darunter läuft gar nicht. 11 Aufrufe statt 25.
Eine Tabelle von unten nach oben: best[0] und best[1] sind die Gebühren, und jede weitere Zelle wird aus den zwei davor gebaut. 5 Zellen, keine Rekursion.
Jede Zelle braucht nur die letzten zwei. Zwei Variablen gleiten statt der Tabelle vorwärts: O(n) Zeit und O(1) Speicher.

Die Idee

Die Antwort merken

Die Lösung ist, dasselbe nicht zweimal zu berechnen. Beim ersten Mal, wenn du das Günstigste bis km k berechnest, schreib es auf. Fragt das nächste Mal jemand nach k, gib zurück, was du aufgeschrieben hast.

static long calls = 0;

static int[] Fees(int n)
{
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int CheapestMemo(int[] fee, int i, int[] memo)
{
    calls++;
    if (i <= 1)
    {
        return fee[i];
    }
    if (memo[i] != -1)
    {
        return memo[i];
    }
    int oneBack = CheapestMemo(fee, i - 1, memo);
    int twoBack = CheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.Min(oneBack, twoBack);
    return memo[i];
}

int[] fee = Fees(30);
int[] memo = new int[fee.Length];
Array.Fill(memo, -1);
int cost = CheapestMemo(fee, 30, memo);
Console.WriteLine($"{cost} Cent, {calls} Aufrufe");

1217 Cent, 59 Aufrufe

Der Speicher ist ein Array mit einem Platz für jeden Kilometer. -1 bedeutet „noch nicht berechnet“: Die Gebühren sind positiv, also ist eine echte Antwort nie -1.

Das heißt Memoization (sich die Ergebnisse merken). Die Funktion ist dieselbe Rekursion, nur mit Speicher. 59 Aufrufe statt 2.692.537: Jeder Kilometer wird einmal berechnet, und die zweite Frage danach gibt die fertige Antwort zurück.

Ein Problem, das aus den Antworten kleinerer Probleme gebaut wird, wenn sich diese kleineren wiederholen, löst man mit dynamischer Programmierung: Jedes Teilproblem wird einmal gelöst und seine Antwort behalten. Der Name ist alt und sagt nicht viel. Merk ihn dir als „merken und wiederverwenden“.

Probier es aus

Sag die Ausgabe voraus

Dieselbe Funktion mit Speicher, für eine Strecke von 8 km. Wie oft wird sie aufgerufen?

static long calls = 0;

static int[] Fees(int n)
{
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int CheapestMemo(int[] fee, int i, int[] memo)
{
    calls++;
    if (i <= 1)
    {
        return fee[i];
    }
    if (memo[i] != -1)
    {
        return memo[i];
    }
    int oneBack = CheapestMemo(fee, i - 1, memo);
    int twoBack = CheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.Min(oneBack, twoBack);
    return memo[i];
}

int[] fee = Fees(8);
int[] memo = new int[fee.Length];
Array.Fill(memo, -1);
int cost = CheapestMemo(fee, 8, memo);
Console.WriteLine($"{cost} Cent, {calls} Aufrufe");

Antwort

331 Cent, 15 Aufrufe

331 Cent, 8 Aufrufe

331 Cent, 67 Aufrufe

Die Idee

Von unten nach oben

Die Rekursion mit Speicher beginnt bei km n und geht nach unten, bis sie die kleinen erreicht. Du kannst auch den anderen Weg gehen: mit den kleinen anfangen und hinaufsteigen. Das Günstigste bis km 0 und km 1 ist die Gebühr selbst. Daraus folgt km 2, dann km 3 und so weiter bis n. Wenn du eine Zelle erreichst, sind die zwei darunter schon fertig.

static int CheapestTable(int[] fee)
{
    int n = fee.Length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++)
    {
        int cheaper = Math.Min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

Das ist die dynamische Programmierung von unten nach oben, mit einer Tabelle. Es gibt keine Rekursion und keine Prüfung „schon berechnet?“: Die Reihenfolge der Schleife garantiert, dass alles Nötige schon in der Tabelle steht. Es gibt n − 1 Zellen, mit einem Stück Arbeit pro Zelle: O(n).

Noch eine Beobachtung. Zelle i schaut nur auf i − 1 und i − 2. Alles davor wird nicht mehr gebraucht. Die ganze Tabelle kann also zu zwei Variablen werden, die vorwärts gleiten:

static int CheapestPair(int[] fee)
{
    int twoBack = fee[0];
    int oneBack = fee[1];
    for (int i = 2; i < fee.Length; i++)
    {
        int here = fee[i] + Math.Min(oneBack, twoBack);
        twoBack = oneBack;
        oneBack = here;
    }
    return oneBack;
}

int[] fee = Fees(30);
Console.WriteLine($"Tabelle: {CheapestTable(fee)} Cent");
Console.WriteLine($"zwei Variablen: {CheapestPair(fee)} Cent");

Tabelle: 1217 Cent
zwei Variablen: 1217 Cent

Die Zeit ist immer noch O(n) und der Speicher O(1): zwei Zahlen, egal wie lang die Strecke.

Sieh es dir an

Miss es: ohne Speicher, mit Speicher, mit Tabelle

Lass alle drei auf Strecken von 10, 20 und 30 km laufen. Wir zählen die Aufrufe der Funktion und bei der Tabelle die Zellen. Die Rekursion ohne Speicher wird über 30 km nicht ausgeführt: Bei 40 km sind es 331.160.281 Aufrufe, und die Seite würde einfrieren.

Rekursion ohne Gedächtnis O(2ⁿ)
Rekursion mit Gedächtnis O(n)
Tabelle, von unten nach oben O(n)

Algorithmus	n = 10	n = 20	n = 30
Rekursion ohne Gedächtnis	177	21.891	2.692.537
Rekursion mit Gedächtnis	19	39	59
Tabelle, von unten nach oben	9	19	29

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

static int CheapestMemo(int[] fee, int i, int[] memo)
{
    if (i <= 1)
    {
        return fee[i];
    }
    if (memo[i] != -1)
    {
        return memo[i];
    }
    int oneBack = CheapestMemo(fee, i - 1, memo);
    int twoBack = CheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.Min(oneBack, twoBack);
    return memo[i];
}

Alle 10 km vervielfacht sich die Rekursion ohne Speicher um etwa das 123-Fache, während die anderen zwei um 20 und um 10 wachsen. Die Kurve in Bench ist mit O(2ⁿ) beschriftet: Sie ist exponentiell, mit einer Basis von etwa 1,6, dem Verhältnis zweier benachbarter Fibonacci-Zahlen.

Genauer, für Neugierige

Dieselben Zahlen in deiner Sprache: die Aufrufe ohne Speicher, mit Speicher und die Tabellenzellen für 10, 20 und 30 km.

static long calls = 0;
static long cells = 0;

static int[] Fees(int n)
{
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int Cheapest(int[] fee, int i)
{
    calls++;
    if (i <= 1)
    {
        return fee[i];
    }
    int oneBack = Cheapest(fee, i - 1);
    int twoBack = Cheapest(fee, i - 2);
    return fee[i] + Math.Min(oneBack, twoBack);
}

static int CheapestMemo(int[] fee, int i, int[] memo)
{
    calls++;
    if (i <= 1)
    {
        return fee[i];
    }
    if (memo[i] != -1)
    {
        return memo[i];
    }
    int oneBack = CheapestMemo(fee, i - 1, memo);
    int twoBack = CheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.Min(oneBack, twoBack);
    return memo[i];
}

static int CheapestTable(int[] fee)
{
    int n = fee.Length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++)
    {
        cells++;
        int cheaper = Math.Min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

foreach (int km in new[] { 10, 20, 30 })
{
    int[] fee = Fees(km);
    calls = 0;
    Cheapest(fee, km);
    long plain = calls;
    calls = 0;
    int[] memo = new int[fee.Length];
    Array.Fill(memo, -1);
    CheapestMemo(fee, km, memo);
    cells = 0;
    int cost = CheapestTable(fee);
    Console.WriteLine($"{km} km: {plain} / {calls} / {cells}, {cost} Cent");
}

10 km: 177 / 19 / 9, 381 Cent
20 km: 21891 / 39 / 19, 822 Cent
30 km: 2692537 / 59 / 29, 1217 Cent

Probier es aus

Finde den Fehler

Ein Kollege hat die Funktion mit Speicher geschrieben. Die Antwort stimmt, aber der Zähler zeigt dasselbe wie ohne Speicher:

int[] fee = Fees(30);
int[] memo = new int[fee.Length];
Array.Fill(memo, -1);
int cost = CheapestMemo(fee, 30, memo);
Console.WriteLine($"{cost} Cent, {calls} Aufrufe");

1217 Cent, 2692537 Aufrufe

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Probier es aus

Ergänze

Zelle i in der Tabelle ist die Gebühr bei km i plus das Günstigere der zwei Orte, von denen du kommen kannst. Was ist der zweite?

static int CheapestTable(int[] fee)
{
    int n = fee.Length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++)
    {
        int cheaper = Math.Min(best[i - 1], );
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

Übung

Die Gebühren aus der Eingabe

Löse die Aufgabe in deinem Editor.

Der günstigste Plan. Lies die Stationsgebühren von km 1 bis km n (in Cent, durch Leerzeichen getrennt) ein und gib den günstigsten Plan aus. Nutze CheapestPair aus der Lektion.

77 114 61 98 45 82

Am günstigsten: 265 Cent

Weitere Aufgaben

Welche Stationen. Gib auch die Kilometer aus, an denen der Kurier hält. Tipp: Merke dir neben der Tabelle, woher jede Zelle kam (i − 1 oder i − 2), und geh dann von n zurück.
Wie viele Pläne. Zähle alle Pläne, egal was sie kosten. Wie viele sind es für 30 km? Vergleiche die Zahlen mit den Fibonacci-Zahlen. (Für 30 km gibt es 1.346.269.)
Ein besserer Akku. Der neue Roller hält 3 km. Wie ändert sich die Formel, und wie viele Variablen brauchst du statt zwei?

Genauer

Die Tiefe und der eingebaute Speicher

Speicher senkt die Arbeit, aber die Rekursion bleibt Rekursion.

Genauer, für Neugierige

Wie tief es geht. Die Rekursion mit Speicher geht zuerst die Kette n, n − 1, … 1 hinunter und beginnt erst dann zu speichern. Der Aufrufstapel hat n Frames, wie in der Lektion „Der Aufrufstapel von innen“. Die Tabelle macht dieselbe Arbeit in einer Schleife, und der Stapel wächst nicht, wie in „Von der Rekursion zur Schleife“.

In C# lässt sich ein Stapelüberlauf nicht abfangen: StackOverflowException beendet den ganzen Prozess, deshalb gibt es hier kein Programm. Die Rekursion mit Speicher für 100.000 km würde das auslösen, während die Tabelle funktioniert. Java, Python und JavaScript liefern einen Fehler, der sich abfangen lässt.

In die Sprache eingebauter Speicher. C# hat keinen eingebauten Speicher für Funktionen. Ein Array, wie hier, oder ein Dictionary<int, int> mit TryGetValue erledigt es. Für einen Schlüssel aus mehreren Zahlen funktioniert ein Tupel: Dictionary<(int, int), long>.

Von oben nach unten oder von unten nach oben. Beide Wege lösen dieselben Teilprobleme. Mit Speicher berechnet man nur die, die man wirklich erreicht, und schreibt es direkt aus der naiven Rekursion. Mit einer Tabelle gibt es keine Rekursion, und man kann sie oft verkleinern wie hier. Sind die Teilprobleme viele und die Antwort braucht nur wenige davon, gewinnt der Speicher. Werden fast alle gebraucht, ist die Tabelle schneller und riskiert den Stapel nicht.

Test

Teste dich

1. Warum macht die Rekursion ohne Speicher 2,7 Millionen Aufrufe für 30 km und mit Speicher nur 59?Mit Speicher überspringt die Funktion die Kilometer, die sie nicht brauchtOhne Speicher werden dieselben Teilprobleme (das Günstigste bis km 5, bis km 4 …) jedes Mal neu gelöst, wenn jemand danach fragtSpeicher macht jeden Aufruf schneller

2. Wie unterscheidet sich die dynamische Programmierung von „Teile und herrsche“ beim Mergesort?Beim Mergesort überlappen sich die Hälften nicht, und jedes Teilproblem wird einmal ohne Speicher gelöst; hier wiederholen sich die Teilprobleme, und es lohnt sich, sie zu merkenMergesort benutzt eine Tabelle und die dynamische Programmierung nichtDie dynamische Programmierung teilt immer in der Mitte

3. Die Tabelle für n km wird von best[2] bis best[n] gefüllt. Wie viel Speicher braucht die Version mit zwei Variablen?O(log n)O(1): nur die letzten zwei WerteO(n): die ganze Tabelle

4. Eine Funktion mit Speicher prüft den Speicher, schreibt aber nie hinein. Was passiert?Die Antwort stimmt, aber es gibt genauso viele Aufrufe wie ohne SpeicherDie Antwort ist falschDie Funktion hört nie auf

5. Warum scheitert die Rekursion mit Speicher in Python bei 5000 km, während die Tabelle funktioniert?Der Speicher von Python reicht für 5000 Zahlen nichtMit Speicher geht der erste Aufruf 5000 Ebenen tief, bevor er etwas speichert, und das Limit in Python sind 1000 Ebenen; die Tabelle ist eine Schleife ohne RekursionDie Tabelle benutzt kleinere Zahlen

Überlappende Teilprobleme

Cookies