Dynamische Programmierung ist ein Begriff, mit dem Sie wahrscheinlich schon herumgeworfen haben, wenn Sie schon längere Zeit in diesem Bereich tätig sind. Das Thema kommt häufig in Design-Review-Meetings und im Alltag von Ingenieuren zur Sprache und steht auch im Mittelpunkt technischer Interviews. Die Divide-and-Conquer-Strategie ist eine narrensichere Methode, um jedes Ziel zu erreichen. In der Computerprogrammierung trifft die gleiche Idee zu. Für zahlreiche Schwierigkeiten gibt es Untertypen, die isoliert und separat behandelt werden können, um eine endgültige Lösung des Hauptproblems zu ermöglichen. In diesem Artikel werden wir den dynamischen Programmieralgorithmus und Python diskutieren.
Was ist dynamische Programmierung?
Dynamische Programmierung ist eine Methode zur Lösung komplexer Probleme, indem man sie zunächst auf einfachere Probleme reduziert und dann die Lösungen dieser einfacheren Probleme als Bausteine zur Lösung des ursprünglichen Problems verwendet.
Wir segmentieren das vorliegende Problem in überschaubare Abschnitte. In den meisten Fällen besteht der einzige wirkliche Unterschied zwischen den Problemen der Eltern und den Problemen ihrer Kinder in ihrer relativen Größe. Somit können diese Miniprobleme in noch mehr Miniprobleme usw. auf unbestimmte Zeit zerlegt werden. Stellen Sie sich vor, dass ein Problem und seine verschiedenen Teilprobleme einen Baum bilden. Zuerst werden die „Blatt“-Probleme angegangen, dann die „Eltern“-Probleme und so weiter im Problembaum. Wenn wir kleinere Schwierigkeiten bewältigen, zeichnen wir unsere Fortschritte zur späteren Verwendung auf. Dadurch können wir diesen Teil des Problems in Zukunft überspringen.
Diese Methode ähnelt der Divide-and-Conquer-Technik darin, dass sie ein Problem in kleinere Probleme zerlegt, die unabhängig voneinander gelöst und dann kombiniert werden können, um die endgültige Lösung zu erhalten.
Wie funktioniert dynamische Programmierung?
Dynamische Programmierung ist effektiv, weil sie schwierige Probleme vereinfacht, indem sie sie in ihre Bestandteile zerlegt. Der nächste Schritt besteht darin, die besten Antworten auf diese sich daraus ergebenden Herausforderungen zu finden. Die Ergebnisse dieser Verfahren können gespeichert werden, sodass die entsprechenden Lösungen aus dem Speicher abgerufen und ohne weitere Berechnungen verwendet werden können. Außerdem kann die Lösung gespeichert werden, um eine Neuberechnung zuvor gelöster Teilprobleme zu vermeiden.
Für die dynamische Programmierung gibt es zwei Methoden:
#1. Top-Down-Ansatz
In der Informatik werden Probleme typischerweise dadurch gelöst, dass Lösungen rekursiv konstruiert werden oder indem die Ergebnisse früherer Schritte verwendet werden, um das vorliegende Problem anzugehen. Es ist möglich, die Lösungen der Teilprobleme auswendig zu lernen oder in einer Tabelle zu führen, wenn sie ähnlich sind. Die Top-Down-Methode basiert auf dem Lernen durch Auswendiglernen. Das Auswendiglernen ist dasselbe wie die zweimalige Durchführung von Rekursion und Zwischenspeicherung. Bei der Rekursion wird die Funktion indirekt aufgerufen, beim Caching werden Zwischenergebnisse verfolgt.
Zu den vielen Vorteilen des Top-Down-Ansatzes gehören:
- Die Top-Down-Methode ist einfach zu verstehen und anzuwenden. Um besser zu verstehen, was getan werden muss, zerlegt diese Methode Probleme in ihre Bestandteile. Jede neue Entwicklung bringt die Erleichterung eines bisher unüberwindbaren Hindernisses mit sich. Einige der Stücke können sogar auf andere Probleme anwendbar sein.
- Es ermöglicht die Lösung von Teilproblemen nach Bedarf. Die Top-Down-Methode ermöglicht die Zerlegung von Problemen in überschaubare Blöcke, wobei die Lösungen für diese Blöcke zur späteren Verwendung gespeichert werden. Anschließend können Kunden um Hilfe bei der Reparatur der einzelnen Komponenten bitten.
- Auch das Debuggen wird vereinfacht. Durch die Aufteilung eines Problems in kleinere Abschnitte ist es einfacher, der Antwort zu folgen und mögliche Fehler zu erkennen.
Im Folgenden sind einige der Nachteile eines Top-Down-Ansatzes aufgeführt:
- Die Top-Down-Strategie nutzt die Rekursionsmethode, die mehr Speicher im Aufrufstapel beansprucht als andere Ansätze. Dies führt letztendlich zu einem Leistungsabfall. Darüber hinaus kann es zu einem Stapelüberlauf kommen, wenn die Rekursion zu weit in die Vergangenheit zurückreicht.
#2. Bottom-Up-Ansatz
Nachdem die Lösung eines Problems anhand seiner Teilprobleme auf eine Weise ausgedrückt wurde, die auf sich selbst zurückgeht, können Benutzer das Problem mithilfe des Bottom-up-Ansatzes umschreiben, bei dem sie zuerst die kleineren Teilprobleme lösen und dann ihre Lösungen auf die größeren anwenden .
Im Gegensatz zur Top-Down-Methode entfällt bei der Bottom-Up-Methode die Rekursion. Daher verursachen die rekursiven Funktionen keinen unnötigen Overhead und verursachen keinen Stapelüberlauf. Darüber hinaus ermöglicht es die Datenkomprimierung. Die zeitliche Komplexität der Rekursion wird reduziert, da die Notwendigkeit entfällt, dieselben Werte neu zu berechnen.
Einige Vorteile der Arbeit von Grund auf sind folgende:
- Zunächst wird bestimmt, wie ein großes Problem aus kleineren, wiederverwendbaren Teilproblemen aufgebaut wird.
- Durch den Verzicht auf Rekursion trägt es dazu bei, den verfügbaren Speicher besser zu nutzen. Als Nebeneffekt wird die zeitliche Komplexität reduziert.
Merkmale der dynamischen Programmierung
Es gibt zwei Unterscheidungsmerkmale der dynamischen Programmierung:
#1. Teilprobleme überschneiden sich
Modifikationen eines Primärproblems, die besser beherrschbar sind, werden „Teilprobleme“ genannt. Die Fibonacci-Folge, bei der jede Zahl der Summe der beiden vorhergehenden Zahlen entspricht (0, 1, 1, 2, 3, 5, 8,…). Sie können die Aufgabe, den n-ten Wert in der Fibonacci-Folge zu finden, in überschaubarere Abschnitte aufteilen. Wenn Sie Lösungen finden, indem Sie dasselbe Teilproblem immer wieder angehen, wird es immer schwieriger, diese überlappenden Problemkomplexe zu lösen.
Dynamische Programmierung kann verwendet werden, um große Programmieraufgaben aufgrund des universellen Auftretens überlappender Teilprobleme in überschaubare Blöcke zu unterteilen.
#2. Unterkonstruktion hat optimale Eigenschaften
Die Eigenschaft der optimalen Unterstruktur zeigt sich, wenn es gelingt, aus den Lösungen aller Teilprobleme eine optimale Lösung zu erstellen. Damit die Rekursion funktioniert, müssen Sie die Antwort, die Sie aus jeder Überlappung ableiten, auf das gesamte Problem anwenden. Die optimale Unterstruktureigenschaft wird durch das gesamte Problem angezeigt, wenn, wie im Fall der Fibonacci-Folge, jedes Teilproblem eine Lösung hat, die auf das nächste Teilproblem in der Folge angewendet werden kann, um seinen Wert zu bestimmen.
Einsatzmöglichkeiten dynamischer Programmierung in der realen Welt
Hier sind die Einsatzmöglichkeiten der dynamischen Programmierung.
#1. Rucksackproblem
Dynamische Programmierung wurde ausgiebig zur Lösung des Rucksackproblems eingesetzt. Dies sind die Probleme, mit denen wir konfrontiert sind:
Der ideale Wert für jedes Unterproblem, der durch die Anzahl der betreffenden Artikel und den im Rucksack verbleibenden Platz bestimmt wird, kann in einem zweidimensionalen Array gespeichert werden, wodurch dieses Problem schnell gelöst werden kann. Wir können den Wert maximieren, indem wir den aktuellen Artikel in jeder Phase einbeziehen oder ausschließen. Die Antwort finden Sie in der unteren rechten Ecke des Arrays.
Das Rucksackproblem kann in den unterschiedlichsten Zusammenhängen eingesetzt werden, vom Packen von Gepäck über Investitionsentscheidungen bis hin zur Zuweisung von Ressourcen.
#2. Alle Paare auf dem kürzesten Weg
Das Problem des kürzesten Pfads in einem gewichteten Diagramm ist eine weitere typische Anwendung der dynamischen Programmierung. Mit Techniken wie Floyd-Warshall oder Bellman-Ford können wir den kürzesten Weg zwischen zwei beliebigen Knotenpaaren finden.
Um den kürzesten Weg zwischen zwei beliebigen Knoten zu verfolgen, verwenden diese Algorithmen ein dreidimensionales Array. Um den Überblick darüber zu behalten, wie weit sie vom Startpunkt entfernt sind, vergleichen sie das Ergebnis außerdem mit der Entfernung zwischen dem Startpunkt und dem Zwischenknoten in jeder Phase. Nachdem die Iterationen abgeschlossen sind, wird die endgültige Lösung die Distanzmatrix sein.
Es gibt verschiedene Einsatzmöglichkeiten für die Lösung des All-Pair-Shortest-Path-Problems, beispielsweise bei der Netzwerkanalyse, dem Routing, der Navigation, der Analyse sozialer Netzwerke usw.
#3. Nahtschnitzen
Im Bereich der Bildverarbeitung ist das Nahtschnitzen eine faszinierende Anwendung der dynamischen Programmierung. Die Aufgabe besteht darin, die Größe eines Bildes zu reduzieren, ohne seine wesentlichen Eigenschaften zu verändern. Energiearme Routen in einem Bild, sogenannte Nähte, können zum Subtrahieren oder Hinzufügen von Pixeln verwendet werden, um diesen Effekt zu erzielen.
Mithilfe dynamischer Programmierung können wir die kumulative Energie jedes Pixels im Bild basierend auf seinem Gradienten und seinen Nachbarn berechnen und diese Informationen dann verwenden, um zu bestimmen, welche Nähte entfernt oder hinzugefügt werden sollten. Wenn wir uns dann vom unteren Bildrand nach oben vorarbeiten, können wir die Nahtstelle mit der geringsten Menge potenzieller Energie finden. Diese Methode kann erneut angewendet werden, bis die erforderliche Größe erreicht ist.
Darüber hinaus können Bilder mithilfe von Seam Carving in der Größe geändert, zugeschnitten, neu ausgerichtet und mehr werden.
#4. Maschinelles Lernen und Genomik
Herausforderungen des maschinellen Lernens und der Genomik wie Sequenzausrichtung, versteckte Markov-Modelle und phylogenetische Bäume sind alle für die Problemlösungsfähigkeiten der dynamischen Programmierung zugänglich.
Das Ausrichten mehrerer Symbolsequenzen (häufig DNA oder Proteine) zur Aufdeckung von Gemeinsamkeiten wird als Sequenzausrichtung bezeichnet. Dies kann Aufschluss über ihre evolutionären Zusammenhänge, Funktionen in der Gesellschaft oder strukturelle Merkmale geben. Optimale Ausrichtungen können durch dynamische Programmierung gefunden werden, indem Übereinstimmungen und Nichtübereinstimmungen zwischen Sequenzen Punkte zugewiesen werden.
Wahrscheinlichkeitsmodelle, sogenannte Hidden-Markov-Modelle, werden zur Beschreibung von Zeitreihendaten verwendet, die von unbekannten Zuständen abhängig sind. Sie sind nützlich für die Modellierung schwieriger Phänomene wie Spracherkennung, NLP, Bioinformatik usw. Wenn eine Reihe von Beobachtungen gegeben werden, können dynamische Programmiertechniken wie Viterbi und Vorwärts-Rückwärts die wahrscheinlichste Abfolge verborgener Zustände bestimmen.
Phylogenetische Bäume zeigen die Verbindungen zwischen Arten oder Genen im Laufe der Zeit. Aus diesen Gemeinsamkeiten lassen sich gemeinsame Vorfahren, Divergenzdaten und evolutionäre Ereignisse ableiten. Außerdem kann ein dynamischer Programmieralgorithmus wie Fitch und Sankoff verwendet werden, um mithilfe von Sequenzierungsdaten optimale phylogenetische Bäume zu generieren.
#5. Kryptographie
Auch die Kryptographie, das Studium der geheimen Kommunikation, profitiert von den Problemlösungsfähigkeiten der dynamischen Programmierung. Verschlüsselung, Entschlüsselung, digitale Signaturen, Authentifizierung und andere ähnliche Prozesse sind alle Teil der Kryptographie.
Durch die Verschlüsselung werden Informationen von für Menschen lesbaren Informationen in mit geheimen Schlüsseln lesbare Informationen umgewandelt. Bei der Entschlüsselung werden verschlüsselte Daten mit dem Originalschlüssel oder einem neuen wieder in Klartext umgewandelt. Digitale Signaturen ermöglichen die Überprüfung der Authentizität und Integrität einer Nachricht oder eines Dokuments. Durch die Überprüfung der Anmeldeinformationen des Absenders oder des Empfängers kann die Identität des Absenders oder Empfängers überprüft werden.
Verschiedene Arten der Kryptografie, einschließlich dynamischer Schlüsselkryptografie, codebasierter Kryptografie und dynamischer programmbasierter Kryptografie, können alle mit dynamischer Programmierung implementiert werden.
Dynamische Schlüsselkryptographie ist ein Mechanismus zum Ver- und Entschlüsseln von Nachrichten mit ständig wechselnden Schlüsseln. „Dynamische“ Schlüssel sind solche, die sich im Laufe der Zeit oder als Reaktion auf andere Faktoren weiterentwickeln. Dadurch sind sie sicherer als statische Schlüssel, die anfällig für Angriffe sind. Bei der Implementierung dynamischer Schlüsselkryptografie ist es möglich, mithilfe dynamischer Programmierung Schlüssel zu generieren und auf dem neuesten Stand zu halten.
Mithilfe einer Technik, die als codebasierte Kryptografie bekannt ist, ist es möglich, Nachrichten zu ver- und entschlüsseln, indem dabei fehlerkorrigierende Codes eingesetzt werden. Es ist möglich, Übertragungsfehler mit Fehlerkorrekturcodes zu beheben. Der Einsatz codebasierter Kryptographie gilt weithin als quantenresistent, da sie sicher gegen Angriffe von Quantencomputern ist. Dynamische Programmierung kann verwendet werden, um Kommunikation mithilfe eines codebasierten Kryptosystems zu verschlüsseln und zu entschlüsseln.
Als Methode zum Verschlüsseln und Entschlüsseln von Daten basiert die auf dynamischer Programmierung basierende Kryptografie auf einem dynamischen Programmieralgorithmus. Um Optimierungsherausforderungen zu bewältigen, unterteilen dynamische Programmiertechniken das Problem typischerweise in eine Reihe einfacherer Teilprobleme. Dynamische Programmierkryptographie verwendet Rucksack, kürzesten Weg und Nahtschnitzerei.
Was ist ein reales Beispiel für dynamische Programmierung?
Zahlreiche Instanzen realer Softwareanwendungen nutzen dynamische Programmierung, um Agilität und Effizienz aufrechtzuerhalten und gleichzeitig ihren Ressourcenbedarf auf dem Hostsystem zu reduzieren. Einige Beispiele sind wie folgt:
- Google Maps. Google Maps verwendet dynamische Programmierung, um die schnellste Route von einem bestimmten Ausgangspunkt zu mehreren verschiedenen Zielen zu finden.
- Vernetzung. Sequentielle Datenübertragung von einem einzelnen Absender an mehrere Empfänger.
- Rechtschreibprüfung. Der Bearbeitungsentfernungsalgorithmus bestimmt die Anzahl der Schritte, die erforderlich sind, um ein Wort in ein anderes umzuwandeln, und liefert ein quantitatives Maß für den Grad der Unähnlichkeit zwischen den beiden Wörtern.
- Plagiatssoftware. Dokumententfernungsmethoden helfen bei der Bestimmung der Ähnlichkeit von Textdokumenten.
- Suchmaschinen. Um festzustellen, wie ähnlich zwei Internetinhalte tatsächlich sind.
Wie löst man dynamische Programmierprobleme?
Das Erlernen der Formel zur Lösung dynamischer Programmierprobleme ist der nächste Schritt nach dem Verständnis des Konzepts der dynamischen Programmierung. Hier sind einige Vorschläge, wie Sie dynamische Programmierung auf das vorliegende Problem anwenden und zu einer praktikablen Lösung gelangen können:
#1. Bestätigen Sie das Problem der dynamischen Programmierung
Der wichtigste Teil besteht darin, zu erkennen, dass ein dynamischer Programmieralgorithmus die angegebene Problemstellung lösen kann. Um dieses Problem zu lösen, muss zunächst festgestellt werden, ob jede der Problemstellungen als Funktion in kleinere Teile zerlegt werden kann.
#2. Bestimmen Sie die Ursachen des Problems
Wenn Sie bereits zu dem Schluss gekommen sind, dass dynamische Programmierung das richtige Werkzeug für diese Aufgabe ist, besteht der nächste Schritt darin, die rekursive Struktur des Problems unter seinen Teilproblemen zu identifizieren. In diesem Fall müssen Sie die fließende Natur der Problembedingungen berücksichtigen. Diese Variable könnte eine Array-Position oder eine Problemlösungsgeschwindigkeit sein.
Darüber hinaus ist es entscheidend, die Bestandteile des Problems zu zählen.
#3. Wählen Sie zwischen einer iterativen und einer rekursiven Methode
Um dynamische Programmierprobleme zu beheben, können Sie iterative oder rekursive Ansätze nutzen. Aus dem bisher Gesagten kann man mit Sicherheit sagen, dass die rekursive Methode vorzuziehen ist. Alle oben genannten Überlegungen gelten jedoch für sich, unabhängig davon, welche Methode zur Lösung des Problems gewählt wird.
Sowohl beim rekursiven als auch beim iterativen Ansatz müssen Sie die Wiederholungsbeziehung und den Basisfall des Problems angeben.
#4. Integrieren Sie ein Erinnerungssystem
Bei der Bearbeitung eines Problems mit ähnlicher Struktur kann es hilfreich sein, sich an frühere Erfahrungen im Umgang mit vergleichbaren Teilproblemen zu erinnern. Dadurch verringert sich die zeitliche Komplexität des Problems. Die zeitliche Komplexität einer Aufgabe kann exponentiell zunehmen, wenn wir dieselben Teilprobleme immer wieder lösen, ohne auf das Auswendiglernen zurückzugreifen.
#5. Fassen Sie die Wiederholungsbeziehung in Worte
Beim Lösen eines Problems überspringen viele Programmierer die Definition der Wiederholungsbeziehung und springen direkt zum Codieren. Sie verstehen das Problem besser und können es schneller programmieren, wenn Sie die Wiederholungsbeziehung vor Beginn explizit ausdrücken können.
Algorithmus Dynamische Programmierung
Die meisten Anwendungen der dynamischen Programmierung umfassen den rekursiven Algorithmus. Die Verwendung dynamischer Programmierung zur Optimierung impliziert, dass die Rekursion für die meisten Optimierungsprobleme von wesentlicher Bedeutung ist.
Es ist jedoch nicht möglich, vollständig rekursive Probleme mit dynamischer Programmierung zu lösen. Eine Rekursion kann die Lösung nur durch eine Divide-and-Conquer-Strategie finden, es sei denn, es liegen überlappende Teilprobleme vor, wie beim Fibonacci-Folgenproblem.
Dies liegt daran, dass sich die zugrunde liegenden Teilprobleme in einem rekursiven Algorithmus wie Merge Sort nicht überschneiden, was den Einsatz dynamischer Programmierung ausschließt.
Verschiedene Arten dynamischer Programmieralgorithmen
Hier sind die verschiedenen Arten von dynamischen Programmieralgorithmen.
#1. Längste gemeinsame Folge
Es ist möglich, dass die Elemente der längsten gemeinsamen Teilsequenz (LCS) in beliebiger Reihenfolge innerhalb der Originalsequenzen erscheinen; Das LCS ist als die längste Teilsequenz definiert, die allen angegebenen Sequenzen gemeinsam ist.
Wenn zwei Folgen S1 und S2 vorliegen, dann wird eine Folge Z, die eine Teilfolge von S1 und S2 ist, als deren gemeinsame Teilfolge bezeichnet. Als zusätzliche Anforderung muss Z aus einer streng aufsteigenden Folge der Indizes der Mengen S1 und S2 bestehen.
Die Indizes der ausgewählten Elemente in Z müssen streng ansteigen, um eine aufsteigende Folge zu bilden.
#2. Floyd-Warshall-Algorithmus
Das Ziel des Floyd-Warshall-Algorithmus ist es, den kürzesten Weg zwischen jedem Knotenpaar in einem gewichteten Diagramm zu finden. Diese Methode verarbeitet Diagramme mit Gewichtungen in beide Richtungen. Andererseits schlägt es für Zyklen fehl, in denen die Summe ihrer Kanten negativ ist.
Floyd-Algorithmus, Roy-Floyd-Algorithmus, Roy-Warhshall-Algorithmus und WFI-Algorithmus sind allesamt Namen für den Floyd-Warhshall-Algorithmus.
Dieser Algorithmus verwendet eine dynamische Programmiertechnik, um optimale Verknüpfungen zu finden.
Wie löst ein dynamischer Programmieralgorithmus LCS-Probleme schneller als eine rekursive Technik?
Dynamische Programmierung reduziert den Aufwand beim Aufrufen einer Funktion. Es merkt sich das Ergebnis jedes Funktionsaufrufs, sodass nachfolgende Aufrufe die gespeicherten Daten nutzen können, ohne die gleiche Arbeit zu wiederholen.
Jedes Mal, wenn ein Element von X mit einem Element von Y verglichen wird, werden die Ergebnisse in eine Tabelle geschrieben, damit sie in nachfolgenden Berechnungen im oben genannten dynamischen Prozess verwendet werden können.
Daher entspricht die Laufzeit einer dynamischen Methode der Zeit, die zum Füllen der Tabelle benötigt wird (O(mn)). Im Gegensatz dazu beträgt die Komplexität des rekursiven Algorithmus 2max(m, n). Lesen Sie auch So wählen Sie den richtigen Verschlüsselungsalgorithmustyp für Ihre Geschäftsanforderungen aus
Was sind die dynamischen Programmierprobleme in Python?
Mithilfe der dynamischen Programmierung kann man für eine beliebige Anzahl unterschiedlicher Problemstellungen die am besten geeignete Lösung ermitteln. Im Folgenden gehen wir einige der am häufigsten nachgefragten bekannten Problemstellungen durch und stellen eine kurze Erklärung zusammen mit dem entsprechenden Python-Code bereit.
#1. Rucksack (0-1) Begrenzt
In dieser Situation werden Ihnen die Preise und Gewichte von N Gütern mitgeteilt und Sie werden damit beauftragt, diese in einen Rucksack mit der Kapazität W zu packen; Ziel ist es, die Anzahl der ausgewählten Gegenstände zu minimieren und trotzdem alles in den Rucksack zu passen.
Bei den meisten technischen Vorstellungsgesprächen für Warenorganisationen müssen die Kandidaten das Rucksackproblem lösen, ein klassisches Beispiel für eine dynamische Programmiertechnik.
Problemstellung Angenommen, Sie haben eine Tasche mit der Kapazität W und eine Liste von Dingen, von denen jedes ein Gewicht und einen entsprechenden Gewinn hat. Ziel ist die Ertragsmaximierung durch effektive Fehlbefüllung.
Die Antwort besteht darin, eine Tabelle mit Spalten für jedes denkbare Gewicht zwischen 1 und W und Zeilen für die tatsächlich ausgewählten Gewichte zu erstellen. Diese Tabelle wird als dp[][] bezeichnet. Wenn „j“ das Fassungsvermögen des Rucksacks ist und die ersten „i“ Elemente im Array „Gewicht/Artikel“ enthalten sind, dann gibt der Zustand /cell dp[i][j] in der Tabelle den höchstmöglichen Gewinn an.
Infolgedessen gibt der Wert in der letzten Zelle die Lösung an. Es ist wichtig, nur das einzupacken, was die Gewichtsbeschränkung des Rucksacks nicht überschreitet. Zum Kriterium „Gewicht>Gewicht[i-1]“ gibt es zwei Alternativen, bei denen alle Spalten gefüllt werden können.
#2. 0/1 Rucksackgebundenes Auswendiglernen
Füllen Sie einen Beutel mit Artikeln mit bekanntem Gewicht und bekanntem Gewinn, Größe K. Ihr Ziel ist es, Ihren Gewinn zu maximieren. Hier verwenden wir Memoisierung statt Tabellierung, um zu sehen, ob wir das Problem lösen können.
Bei dem oben genannten 0/1-Rucksackproblem wurde eine Bottom-Up-Strategie zur Lösungsfindung verwendet, während bei diesem Problem ein Top-Down-Ansatz auf Basis von Auswendiglernen zur Lösungsfindung verwendet wurde.
Dynamische Programmierung nutzt das Auswendiglernen, um die Notwendigkeit zu reduzieren, dieselben Teile des Problems mehrmals zu lösen. Dadurch entfällt die Notwendigkeit, das Teilproblem ständig zu lösen, und der Prozess der Ausgabegenerierung wird rationalisiert.
Problemstellung Angenommen, Sie haben eine Tasche mit der Kapazität W und eine Liste von Dingen, von denen jedes ein Gewicht und einen entsprechenden Gewinn hat. Wenn die Tasche mit größtmöglicher Effizienz gefüllt ist, kann man den größtmöglichen Gewinn erzielen.
Die Lösung besteht darin, zunächst ein zweidimensionales Array zu konstruieren, das die endgültigen Antworten auf die einzelnen Teilprobleme enthält. In den Spalten der Tabelle werden alle potenziellen Gewichtungen zwischen 1 und W aufgeführt und in entsprechend viele Abschnitte unterteilt. In den Zeilen werden jeweils die von Ihnen ausgewählten Gewichtungen angezeigt.
Wir verwenden ein dp-Array, um jedes gelöste Teilproblem zu verfolgen. Anstatt ein zuvor gelöstes Teilproblem zu lösen, geben wir einfach seine Antwort zurück.
#3. Gleiches Teilmengenproblem
Finden Sie eine Partition der gegebenen Menge, sodass die Gesamtzahl der Elemente in beiden Teilmengen gleich ist, indem Sie dynamische Programmierung verwenden, um das Problem der gleichen Teilmenge zu lösen. Zusätzlich zu seinen anderen Namen ist das Problem der gleichen Teilmenge (oder des Partitionsproblems) ein hervorragendes Beispiel für die Leistungsfähigkeit der dynamischen Programmierung.
Die vorliegende Aufgabe erfordert, dass wir das Array arr in zwei Hälften teilen, sodass jede der resultierenden Teilmengen die gleiche Gesamtgröße hat.
Als Lösung müssen wir ein zweidimensionales Array mit den Abmessungen (Summe/2+1)*(Ziel+1) erstellen. Hier können die Ergebnisse der Aufteilung des ursprünglichen Arrays für jede Teilmenge und jede Summe gespeichert und später abgerufen werden. Die erste Dimension des Arrays stellt die verschiedenen Teilmengen dar, die erstellt werden können, während die zweite Dimension des Arrays die verschiedenen Summen darstellt, die durch Kombinieren von Teilmengen berechnet werden können.
Vorteile der dynamischen Programmierung
Hier sind einige der Vorteile der dynamischen Programmierung.
#1. Wirksames Heilmittel
Dynamische Programmierung ist ein leistungsstarkes Werkzeug zum Finden optimaler Lösungen für Probleme mit optimaler Unterstruktur und überlappenden Teilproblemen. Durch die Zerlegung in überschaubare Teile lassen sich diese Herausforderungen mit der Methode leichter bewältigen. Die dynamische Programmierung ist in der Lage, eine optimale Lösung zu schaffen, indem sie sich wiederholende Berechnungen vermeidet und Antworten auf Teilprobleme wiederverwendet.
#2. Erleichtert die einfache Problemfindung
Die Lösung eines schwierigen Problems kann einfacher sein, wenn man es zunächst in einfachere Teile zerlegt. Es erleichtert die Bewältigung komplexer Probleme, indem es sie in überschaubarere Teile aufteilt. Diese Methode vereinfacht die Lösung und macht das Problem leichter zugänglich.
#3. Effizient
Durch die Eliminierung unnötiger Berechnungen und die Wiederverwendung zuvor gelöster Teilprobleme kann die dynamische Programmierung die zur Lösung eines Problems erforderliche Zeit erheblich verkürzen. Bei Überschneidungen der Teilprobleme kann die Methode helfen, indem sie die Gesamtzahl der zur Lösung des Problems erforderlichen Maßnahmen reduziert.
#4. Effektiv, wenn es für ein Problem mehrere Lösungen gibt
Dynamische Programmierung kann dabei helfen, festzustellen, welche von mehreren möglichen Erklärungen wahrscheinlicher ist. Wenn es mehrere praktikable Optionen zur Behebung eines Problems gibt, kann uns diese Methode dabei helfen, die beste Lösung auszuwählen.
Was sind die Nachteile der dynamischen Programmierung?
Hier sind einige der Nachteile der dynamischen Programmierung.
#1. Unterthemen, die immer wieder auftreten
Dynamische Programmierung funktioniert am besten, wenn das Problem überlappende Teilprobleme aufweist, was möglicherweise nicht immer der Fall ist. Es wird nicht funktionieren und Ihnen wahrscheinlich nicht die beste Lösung bieten, wenn sich die einzelnen Probleme nicht überschneiden.
#2. Komplikation in Zeit und Raum
Wenn das Problem groß ist, erfordert die dynamische Programmierung möglicherweise viel Arbeitsspeicher und Speicherplatz, was die zeitliche und räumliche Komplexität der Lösung erhöht. Mithilfe des Speichers speichert der Ansatz Zwischenergebnisse in einer Tabelle oder Memoisierungstabelle.
#3. Rahmen für das Problem
Obwohl dynamische Programmierung für bestimmte Problemstrukturen effektiv ist, ist sie nicht immer die beste Wahl. Diese Methode funktioniert am besten, wenn das Problem überlappende Teilprobleme aufweist, daher ist sie möglicherweise nicht auf andere Situationen anwendbar.
#4. Schwierig in die Praxis umzusetzen
Dynamische Programmierung erfordert fundierte Kenntnisse über Algorithmen und Datenstrukturen, was die Implementierung für Anfänger zu einer Herausforderung macht. Die Methode erfordert vorherige Überlegungen und eine gründliche Vertrautheit mit dem jeweiligen Problem.
Fazit
Zusammenfassend lässt sich sagen, dass die dynamische Programmierung eine wirksame Methode ist, um Antworten zu finden, obwohl andere Ansätze vorzuziehen sind. Es ist wichtig, die Vor- und Nachteile zu kennen und je nach Problem die richtige Methode auszuwählen. Für Probleme mit optimaler Unterstruktur und überlappenden Teilproblemen kann die dynamische Programmierung eine optimale Lösung liefern; Allerdings ist diese Methode möglicherweise nicht immer anwendbar.
Obwohl es schwierig zu entwickeln ist und viel Speicher benötigt, ist es aufgrund seiner Fähigkeit, den Problemlösungsprozess zu rationalisieren und die Rechenzeiten zu verkürzen, eine wichtige Ressource für Informatiker und Mathematiker.
Häufig gestellte Fragen zur dynamischen Programmierung
Was ist der Unterschied zwischen linearer Programmierung und dynamischer Programmierung?
Für lineare Optimierungsprobleme gibt es den Algorithmus der linearen Programmierung (LP), und für generische nichtlineare Optimierungsprobleme mit nicht konvexen Einschränkungen gibt es die dynamische Programmierung (DP), die die globale Optimalität einer Lösung garantiert.
Wie schwer ist es, dynamische Programmierung zu erlernen?
Es ist allgemein bekannt, dass dynamische Programmierung ein komplexes Thema ist, insbesondere für Neueinsteiger auf dem Gebiet der Informatik. Allerdings kann man dynamisches Programmieren leicht erlernen, wenn man die Grundprinzipien gut beherrscht und ausreichend Übung übt.
Ist dynamische Programmierung sehr schwierig?
Sie sind hart! Zunächst kann es schwierig sein, die Idee dynamischer Programmiermethoden zu verstehen. Jeder erfahrene Programmierer würde bestätigen, dass die Beherrschung von DP einen erheblichen Zeitaufwand erfordert. Notwendig ist auch die Fähigkeit, ein Problem in seine Einzelteile zu zerlegen und wieder zu einem funktionierenden Ganzen zusammenzusetzen.
Ähnliche Artikel
- PROJEKTZEITMANAGEMENT: Prozesse, Tools & Software für effektives Management
- AMAZON SEO: So optimieren Sie Ihre Produkte, um besser zu ranken
- DIE BELIEBTESTEN PROGRAMMIERSPRACHEN: Leitfaden 2023
- WAS IST COMPUTERPROGRAMMIERUNG: Beispiele, Typen, Kurse und Software
- Testamente online: Die besten Online-Testamenter.
Referenz
