Dynamische Programmierung ist ein Konzept, das von Richard Bellman, einem Mathematiker und Wirtschaftswissenschaftler, entwickelt wurde.
Damals suchte Bellman nach einer Möglichkeit, komplexe Optimierungsprobleme zu lösen. Bei Optimierungsproblemen müssen Sie aus einer Reihe von Optionen die beste Lösung auswählen.
Ein Beispiel für ein Optimierungsproblem ist das Problem des Handlungsreisenden. Ziel ist es, die kürzeste Route zu finden, damit der Verkäufer jede Stadt genau einmal besuchen und zur Startstadt zurückkehren kann.
Bellmans Herangehensweise an diese Probleme bestand darin, sie in kleinere Teilprobleme aufzuteilen und die Teilprobleme vom kleinsten bis zum größten zu lösen. Anschließend speicherte er die Ergebnisse der Teilprobleme und verwendete sie wieder, um größere Teilprobleme zu lösen. Dies ist die Grundidee hinter der dynamischen Programmierung.
Inhaltsverzeichnis
Was ist dynamische Programmierung?
Dynamische Programmierung löst Optimierungsprobleme, indem sie in kleinere Unterprobleme zerlegt, jedes Unterproblem einmal gelöst und ihre Lösungen gespeichert werden, damit sie wiederverwendet und kombiniert werden können, um das größere Problem zu lösen. Die Probleme werden vom kleinsten bis zum größten gelöst, sodass Lösungen wiederverwendet werden können.
Wie funktioniert dynamische Programmierung?
Das Lösen eines Problems mit dynamischer Programmierung umfasst die folgenden Schritte:
Um dies in Aktion zu sehen, berechnen wir die 6. Fibonacci-Zahl, F(6), mit diesem Prozess.
Definieren Sie zunächst die Teilprobleme, die gelöst werden müssen.
F(n) = F(n-1) + F(n-2) für n > 1
Also: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Der zweite Schritt beinhaltet das Lösen jedes Teilproblems unter Verwendung einer rekursiven Funktion oder eines iterativen Prozesses. Wir lösen die Teilprobleme vom kleinsten bis zum größten, indem wir die Ergebnisse kleinerer Teilprobleme wiederverwenden. Dies gibt uns Folgendes:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Wenn wir jedes der Teilprobleme lösen, speichern wir die Lösungen in einem Array oder einer Tabelle, damit sie bei der Lösung größerer Teilprobleme wie folgt wiederverwendet werden können:
Sobald alle Teilprobleme gelöst sind, verwenden wir die Lösungen, um die Lösung des ursprünglichen Problems zu konstruieren.
In diesem Fall ist die Lösung des ursprünglichen Problems die 6. Fibonacci-Zahl, die durch Summieren der Ergebnisse von F(5) und F(4) gefunden wird, Unterproblemen, die aus dem größten Problem identifiziert wurden. Das Ergebnis gibt uns 8.
Wo und warum wird dynamische Programmierung verwendet?
Dynamische Programmierung wird in Bereichen verwendet, in denen wir Probleme haben, die in kleinere Teilprobleme unterteilt werden können, und deren Lösungen zur Lösung größerer Probleme verwendet werden.
Diese Bereiche umfassen Informatik, Wirtschaftswissenschaften, Mathematik und Ingenieurwissenschaften. In der Informatik wird es zur Lösung von Problemen mit Sequenzen, Graphen und ganzzahligen Werten sowie in der kompetitiven Programmierung verwendet.
In der Wirtschaftswissenschaft wird es verwendet, um Optimierungsprobleme in den Bereichen Finanzen, Produktion und Ressourcenallokation zu lösen. In der Mathematik wird die dynamische Programmierung in der Spieltheorie, Statistik und Wahrscheinlichkeit verwendet, wo sie zur Lösung von Optimierungsproblemen verwendet wird.
In der Technik wird es verwendet, um Probleme in der Ressourcenzuweisung, Planung, Fertigung, Kommunikation und Steuerungssystemen zu lösen.
Die Verwendung dynamischer Programmierung zur Lösung von Optimierungsproblemen hat mehrere Vorteile:
Wenn es um die Lösung von Optimierungsproblemen geht, ist die dynamische Programmierung ein sehr nützliches Werkzeug, um die Effizienz der Lösungen sicherzustellen.
Ansätze, die in der dynamischen Programmierung verwendet werden
Bei der dynamischen Programmierung werden zwei Ansätze verwendet, um Optimierungsprobleme zu lösen. Dies sind der Top-Down-Ansatz und der Bottom-Up-Ansatz.
Top-Down-Ansatz
Dieser Ansatz wird auch als Memoisierung bezeichnet. Memoization ist eine Optimierungstechnik, die hauptsächlich verwendet wird, um Computerprogramme schneller zu machen, indem die Ergebnisse von Funktionsaufrufen im Cache gespeichert und die zwischengespeicherten Ergebnisse zurückgegeben werden, wenn sie das nächste Mal benötigt werden, anstatt sie erneut zu berechnen.
Der Top-Down-Ansatz beinhaltet Rekursion und Caching. Rekursion beinhaltet eine Funktion, die sich selbst mit einfacheren Versionen des Problems als Argument aufruft. Rekursion wird verwendet, um das Problem in kleinere Teilprobleme zu zerlegen und die Teilprobleme zu lösen.
Sobald ein Unterproblem gelöst ist, wird sein Ergebnis zwischengespeichert und wiederverwendet, wenn ein ähnliches Problem auftritt. Das Top-Down ist einfach zu verstehen und umzusetzen und löst nur einmal ein Teilproblem. Ein Nachteil ist jedoch, dass es aufgrund der Rekursion viel Speicher benötigt. Dies kann zu einem Stapelüberlauffehler führen.
Bottom-up-Ansatz
Der Bottom-up-Ansatz, auch als Tabellierung bekannt, beseitigt die Rekursion und ersetzt sie durch Iteration, wodurch Stapelüberlauffehler vermieden werden.
Bei diesem Ansatz wird ein großes Problem in kleinere Teilprobleme zerlegt, und die Lösungen für die Teilprobleme werden verwendet, um das größere Problem zu lösen.
Kleinere Teilprobleme werden zuerst vom größten zum kleinsten gelöst, und ihre Ergebnisse werden in einer Matrix, einem Array oder einer Tabelle gespeichert, daher der Name Tabellierung.
Die gespeicherten Ergebnisse lösen größere Probleme, die von den Teilproblemen abhängen. Das Ergebnis des ursprünglichen Problems wird dann gefunden, indem das größte Teilproblem unter Verwendung zuvor berechneter Werte gelöst wird.
Dieser Ansatz hat den Vorteil, dass er speicher- und zeiteffizient ist, indem er auf Rekursion verzichtet.
Beispiele für Probleme, die durch dynamische Programmierung gelöst werden können
Im Folgenden sind einige Programmierprobleme aufgeführt, die mit dynamischer Programmierung gelöst werden können:
#1. Rucksackproblem
Quelle: Wikipedia
Ein Rucksack ist eine Tasche aus Segeltuch, Nylon oder Leder, die normalerweise auf den Rücken geschnallt wird und von Soldaten und Wanderern zum Tragen von Vorräten verwendet wird.
Beim Rucksackproblem wird Ihnen ein Rucksack präsentiert, und angesichts seiner Tragfähigkeit müssen Sie Gegenstände auswählen, von denen jeder seinen Wert hat. Ihre Auswahl sollte so getroffen werden, dass Sie den maximalen Gesamtwert der kommissionierten Artikel erhalten und das Gewicht der Artikel kleiner oder gleich der Kapazität des Rucksacks ist.
Ein Beispiel für das Rucksackproblem ist unten angegeben:
Stellen Sie sich vor, Sie machen eine Wandertour und haben einen Rucksack mit einem Fassungsvermögen von 15 Kilogramm dabei. Sie haben eine Liste der Gegenstände, die Sie mitbringen können, zusammen mit ihren Werten und Gewichten, wie in der folgenden Tabelle gezeigt:
ArtikelWertGewichtZelt2003Schlafsack1502Kocher501Lebensmittel1002Wasserflasche100,5Erste-Hilfe-Set251
Wählen Sie eine Teilmenge der mitzubringenden Gegenstände so aus, dass der Gesamtwert der Gegenstände maximiert wird, während das Gesamtgewicht kleiner oder gleich der Rucksackkapazität ist, die 15 Kilogramm beträgt.
Reale Anwendungen des Rucksackproblems umfassen die Auswahl von Wertpapieren, die einem Portfolio hinzugefügt werden sollen, um das Risiko zu minimieren und den Gewinn zu maximieren, und das Finden der am wenigsten verschwenderischen Wege zum Schneiden von Rohstoffen.
#2. Terminierungsproblem
Ein Scheduling-Problem ist ein Optimierungsproblem, bei dem das Ziel darin besteht, Aufgaben optimal einer Menge von Ressourcen zuzuweisen. Die Ressourcen können Maschinen, Personal oder andere Ressourcen sein, die zum Abschließen der Aufgaben verwendet werden.
Ein Beispiel für ein Scheduling-Problem ist unten angegeben:
Stellen Sie sich vor, Sie sind ein Projektmanager, der für die Planung einer Reihe von Aufgaben verantwortlich ist, die von einem Team von Mitarbeitern erledigt werden müssen. Jede Aufgabe hat eine Startzeit, eine Endzeit und eine Liste der Mitarbeiter, die für die Ausführung qualifiziert sind.
Hier ist eine Tabelle, die die Aufgaben und ihre Eigenschaften beschreibt:
AufgabeStartzeitEndzeitQualifizierte MitarbeiterT1911A, B, CT21012A, CT31113B, CT41214A, B
Weisen Sie jede Aufgabe einem Mitarbeiter zu, um die Gesamtbearbeitungszeit zu minimieren.
Das Planungsproblem kann in der Fertigungsindustrie auftreten, wenn versucht wird, die Zuweisung von Ressourcen wie Maschinen, Materialien, Werkzeugen und Arbeitskräften zu optimieren.
Auch im Gesundheitswesen kann es bei der Optimierung des Einsatzes von Betten, Personal und medizinischem Material auftreten. Andere Branchen, in denen dieses Problem auftreten kann, sind Projektmanagement, Lieferkettenmanagement und Bildung.
#3. Problem des Handlungsreisenden
Quelle: Wikipedia
Dies ist eines der am besten untersuchten Optimierungsprobleme, das mit dynamischer Programmierung gelöst werden kann.
Das Problem des Handlungsreisenden liefert eine Liste von Städten und die Entfernungen zwischen jedem Städtepaar. Sie müssen die kürzestmögliche Route finden, die jede Stadt genau einmal besucht und zur Ausgangsstadt zurückkehrt.
Ein Beispiel für ein Traveling-Salesman-Problem ist unten angegeben:
Stellen Sie sich vor, Sie sind ein Verkäufer, der in kürzester Zeit eine Reihe von Städten besuchen muss. Sie haben eine Liste der Städte, die Sie besuchen müssen, und die Entfernungen zwischen jedem Städtepaar, wie in der folgenden Tabelle gezeigt:
StadtABCDEA010152030B100352515C153503020D202530010E301520100
Das Problem des Handlungsreisenden tritt unter anderem in der Freizeitbranche bei der Routenplanung für Touristen, in der Logistik bei der Planung des Warenversands, im Transportwesen bei der Planung von Busrouten und in der Vertriebsbranche auf.
Natürlich hat die dynamische Programmierung viele reale Anwendungen, was hilft, mehr darüber zu erfahren.
Betrachten Sie die folgenden Ressourcen, um Ihr Wissen über dynamische Programmierung zu vertiefen.
Ressourcen
Dynamische Programmierung von Richard Bellman
Dynamische Programmierung ist ein Buch von Richard Bellman, der die dynamische Programmierung erfunden und in ihren Anfängen entwickelt hat.
Das Buch ist leicht verständlich geschrieben und erfordert nur Grundkenntnisse in Mathematik und Analysis, um den Text zu verstehen. In dem Buch stellt Bellman die mathematische Theorie eines mehrstufigen Entscheidungsprozesses vor, der der Schlüssel zur dynamischen Programmierung ist.
Das Buch untersucht dann Engpassprobleme in mehrstufigen Produktionsprozessen, Existenz- und Eindeutigkeitstheoreme und die optimale Bestandsgleichung.
Das Beste an dem Buch ist, dass Bellman Beispiele für viele komplexe Probleme in Bereichen wie Logistik, Planungstheorie, Kommunikationstheorie, mathematische Ökonomie und Steuerungsprozesse bietet und zeigt, wie dynamische Programmierung die Probleme lösen kann.
Das Buch ist als Kindle-, Hardcover- und Taschenbuchversion erhältlich.
Masterkurs Dynamische Programmieralgorithmen
Dieser Masterkurs für dynamische Programmieralgorithmen von Udemy wird von Apaar Kamal, einem Softwareentwickler bei Google, und Prateek Narang, der auch mit Google zusammengearbeitet hat, angeboten.
Der Kurs ist optimiert, um den Lernenden zu helfen, sich im Programmierwettbewerb zu behaupten, der viele Probleme aufweist, die dynamisches Programmieren erfordern.
Abgesehen von Programmierwettbewerbern ist der Kurs ideal für Programmierer, die ihr Verständnis von Algorithmen verbessern möchten, und für Personen, die sich auf Programmierinterviews und Online-Codierrunden vorbereiten.
Der Kurs, der über 40 Stunden dauert, behandelt die dynamische Programmierung ausführlich. Der Kurs bietet zunächst eine Auffrischung zu Konzepten wie Rekursion und Backtracking.
Anschließend werden neben vielen anderen Konzepten die dynamische Programmierung in Spieltheorie, Strings, Bäume und Graphen, Matrixexponentiation, Bitmasken, Kombinatorik und Teilsequenzen, Partitionsprobleme und mehrdimensionale dynamische Programmierung behandelt.
Competitive Programming Essentials, Meisteralgorithmen
Udemy bietet einen Competitive Programming Essentials-Kurs von Prateek Narang und Amal Kamaar an, der dynamisches Programmieren, Mathematik, Zahlentheorie und fortgeschrittene Datenstrukturen und Algorithmen auf eine Weise behandelt, die für wettbewerbsfähige Programmierer nützlich und relevant ist.
Der Kurs bietet eine Auffrischung der Datenstrukturen und Algorithmen, bevor er in komplexere Algorithmen und Techniken eintaucht, die sich beim kompetitiven Programmieren als nützlich erweisen.
Der Kurs behandelt dynamische Programmierung, Mathematik, Spieltheorie, Mustererkennung, Bitmasking und eine Vielzahl fortgeschrittener Algorithmen, die in Programmierwettbewerben verwendet und getestet werden.
Der Udemy-Kurs ist in 10 Module und 42 Abschnitte unterteilt und bietet nach jedem Abschnitt viele Übungsfragen. Dieser Bestseller-Kurs ist ein Muss für alle, die sich für kompetitive Programmierung interessieren.
Letzte Worte
Dynamisches Programmieren ist eine nützliche Fähigkeit für jeden Programmierer, um zu lernen, wie er seine Problemlösung von realen Problemen verbessern kann. Daher sollten Programmierer erwägen, die vorgeschlagenen Ressourcen durchzugehen, um dieses wichtige Tool in ihre Toolbox aufzunehmen.
Als Nächstes können Sie sich Programmiersprachen ansehen, die in der Datenwissenschaft verwendet werden können.