Dynamische Programmierung

Dynamische Programmierung ist ein Paradigma des Algorithmenentwurfs, das Probleme mit optimaler Teilstruktur und überlappenden Teilproblemen löst, indem jedes Teilproblem einmal gelöst und sein Ergebnis zur Wiederverwendung gespeichert wird, wodurch exponentielle Neuberechnungen in polynomiale Berechnungen umgewandelt werden.

Definition

Dynamische Programmierung ist eine Methode, die ein Optimierungs- oder Zählproblem löst, indem sie ihren Wert rekursiv in Bezug auf überlappende Teilprobleme definiert und jedes einzelne Teilproblem genau einmal berechnet, wobei das Ergebnis zwischengespeichert wird, damit es wiederverwendet und nicht neu berechnet werden kann.

Scope

Dieses Thema behandelt die beiden Merkmale, die die dynamische Programmierung anwendbar machen – optimale Teilstruktur und überlappende Teilprobleme – sowie die beiden Implementierungsstile, Top-Down-Memoisation und Bottom-Up-Tabellierung. Es umfasst kanonische Probleme wie die längste gemeinsame Teilsequenz, die Editierdistanz, das Rucksackproblem, die Matrixkettenmultiplikation und dynamische Programme für kürzeste Pfade, zusammen mit dem Entwurf des Zustandsraums und der Analyse von Zeit- und Speicherkompromissen. Es schließt graphenspezifische Methoden für kürzeste Pfade aus, die unter Graphenalgorithmen behandelt werden, obwohl sie dasselbe zugrunde liegende Prinzip teilen.

Core questions

• Besitzt das Problem eine optimale Teilstruktur, die es ermöglicht, eine optimale Lösung aus optimalen Teillösungen aufzubauen?
• Wie wird die Menge der Teilprobleme (der Zustandsraum) definiert, sodass jedes nur polynomial oft rekursiv aufgerufen wird?
• Sollte die Lösung Top-Down mit Memoisation oder Bottom-Up mit Tabellierung implementiert werden?
• Wie kann die Tabelle rekonstruiert werden, um die tatsächliche optimale Lösung und nicht nur ihren Wert wiederherzustellen?
• Wie kann der Speicherbedarf reduziert werden, wenn in jedem Schritt nur ein Teil der Tabelle benötigt wird?

Key concepts

• optimale Teilstruktur
• überlappende Teilprobleme
• Optimalitätsprinzip
• Memoisation
• Tabellierung
• Zustandsraum und Rekurrenz
• längste gemeinsame Teilsequenz
• Editierdistanz
• Rucksackproblem

Key theories

Optimalitätsprinzip

Bellmans Optimalitätsprinzip besagt, dass eine optimale Strategie die Eigenschaft hat, dass, unabhängig vom Anfangszustand und der Entscheidung, die verbleibenden Entscheidungen eine optimale Strategie für den resultierenden Zustand darstellen müssen – die formale Grundlage dynamischer Programmierungsrekurrenzen.

Memoisation versus Tabellierung

Ein dynamisches Programm kann Top-Down durch Hinzufügen eines Caches zu einer rekursiven Formulierung (Memoisation) oder Bottom-Up durch das Füllen einer Tabelle in Abhängigkeitsreihenfolge (Tabellierung) realisiert werden; beide berechnen jedes Teilproblem einmal, unterscheiden sich jedoch in der Auswertungsreihenfolge und dem Speicherverhalten.

Clinical relevance

Dynamische Programmierung ist in der Praxis allgegenwärtig: Sequenzalignment (Needleman-Wunsch, Smith-Waterman) in der Computerbiologie, Editierdistanz bei der Rechtschreibprüfung und Versionskontroll-Diffs, der Viterbi-Algorithmus in der Spracherkennung und Kommunikation sowie dynamische Programme in der Operations Research, Finanzwirtschaft und beim Reinforcement Learning.

History

Richard Bellman entwickelte die dynamische Programmierung in den 1950er Jahren bei der RAND Corporation und wählte den Namen teilweise, um für Forschungsförderer akzeptabel zu sein. Das Optimalitätsprinzip und die Bellman-Gleichung wurden grundlegend in der Operations Research, Kontrolltheorie und Informatik, und die Technik wurde später als zentrales algorithmisches Paradigma in Algorithmenlehrbüchern kodifiziert.

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos

Seminal works

• bellman1957
• cormen2009

Frequently asked questions

Was ist der Unterschied zwischen Divide-and-Conquer und dynamischer Programmierung?

Beide zerlegen ein Problem in Teilprobleme, aber bei Divide-and-Conquer sind die Teilprobleme unabhängig und werden einmal gelöst, während sich bei der dynamischen Programmierung die Teilprobleme überlappen und durch naive Rekursion viele Male neu berechnet würden. Die dynamische Programmierung speichert Teillösungen zwischen, um diese Neuberechnung zu vermeiden.

Wann ist die dynamische Programmierung nicht anwendbar?

Sie erfordert eine optimale Teilstruktur und eine polynomial große Menge unterschiedlicher Teilprobleme. Wenn dem Problem eine optimale Teilstruktur fehlt oder wenn der natürliche Zustandsraum exponentiell ist und nicht komprimiert werden kann, ist die dynamische Programmierung entweder inkorrekt oder nicht mehr effizient.