Dynamische Programmierung

23.10.00


Zum Starten hier klicken


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: