Dynamische Programmierung: Was es ist, wie es funktioniert und Lernressourcen

Dynamische Programmierung ist ein Konzept, das von Richard Bellman, einem Mathematician und Ökonom.

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.

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:

1. Definieren Sie die Teilprobleme: Ein großes Problem wird in kleine Teilprobleme zerlegt.
2. Lösen Sie die Teilaufgaben: Dies beinhaltet das Lösen des identifizierten Teilproblems, was durch Rekursion oder Iteration erfolgen kann.
3. Speichern Sie die Lösungen: Lösungen zu Teilproblemen werden gespeichert, damit sie wiederverwendet werden können.
4. Konstruieren Sie die Lösung des ursprünglichen Problems: Die Lösung des großen Problems wird aus den bereits berechneten Teilproblemen konstruiertated.

Um dies in der Praxis zu sehen, rechnen wirate die 6. Fibonacci-Zahl, F(6), unter Verwendung dieser process.

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 besteht darin, jedes Teilproblem mithilfe einer rekursiven Funktion oder einer Iteration zu lösen process. Wir lösen die Teilprobleme vom kleinsten bis zum größten und verwenden dabei Ergebnisse aus kleineren Teilproblemen wieder. Das 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.

Zu diesen Bereichen gehören Informatik, Wirtschaftswissenschaften, Mathematics und Ingenieurwesen. In der Informatik wird es zur Lösung von Problemen mit Folgen, Graphen und ganzzahligen Werten sowie in der Wettbewerbsprogrammierung eingesetzt.

In den Wirtschaftswissenschaften wird es zur Lösung von Optimierungsproblemen in den Bereichen Finanzen, Produktion und Ressourcenallokation eingesetzt. In mathematics, dynamische Programmierung wird in der Spieltheorie, Statistik und Wahrscheinlichkeitstheorie 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:

1. effizienzHinweis: Die dynamische Programmierung kann effizienter sein als andere Optimierungsalgorithmen, da sie die mehrfache Neuberechnung ähnlicher Probleme vermeidet.
2. Große Probleme lösen: Dynamische Programmierung ist ideal für große Optimierungsprobleme, die mit anderen Methoden nicht zu lösen wären. Dies liegt daran, dass das Problem in kleinere Probleme zerlegt wird, wodurch ihre Komplexität reduziert wird.
3. Optimale Lösungen: Dynamische Programmieralgorithmen können die optimale Lösung für ein Problem finden, wenn die Teilprobleme und Ziele richtig definiert sind.
4. Einfachheit: Dynamische Programmieralgorithmen sind insbesondere einfach zu implementieren und zu verstehenally wenn das Problem in einer bestimmten Reihenfolge definiert werden kann.
5. Erweiterbarkeit: Dynamische Programmieralgorithmen können leicht erweitert werden, um komplexere Probleme zu lösen, indem zusätzliche Unterprobleme hinzugefügt und die Ziele des Problems modifiziert 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 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 umfasst Rekursion und Caching. Bei der Rekursion handelt es sich um eine Funktion, die sie aufruftself mit einfacheren Versionen des Problems als Argument. 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 mit p gelöst wirdrevsorgfältig berechnete Werte.

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

Ein Rucksack ist eine Tasche aus canvas, Nylon oder Leder typischally Auf den Rücken geschnallt und von Soldaten und Wanderern zum Transport von Vorräten verwendet.

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:

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.

Bei realen Anwendungen des Rucksackproblems geht es um die Auswahl von Wertpapieren, die einem Portfolio hinzugefügt werden sollen, um das Risiko zu minimieren und zu maximieren profit und die am wenigsten verschwenderischen Wege finden, Rohmaterial zu schneidenateRials.

# 2. Planungsproblem

Ein Planungsproblem ist ein Optimierungsproblem, bei dem das Ziel die Optimierung istally Aufgaben einer Reihe von Ressourcen zuweisen. Bei den Ressourcen kann es sich um Maschinen, Personal oder andere Ressourcen handeln, die zur Erledigung der Aufgaben eingesetzt 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:

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 usw. zu optimierenateRessourcen, Werkzeuge und Arbeit.

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 mit dem reisenden Verkäufer

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 wären ein SalesperSohn, der in kürzester Zeit eine Reihe von Städten besuchen muss. Sie haben eine Liste der Städte, die Sie besuchen müssen, sowie die Entfernungen zwischen den einzelnen Städtepaaren, wie in der folgenden Tabelle dargestellt:

Das Problem des Handlungsreisenden kann in der Freizeitbranche bei der Planung von Routen für Touristen und in der Logistik auftreten planning den Versand von Waren, Transport wenn plannBuslinien und in der Vertriebsbranche.

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.

Downloads & 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.

Vorspann	Produkt	Rating	Preis
	Dynamische Programmierung (Dover Books on Computer Science)		$15.79	Bei Amazon kaufen

Das Buch ist leicht verständlich geschrieben und erfordert nur Grundkenntnisse in MathematikthematicS und Analysis, um den Text zu verstehen. In dem Buch stellt Bellman die Ma vorthematical-Theorie einer mehrstufigen Entscheidung process Das ist der Schlüssel zur dynamischen Programmierung.

Anschließend untersucht das Buch Engpassprobleme in der mehrstufigen Produktion processEs, Existenz- und Eindeutigkeitstheoreme und die optimale Inventargleichung.

Das Beste an dem Buch ist, dass Bellman Beispiele für viele komplexe Probleme in Bereichen wie Logistik, Planungstheorie, Kommunikationstheorie usw. bietetthematicAlökonomie und Kontrolle processes 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 Pr. angebotenateek Narang, der auch mit Google zusammengearbeitet hat.

Der Kurs ist optimiert, um den Lernenden zu helfen, sich im Programmierwettbewerb zu behaupten, der viele Probleme aufweist, die dynamisches Programmieren erfordern.

Aside from programming competitors, the course is ideal for programmers looking to improve their understanding of algorithms and people preparing for programming interviews and online coding rounds.

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 dynamische Programmierung in der Spieltheorie, Strings, Bäume und Graphen, Matrixpotenzierung, bitMasken, Kombinatorik und Teilsequenzen, Partitionsprobleme und mehrdimensionale dynamische Programmierung sowie viele andere Konzepte.

Competitive Programming Essentials, Meisteralgorithmen

Udemy bietet a Grundlagen der kompetitiven Programmierung Kurs von Profateek Narang und Amal Kamaar, das dynamische Programmierung, 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 umfasst dynamische Programmierung, mathematics, Spieltheorie, Mustervergleich, BitMaskierung und eine Vielzahl fortschrittlicher 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.

Zusammenfassung

Dynamische Programmierung ist für jeden Programmierer eine nützliche Fähigkeit, die er erlernen kann, um die Problemlösung realer Probleme zu verbessern. Daher sollten Programmierer erwägen, die vorgeschlagenen Ressourcen durchzugehen, um dieses wichtige Tool zu ihrem Tool hinzuzufügenbox.

Als nächstes können Sie auschecken Programmiersprachen zur Verwendung in der Datenwissenschaft.