Veröffentlicht · wird verbessert
Algorithm
Dynamische Programmierung speichert die Lösungen überlappender Teilprobleme und verwendet sie wieder – so werden aus exponentiellen Suchen effiziente Tabellen.
Dynamische Programmierung (DP) ist eine Technik des Algorithmenentwurfs: Ein Problem wird in kleinere Teilprobleme zerlegt, jedes Teilproblem wird nur einmal gelöst, das Ergebnis gespeichert und wiederverwendet, sobald dasselbe Teilproblem erneut auftritt. Richard Bellman hat das Verfahren in den 1950er-Jahren formalisiert. Es greift, wenn sich Teilprobleme überlappen und sich eine optimale Lösung aus optimalen Lösungen der Teilprobleme zusammensetzen lässt.
Viele Probleme, die mit einfacher Rekursion oder Brute Force exponentielle Zeit brauchen, lassen sich mit DP in einer Zeit proportional zur Zahl der Zustände lösen. DP steckt in Diff-Werkzeugen, in der Editierdistanz von Rechtschreibprüfungen, im Alignment von DNA-Sequenzen, im Viterbi-Algorithmus der Spracherkennung und in der Join-Reihenfolge von Datenbank-Optimierern. In Programmierinterviews gehört das Thema zu den häufigsten überhaupt.
Zum Einstieg eignet sich Fibonacci, um den Unterschied zwischen Memoisierung (top-down) und Tabellierung (bottom-up) zu verstehen. Danach folgen die Klassiker: Münzwechsel, 0/1-Rucksackproblem, längste aufsteigende Teilfolge, längste gemeinsame Teilfolge und Editierdistanz. Legen Sie bei jeder Aufgabe zuerst Zustand, Rekurrenz, Basisfälle und Berechnungsreihenfolge fest, prüfen Sie die Rekurrenz an einer kleinen Tabelle von Hand und schreiben Sie erst dann den Code.
Tritt dasselbe Teilproblem mehrfach auf, wird es nur einmal berechnet und gespeichert; wiederholte Arbeit wird zum Tabellenzugriff.
Eine optimale Lösung muss sich aus optimalen Lösungen der Teilprobleme aufbauen lassen; diese Eigenschaft begründet die Rekurrenz.
DP wird top-down mit einem Cache für die Rekursion (functools.cache) oder bottom-up mit Schleifen über eine Tabelle umgesetzt.
Der Zustand enthält nur die Parameter, die die Antwort bestimmen; mit rollierenden Arrays bleiben nur die nötigen Zeilen im Speicher.
knapsack löst das 0/1-Rucksackproblem bottom-up mit einer einzigen Zeile und durchläuft die Kapazitäten von groß nach klein, damit jeder Gegenstand höchstens einmal genutzt wird. lcs berechnet die Länge der längsten gemeinsamen Teilfolge top-down, memoisiert mit functools.cache. python dynamic_programming.py gibt 9 und 4 aus.
dynamic_programming.py
from functools import cache
def knapsack(weights, values, capacity):
"""0/1 knapsack: best total value within capacity (bottom-up, one row)."""
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1): # high to low: each item used at most once
best[c] = max(best[c], best[c - w] + v)
return best[capacity]
def lcs(a, b):
"""Length of the longest common subsequence (top-down, memoized)."""
@cache
def solve(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + solve(i + 1, j + 1)
return max(solve(i + 1, j), solve(i, j + 1))
return solve(0, 0)
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9
print(lcs("ABCBDAB", "BDCABA")) # 4
python dynamic_programming.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Dynamische Programmierung.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Dynamische Programmierung aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.