Schlüsselprinzipien der dynamischen Programmierung (DP)
Die dynamische Programmierung ist eine algorithmische Technik, mit der Optimierungsprobleme gelöst werden, indem sie in kleinere, überlappende Unterprobleme, das Lösen jedes Teilproblems, nur einmal unterteilt und die Ergebnisse gespeichert werden, um redundante Berechnungen zu vermeiden. Es ist besonders gut geeignet für Probleme, die optimale Unterstruktur aufweisen und überlappende Unterprobleme .
Hier ist eine Aufschlüsselung seiner Schlüsselprinzipien:
1. optimale Unterstruktur:
- Ein Problem weist eine optimale Unterstruktur auf, wenn eine optimale Lösung für das Problem aus optimalen Lösungen für seine Teilprobleme erstellt werden kann. Wenn Sie die optimale Lösung für jedes kleinere Stück kennen, können Sie sie zusammenstellen, um die allgemeine optimale Lösung zu bilden.
- Beispiel: Der kürzeste Weg zwischen zwei Städten in einem Diagramm hat eine optimale Unterstruktur. Jeder Unterweg des kürzesten Weges muss auch der kürzeste Weg zwischen seinen Endpunkten sein.
2. Überlappende Unterprobleme:
- Das Problem kann in Unterprobleme unterteilt werden, die in der Berechnung mehrfach wiederverwendet werden. Dies bedeutet, dass dieselben Unterprobleme wiederholt gelöst werden, wenn ein naiver rekursiver Ansatz verwendet wird.
- Beispiel: Durch die Berechnung der n -ten Fibonacci -Zahl wird rekursiv die wiederholte Berechnung kleinerer Fibonacci -Zahlen (z. B. Fib (3) bei der Berechnung von FIB (5)) mehrmals berechnet.
3..
- Memoisierung (Top-Down): Dieser Ansatz beginnt mit dem ursprünglichen Problem und unterteilt ihn rekursiv in Unterprobleme. Die Ergebnisse jedes gelösten Unterproblems werden (normalerweise in einem Wörterbuch oder einer Hash -Karte) gespeichert, um eine Neubearbeitung zu vermeiden. Wenn zum zweiten Mal ein Teilproblem aufgetaucht ist, wird das gespeicherte Ergebnis einfach nachgeschlagen und zurückgegeben.
- Tabulierung (Bottom-up): Dieser Ansatz berechnet die Lösungen systematisch auf alle möglichen Unterprobleme auf Bottom-up-Weise, beginnend mit den kleinsten Unterproblemen und dem Aufbau des ursprünglichen Problems. Die Ergebnisse werden typischerweise in einer Tabelle (z. B. ein Array oder eine Matrix) gespeichert.
4. Zustand:
- Ein Zustand repräsentiert eine spezifische Konfiguration des Problems, das gelöst werden muss. Die Definition des Staates ist entscheidend für die Gestaltung einer DP -Lösung. Der Staat sollte alle Informationen erfassen, die erforderlich sind, um ein Teilproblem unabhängig von anderen Teilproblemen zu lösen. Die Anzahl der Zustände bestimmt typischerweise die Raumkomplexität der DP -Lösung.
- Beispiel: Im Rucksack -Problem könnte ein Zustand als "(Index, Kapazität) definiert werden, wobei" Index "die bisher berücksichtigten Elemente darstellt und" Kapazität "die verbleibende Kapazität des Rucksacks darstellt.
5. Übergänge:
- Übergänge sind die Regeln, die beschreiben, wie die Lösung für einen bestimmten Zustand berechnet werden, der auf den Lösungen für ihre Unterprobleme basiert. Diese Regeln definieren die Beziehung zwischen den verschiedenen Zuständen und ermöglichen es Ihnen, die Lösung aus kleineren Unterproblemen aufzubauen. Die Übergänge werden typischerweise als rekursive Gleichungen ausgedrückt.
- Beispiel: In der Fibonacci-Sequenz ist der Übergang `fib (n) =fib (n-1) + fib (n-2)`.
Anwendungen der dynamischen Programmierung
Dynamische Programmierung wird in verschiedenen Domänen ausgiebig verwendet. Hier sind einige bemerkenswerte Anwendungen:
1. Optimierungsprobleme:
* kürzeste Pfadalgorithmen:
* Floyd-warshall-Algorithmus: Findet die kürzesten Pfade zwischen allen Eckpaaren in einem gewichteten Diagramm.
* Bellman-Ford-Algorithmus: Findet den kürzesten Pfad von einem Quellscheitelpunkt zu allen anderen Scheitelpunkten in einem gewichteten Graphen, auch mit negativen Kantengewichten (erfasst negative Zyklen).
* Rucksack Problem: Ermittelt die wertvollsten Gegenstände in einen Rucksack, ohne die Gewichtskapazität zu überschreiten. Zu den Variationen gehören 0/1 Rucksack, unbegrenzter Rucksack und Fractional Rucksack.
* längste gemeinsame Subsequenz (LCS): Findet die längste Folge von Zeichen, die zwei oder mehr Saiten gemeinsam sind. Wird in Bioinformatik (Sequenzausrichtung), Dateivergleich und Textbearbeitung verwendet.
* Matrixkette Multiplikation: Bestimmt die optimale Reihenfolge, um eine Abfolge von Matrizen zu multiplizieren, um die Anzahl der Skalarmultiplikationen zu minimieren.
* Distanz bearbeiten (Levenshtein -Abstand): Berechnet die minimale Anzahl von Änderungen (Insertionen, Löschungen, Substitutionen), die erforderlich sind, um eine Zeichenfolge in eine andere zu verwandeln. Wird in Zaubersprüchen, DNA -Sequenzierung und natürlicher Sprachverarbeitung verwendet.
* Münzveränderung Problem: Findet die minimale Anzahl von Münzen, die erforderlich sind, um einen bestimmten Betrag zu erzielen, oder die Anzahl der Möglichkeiten, einen bestimmten Betrag mit einer Reihe von Münzen zu erstellen.
* Reiseverkäufer Problem (TSP) (Hold-Karp-Algorithmus): Findet die kürzeste Route, die jede Stadt genau einmal besucht und in die Origin City zurückkehrt. Während DP eine * exakte * Lösung für kleine Instanzen liefert, ist sie für große Instanzen nicht praktisch (NP-HART).
2. Sequenzanalyse:
* Sequenzausrichtung (Bioinformatik): Ausrichtung von DNA- oder Proteinsequenzen, um Ähnlichkeiten und Unterschiede zu identifizieren, und häufig mit Algorithmen wie Needleman-Wunsch (Global Alignment) und Smith-Waterman (lokale Ausrichtung).
* Hidden Markov -Modelle (HMMS): Wird in Spracherkennung, Verarbeitung natürlicher Sprache und Bioinformatik zur Modellierung sequentieller Daten verwendet. Der Viterbi -Algorithmus, ein DP -Algorithmus, wird verwendet, um die wahrscheinlichste Sequenz versteckter Zustände zu finden, die eine Folge von Beobachtungen haben.
3. Graphalgorithmen:
* All-Pairs-kürzeste Wege (Floyd-warshall): Wie oben erwähnt.
* Netzwerkflussprobleme: Finden Sie den maximalen Fluss eines Netzwerks von einer Quelle zu einer Senke.
4. Spieltheorie:
* optimale Strategien finden: In Spielen wie Schach oder Tic-Tac-Toe kann dynamische Programmierung verwendet werden, um die optimalen Bewegungen für einen Spieler zu bestimmen.
* Minimax-Algorithmus (mit Alpha-Beta-Schnitt): Eine Variante der dynamischen Programmierung, die häufig im Spielspiel verwendet wird, um mögliche Spielstaaten zu erkunden und den besten Schritt für einen Spieler zu finden.
5. Computer Vision:
* Bildsegmentierung: Ein Bild in aussagekräftige Regionen oder Objekte aufzuteilen. Dynamische Programmierung kann verwendet werden, um den Segmentierungsprozess zu optimieren.
6. Textverarbeitung:
* Textrechnung: Bestimmen Sie den optimalen Weg, um einen Textabsatz in Zeilen zu unterteilen, um die Ablagerung des rechten Randes zu minimieren.
* Wortbruch: Eine Abfolge von Zeichen in Wörter zerlegen.
7. Steuerungssysteme:
* optimale Kontrolle: Bestimmung der Steuereingänge, die ein System optimal von einem Zustand zu einem anderen treiben (z. B. minimieren den Energieverbrauch).
zwischen Memoisierung und Tabellierung wählen:
* Memoisierung:
* Intuitiver und einfacher zu verstehen für einige Probleme.
* Berechnet nur die Teilprobleme, die tatsächlich benötigt werden.
* Kann unter Stapelüberlauf für eine sehr tiefe Rekursion leiden.
* Tabellierung:
* Typischerweise effizienter in Bezug auf konstante Faktoren (kein Rekursionsaufwand).
* Kann einige Teilprobleme berechnen, die nicht benötigt werden.
* Erfordert im Allgemeinen eine sorgfältige Bestellung von Berechnungen, um sicherzustellen, dass Unterprobleme gelöst werden, bevor sie benötigt werden.
Schritte zur Lösung eines dynamischen Programmierproblems:
1. den Zustand definieren: Bestimmen Sie die Parameter, die ein Subproblem eindeutig identifizieren.
2. Definieren Sie die Übergänge: Drücken Sie die Lösung in einem Unterproblem in Bezug auf die Lösungen für kleinere Teilprobleme aus.
3. Identifizieren Sie die Basisfälle: Definieren Sie die Lösungen auf die kleinsten Teilprobleme (der Ausgangspunkt).
4. Implementieren Sie den Algorithmus: Verwenden Sie entweder eine Memoisierung (oben nach unten) oder die Tabellierung (Bottom-up), um die Lösungen zu berechnen und zu speichern.
5. Bestimmen Sie die Reihenfolge der Berechnung: Bestimmen Sie bei Verwendung der Tabellierung die richtige Reihenfolge, in der die Teilprobleme berechnet werden sollen.
6. die optimale Lösung extrahieren: Sobald alle Teilprobleme gelöst sind, extrahieren Sie die optimale Lösung für das ursprüngliche Problem aus den gespeicherten Ergebnissen.
Dynamische Programmierung ist eine leistungsstarke Technik, erfordert jedoch eine sorgfältige Analyse und ein problemspezifisches Design. Das Verständnis der Prinzipien und das Praktizieren mit verschiedenen Beispielen ist der Schlüssel zur Beherrschung dieses algorithmischen Ansatzes.
