Dynamische Programmierung Schritt für Schritt: die Editierdistanz herleiten

Ziel

Ein Problem lösen, dessen optimale Antwort aus optimalen Antworten kleinerer Instanzen aufgebaut ist und dessen naive Rekursion dieselben Instanzen exponentiell oft neu berechnet, und zwar in polynomialer Zeit und mit vorhersehbarem Speicherbedarf.

Voraussetzungen

Zwei Eigenschaften: optimale Substruktur (die beste Lösung enthält beste Lösungen von Teilproblemen) und überlappende Teilprobleme (die Zahl der unterschiedlichen Teilprobleme ist polynomial, während der naive Aufrufbaum es nicht ist). Das Beispiel: die Editierdistanz zwischen den Zeichenketten a (Länge m) und b (Länge n), die minimale Anzahl einzelner Zeicheneinfügungen, -löschungen und -ersetzungen, die a in b überführt.

Schritte

1. Den Zustand als kleinste Menge von Parametern definieren, die ein Teilproblem identifiziert: D(i, j) ist die Editierdistanz zwischen den ersten i Zeichen von a und den ersten j Zeichen von b. Die Antwort ist D(m, n).
2. Die Basisfälle aufschreiben: D(i, 0) = i (alles löschen) und D(0, j) = j (alles einfügen).
3. Die Rekurrenz aufschreiben. Falls a[i-1] == b[j-1], dann D(i, j) = D(i-1, j-1). Andernfalls D(i, j) = 1 + min(D(i-1, j), D(i, j-1), D(i-1, j-1)), wobei die drei Terme Löschung, Einfügung und Ersetzung entsprechen.
4. Die Zustände zählen: (m+1) * (n+1), jeder in konstanter Zeit aus drei Nachbarn berechnet, sodass der Algorithmus O(mn) ist. Die naive Rekursion besucht D(i-1, j-1) von drei Aufrufern aus erneut und explodiert.
5. Top-down memoisieren: die Rekurrenz wörtlich als rekursive Funktion schreiben und mit @functools.cache dekorieren (dokumentiert in functools neben lru_cache). Das ist der schnellste Weg zu einer korrekten Version, aber die Rekursionstiefe wächst mit m + n, weshalb sich das für kurze Eingaben eignet.
6. Bottom-up tabellieren: eine Tabelle Zeile für Zeile füllen, da jede Zelle nur die Zeile darüber und die Zelle links davon benötigt. Für kitten und sitting endet die Tabelle mit D(6, 7) = 3: k durch s ersetzen, e durch i ersetzen, g einfügen.
7. Speicher senken: nur die vorherige und die aktuelle Zeile behalten, was O(min(m, n)) Speicherplatz ergibt. Die vollständige Tabelle behalten, wenn das tatsächliche Editierskript benötigt wird, und von D(m, n) aus zurückverfolgen.
8. Gegen Brute-Force bei kleinen zufälligen Zeichenketten verifizieren, zusätzlich bei leeren Zeichenketten, identischen Zeichenketten und Ein-Zeichen-Unterschieden.

Erwartetes Ergebnis

Eine Funktion mit quadratischer Zeit und linearem Speicherbedarf, deren Rekurrenz in einem Kommentar neben dem Code steht und gegen ein Brute-Force-Orakel geprüft wurde.

Grenzen und Prüfbasis

Probleme ohne optimale Substruktur (der längste einfache Pfad in einem Graphen) lassen sich mit dieser Methode nicht lösen. Zustandsräume über Teilmengen sind exponentiell in der Grösse der Menge und nur für kleine Eingaben praktikabel. Die Zahlen im Beispiel ergeben sich rechnerisch aus der Rekurrenz; es werden keine Laufzeiten behauptet.