Die 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 die beste Lösung aus einer Reihe von Optionen auswählen.
Ein Beispiel für ein Optimierungsproblem ist das Traveling Salesman Problem. Das Ziel ist es, die kürzeste Route zu finden, die es dem Handelsvertreter ermöglicht, jede Stadt genau einmal zu besuchen und in die Ausgangsstadt zurückzukehren.
Bellmans Ansatz für diese Probleme bestand darin, sie in kleinere Teilprobleme zu zerlegen und die Teilprobleme vom kleinsten zum größten zu lösen. Anschließend speicherte er die Ergebnisse der Teilprobleme und verwendete sie erneut, um größere Teilprobleme zu lösen. Das ist die Hauptidee hinter der dynamischen Programmierung.
Was ist dynamische Programmierung?
Bei der dynamischen Programmierung werden Optimierungsprobleme gelöst, indem man sie in kleinere Teilprobleme zerlegt, jedes Teilproblem einmal löst und die Lösungen speichert, damit sie wiederverwendet und zur Lösung des größeren Problems kombiniert werden können. Die Probleme werden vom kleinsten zum größten gelöst, so dass die Lösungen wiederverwendet werden können.
Wie funktioniert dynamische Programmierung?
Das Lösen eines Problems mit Hilfe der dynamischen Programmierung umfasst die folgenden Schritte:
- Definieren Sie die Teilprobleme: Ein großes Problem wird in kleine Teilprobleme unterteilt.
- Lösen Sie die Teilprobleme: Dies beinhaltet die Lösung des identifizierten Teilproblems, was durch Rekursion oder Iteration geschehen kann.
- Speichern Sie die Lösungen: Die Lösungen der Teilprobleme werden gespeichert, damit sie wiederverwendet werden können.
- Konstruieren Sie die Lösung des ursprünglichen Problems: Die Lösung des großen Problems wird aus den bereits berechneten Teilproblemen konstruiert.
Um dies in Aktion zu sehen, berechnen wir die 6. Fibonacci-Zahl, F(6), nach diesem Verfahren.
Definieren Sie zunächst die Teilprobleme, die gelöst werden müssen.
F(n) = F(n-1) F(n-2) für n > 1
Daraus folgt: 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 besteht darin, jedes Teilproblem mit Hilfe einer rekursiven Funktion oder eines iterativen Prozesses zu lösen. Wir lösen die Teilprobleme vom kleinsten zum größten, wobei wir die Ergebnisse der kleineren Teilprobleme wiederverwenden. Daraus ergibt sich das Folgende:
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
Während wir die einzelnen Teilprobleme lösen, speichern wir die Lösungen in einem Array oder einer Tabelle, so dass sie bei der Lösung größerer Teilprobleme wie folgt wiederverwendet werden können:
| n | F(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
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 sich aus der Summe der Ergebnisse von F(5) und F(4), den Teilproblemen des größten Problems, ergibt. Das Ergebnis ist 8.
Wo und warum wird die dynamische Programmierung eingesetzt?
Dynamische Programmierung wird in Bereichen eingesetzt, 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.
Zu diesen Bereichen gehören Informatik, Wirtschaft, Mathematik und Ingenieurwesen. In der Informatik wird es zur Lösung von Problemen mit Sequenzen, Graphen und ganzzahligen Werten sowie bei der kompetitiven Programmierung eingesetzt.
In den Wirtschaftswissenschaften wird sie zur Lösung von Optimierungsproblemen in den Bereichen Finanzen, Produktion und Ressourcenzuweisung eingesetzt. In der Mathematik wird die dynamische Programmierung in der Spieltheorie, der Statistik und der Wahrscheinlichkeitsrechnung verwendet, wo sie zur Lösung von Optimierungsproblemen eingesetzt wird.
In der Technik wird sie zur Lösung von Problemen in den Bereichen Ressourcenzuweisung, Zeitplanung, Fertigung, Kommunikation und Kontrollsysteme eingesetzt.
Die Verwendung der dynamischen Programmierung zur Lösung von Optimierungsproblemen hat mehrere Vorteile:
- Effizienz: Die dynamische Programmierung kann effizienter sein als andere Optimierungsalgorithmen, da sie die mehrfache Neuberechnung ähnlicher Probleme vermeidet.
- Lösen großer Probleme: Die dynamische Programmierung ist ideal für große Optimierungsprobleme, die mit anderen Methoden nicht lösbar wären. Das liegt daran, dass sie das Problem in kleinere Probleme zerlegt und so die Komplexität reduziert.
- Optimale Lösungen: Algorithmen der dynamischen Programmierung können die optimale Lösung für ein Problem finden, wenn die Teilprobleme und Ziele richtig definiert sind.
- Einfachheit: Algorithmen der dynamischen Programmierung sind einfach zu implementieren und zu verstehen, insbesondere wenn das Problem in einer bestimmten Reihenfolge definiert werden kann.
- Erweiterbarkeit: Algorithmen der dynamischen Programmierung können leicht erweitert werden, um komplexere Probleme zu lösen, indem zusätzliche Teilprobleme hinzugefügt und die Ziele des Problems geändert werden.
Wenn es um die Lösung von Optimierungsproblemen geht, ist die dynamische Programmierung ein sehr nützliches Werkzeug, um die Effizienz der Lösungen zu gewährleisten.
Bei der dynamischen Programmierung verwendete Ansätze
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 ist auch als Memoisierung bekannt. Memoisierung ist eine Optimierungstechnik, die in erster Linie dazu dient, Computerprogramme schneller zu machen, indem die Ergebnisse von Funktionsaufrufen im Cache gespeichert werden und die Ergebnisse beim nächsten Mal, wenn sie benötigt werden, zurückgegeben werden, anstatt sie erneut zu berechnen.
Der Top-Down-Ansatz umfasst Rekursion und Caching. Bei der Rekursion ruft sich eine Funktion selbst mit einfacheren Versionen des Problems als Argument auf. Die Rekursion wird verwendet, um das Problem in kleinere Teilprobleme zu zerlegen und die Teilprobleme zu lösen.
Sobald ein Teilproblem gelöst ist, wird das Ergebnis zwischengespeichert und bei einem ähnlichen Problem wiederverwendet. Das Top-Down-Verfahren ist einfach zu verstehen und zu implementieren und löst ein Teilproblem nur einmal. Ein Nachteil ist jedoch, dass es aufgrund der Rekursion viel Speicherplatz benötigt. Dies kann zu einem Stack Overflow-Fehler führen.
Bottom-Up-Ansatz
Der Bottom-Up-Ansatz, auch bekannt als Tabellierung, verzichtet auf Rekursion und ersetzt sie durch Iteration, wodurch Stack Overflow-Fehler vermieden werden.
Bei diesem Ansatz wird ein großes Problem in kleinere Teilprobleme zerlegt, und die Lösungen für die Teilprobleme werden zur Lösung des größeren Problems verwendet.
Kleinere Teilprobleme werden zunächst vom größten zum kleinsten gelöst und ihre Ergebnisse werden in einer Matrix, einem Array oder einer Tabelle gespeichert, daher der Name Tabulation.
Mit den gespeicherten Ergebnissen werden größere Probleme gelöst, die von den Unterproblemen abhängen. Das Ergebnis des ursprünglichen Problems wird dann gefunden, indem das größte Teilproblem mit Hilfe der zuvor berechneten Werte gelöst wird.
Dieser Ansatz hat den Vorteil, dass er speicher- und zeiteffizient ist, da er ohne Rekursion auskommt.
Beispiele für Probleme, die durch dynamische Programmierung gelöst werden können
Im Folgenden finden Sie einige Programmierprobleme, die mit dynamischer Programmierung gelöst werden können:
#1. Knapsack-Problem
Ein Tornister ist eine Tasche aus Segeltuch, Nylon oder Leder, die typischerweise auf den Rücken geschnallt wird und von Soldaten und Wanderern zum Transport von Vorräten verwendet wird.
Beim Rucksackproblem wird Ihnen ein Rucksack vorgelegt, aus dem Sie angesichts seines Fassungsvermögens Gegenstände auswählen müssen, die jeweils einen bestimmten Wert haben. Ihre Auswahl sollte so erfolgen, dass Sie den maximalen Gesamtwert der Gegenstände erhalten und das Gewicht der Gegenstände kleiner oder gleich der Kapazität des Rucksacks ist.
Im Folgenden finden Sie ein Beispiel für das Rucksackproblem:
Stellen Sie sich vor, Sie gehen auf eine Wandertour und haben einen Rucksack mit einem Fassungsvermögen von 15 Kilogramm. Sie haben eine Liste von Gegenständen, die Sie mitnehmen können, zusammen mit deren Werten und Gewichten, wie in der folgenden Tabelle dargestellt:
| Gegenstand | Wert | Gewicht |
|---|---|---|
| Zelt | 200 | 3 |
| Schlafsack | 150 | 2 |
| Kocher | 50 | 1 |
| Essen | 100 | 2 |
| Wasserflasche | 10 | 0.5 |
| Erste-Hilfe-Kasten | 25 | 1 |
Wählen Sie eine Teilmenge der mitzunehmenden Gegenstände so aus, dass der Gesamtwert der Gegenstände maximiert wird und das Gesamtgewicht kleiner oder gleich dem Fassungsvermögen des Rucksacks ist, das 15 Kilogramm beträgt.
Zu den realen Anwendungen des Rucksackproblems gehören die Auswahl von Wertpapieren, die einem Portfolio hinzugefügt werden sollen, um das Risiko zu minimieren und den Gewinn zu maximieren, sowie die Suche nach den am wenigsten verschwenderischen Methoden zum Abbau von Rohstoffen.
#2. Zeitplanungsproblem
Ein Scheduling-Problem ist ein Optimierungsproblem, bei dem das Ziel darin besteht, einem Satz von Ressourcen Aufgaben optimal zuzuweisen. Bei den Ressourcen kann es sich um Maschinen, Personal oder andere Ressourcen handeln, die zur Erfüllung der Aufgaben eingesetzt werden.
Im Folgenden finden Sie ein Beispiel für ein Planungsproblem:
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 von Mitarbeitern, die für die Erledigung der Aufgabe qualifiziert sind.
Die folgende Tabelle beschreibt die Aufgaben und ihre Eigenschaften:
| Aufgabe | Startzeit | Endzeit | Qualifizierte Mitarbeiter |
|---|---|---|---|
| T1 | 9 | 11 | A, B, C |
| T2 | 10 | 12 | A, C |
| T3 | 11 | 13 | B, C |
| T4 | 12 | 14 | A, B |
Weisen Sie jede Aufgabe einem Mitarbeiter zu, um die Gesamtbearbeitungszeit zu minimieren.
Das Planungsproblem kann in der Fertigungsindustrie auftreten, wenn Sie versuchen, die Zuweisung von Ressourcen wie Maschinen, Materialien, Werkzeugen und Arbeitskräften zu optimieren.
Es kann auch im Gesundheitswesen auftreten, wenn es darum geht, den Einsatz von Betten, Personal und medizinischem Material zu optimieren. Andere Branchen, in denen dieses Problem auftreten kann, sind das Projektmanagement, das Lieferkettenmanagement und das Bildungswesen.
#3. Travelling Salesman Problem
Dies ist eines der am meisten untersuchten Optimierungsprobleme, das mit dynamischer Programmierung gelöst werden kann.
Das Travelling-Salesman-Problem 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ückführt.
Im Folgenden finden Sie ein Beispiel für ein Handelsvertreterproblem:
Stellen Sie sich vor, Sie sind ein Vertreter, der eine Reihe von Städten in der kürzest möglichen Zeit 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 dargestellt:
| Stadt | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 10 | 15 | 20 | 30 |
| B | 10 | 0 | 35 | 25 | 15 |
| C | 15 | 35 | 0 | 30 | 20 |
| D | 20 | 25 | 30 | 0 | 10 |
| E | 30 | 15 | 20 | 10 | 0 |
Das Travelling-Salesman-Problem findet man unter anderem in der Freizeitindustrie bei der Planung von Reiserouten für Touristen, in der Logistik bei der Planung des Warenversands, im Transportwesen bei der Planung von Busrouten und in der Vertriebsbranche.
Es liegt auf der Hand, dass die dynamische Programmierung viele reale Anwendungen hat, und das hilft, mehr darüber zu erfahren.
Nutzen Sie die folgenden Ressourcen, um Ihr Wissen über dynamische Programmierung zu vertiefen.
Ressourcen
Dynamische Programmierung von Richard Bellman
Dynamic Programming ist ein Buch von Richard Bellman, der die dynamische Programmierung erfunden und in ihrer Anfangsphase entwickelt hat.
| Preview | Product | Rating | |
|---|---|---|---|
|
Dynamic Programming (Dover Books on Computer Science) | Buy on Amazon |
Das Buch ist so leicht verständlich geschrieben, dass zum Verständnis des Textes nur Grundkenntnisse in Mathematik und Kalkül erforderlich sind. In dem Buch führt Bellman in die mathematische Theorie eines mehrstufigen Entscheidungsprozesses ein, der für die dynamische Programmierung von zentraler Bedeutung ist.
Anschließend untersucht das Buch 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 Kontrollprozesse anführt und zeigt, wie die dynamische Programmierung die Probleme lösen kann.
Das Buch ist als Kindle-, Hardcover- und Taschenbuchversion erhältlich.
Meisterkurs Dynamische Programmieralgorithmen
Dieser Dynamic Programming Algorithms Master Course von Udemy wird von Apaar Kamal, einem Software-Ingenieur bei Google, und Prateek Narang, der ebenfalls bei Google gearbeitet hat, angeboten.
Der Kurs ist so optimiert, dass er den Lernenden hilft, bei Programmierwettbewerben mit vielen Problemen, die dynamische Programmierung erfordern, zu glänzen.
Abgesehen von Programmierwettbewerben ist der Kurs auch ideal für Programmierer, die ihr Verständnis von Algorithmen verbessern wollen, sowie für Personen, die sich auf Programmierinterviews und Online-Codierrunden vorbereiten.
Der Kurs, der über 40 Stunden dauert, behandelt die dynamische Programmierung in aller Tiefe. Der Kurs bietet zunächst eine Auffrischung von Konzepten wie Rekursion und Backtracking.
Anschließend werden dynamische Programmierung in der Spieltheorie, Strings, Bäume und Graphen, Matrixpotenzierung, Bitmasken, Kombinatorik und Teilfolgen, Partitionsprobleme und mehrdimensionale dynamische Programmierung sowie viele andere Konzepte behandelt.
Grundlagen der kompetitiven Programmierung, Algorithmen meistern
Udemy bietet einen Kurs Competitive Programming Essentials von Prateek Narang und Amal Kamaar an, der dynamische Programmierung, Mathematik, Zahlentheorie und fortgeschrittene Datenstrukturen und Algorithmen auf eine Weise behandelt, die für Programmierer im Wettbewerb nützlich und relevant ist.
Der Kurs bietet eine Auffrischung der Kenntnisse über Datenstrukturen und Algorithmen, bevor er in komplexere Algorithmen und Techniken eintaucht, die bei der Programmierung im Wettbewerb nützlich sind.
Der Kurs behandelt dynamische Programmierung, Mathematik, Spieltheorie, Pattern Matching, Bitmasking und eine Vielzahl von fortgeschrittenen Algorithmen, die in Programmierwettbewerben verwendet und getestet werden.
Der Udemy-Kurs ist in 10 Module und 42 Abschnitte unterteilt und bietet nach jedem Abschnitt eine Vielzahl von Übungsfragen. Dieser Bestseller-Kurs ist ein Muss für jeden, der sich für Wettbewerbsprogrammierung interessiert.
Abschließende Worte
Dynamische Programmierung ist eine nützliche Fähigkeit, die jeder Programmierer erlernen sollte, um seine Problemlösungen für reale Probleme zu verbessern. Daher sollten Programmierer in Erwägung ziehen, die vorgeschlagenen Ressourcen durchzuarbeiten, um dieses wichtige Werkzeug in ihren Werkzeugkasten aufzunehmen.
Als nächstes können Sie sich über Programmiersprachen für die Datenwissenschaft informieren.