Inhaltsverzeichnis
Dynamische Programmierung
Prinzip und Voraussetzung
Bei der Anwendung der dynamischer Programmierung können
Das Produkt mehrerer Matrizen
Die Gesamtanzahl der erforderlichen Skalar-Multiplikationen
Die Reihenfolge der Multiplikation kann durch das Setzen
Demnach ergibt die Multiplikation einer Matrix der
PPT-Folie
Die kleinere der beiden Summen wird gespeichert und ebenso
Dies führt zu folgendem Programm:
cost [l][r] gibt die minimalen Kosten der Berechnung von
Die getroffenen Entscheidungen werden in einem getrennten
Lösung des Problems der Multiplikation mehrerer Matrizen
Beschreibung zur Tabelle
Eigenschaft:
Beispiel: Traveling Salesman Problem (TSP)
Dynamische Programmierung:
Algorithmus konstruiert Tabelle :
Beispiel: 4 Städte, symmetrische Entfernungen, M:
Lösung: 1, 2, 4, 3, 1
Das Rucksack-Problem
Abbildung zum Rucksack-Problem
Bedeutung des Rucksack-Problems auch im kommerziellen Bereich:
Diese Berechnung kann in sehr effizienter Weise realisiert
In diesem Beispiel ist:
Lösung des Rucksack-Problems
Erklärung zur Lösung des Beispiels
Eigenschaft:
Optimale binäre Suchbäume
Jeder Knoten im binären Suchbaum ist mit einer ganzen Zahl
Ein binärer Suchbaum mit Häufigkeiten
Dieses Problem weist Ähnlichkeiten zu dem Problem der
Annahme: Gegeben:
Implementierung
Für jedes j wird die Berechnung ausgeführt, indem jeder
Optimaler binärer Suchbaum
Eigenschaft:
|