Dynamisches Programmieren SS09

Autoren: Markus Ullrich & Norbert Baum

Dev-Status

"Bottom up" versus "top down"

ToDo - Markus

Genau wie die Teile-und-Herrsche-Verfahren, löst auch die Dynamische Programmierung Probleme, durch die Kombination der Lösungen von Teilproblemen. Allerdings nutzt die dynamische Programmierung einen Bottom-up-Ansatz, bei dem alle Teillösungen "von unten her" berechnet werden. Dabei wird erwartet, dass eine optimale Gesamtlösung aus optimalen Teillösungen aufgebaut werden kann. Eine solche Lösung sollte bewusst nicht als die optimale Lösung bezeichnet werden, da es verschiedene Lösungen geben kann, die den optimalen Wert besitzen.

Die Anwendung Dynamischer Programmierung macht vor allem dann Sinn, wenn ein Problem aus sich überlappenden Teilproblemen aufgebaut ist, also wenn Teilprobleme ihrerseits gemeinsame Teilprobleme nutzen. In diesem Fall würde ein Teile-und-Herrsche-Verfahren die gemeinsamen Teilprobleme wiederholt lösen und somit mehr Arbeit als notwendig ausführen. Bei einem dynamischen Programm werden die bereits berechneten Teillösungen in einer Tabelle gespeichert, womit deren erneute Berechnung entfällt.

Das bedeutet, dass sich der Begriff "Programmierung" hier nicht auf das schreiben von Code bezieht, sondern vielmehr auf eben diese tabellarische Methode zum Lösen von Optimierungsproblemen. Demnach sollte die Methode besser "Dynamisches Optimieren" heißen.

Iterative Berechnung

ToDo - Norbert

Aufwandsbetrachtung

ToDo - Norbert

Rekursive Berechnung mit memoizing

ToDo - Markus

Beispiele

Fibonacci-Zahl

ToDo - Norbert
Fib-mem fertig bauen!

ohne memoizing

<eval>System.out.println(fib(15));</eval>

mit memoziing

<eval> System.out.println(fib_mem(30)); </eval>

Rundreiseproblem

ToDo - Markus

(Ablaufkoordination von Magnetbändern)

ToDo - ?

Finden der optimalen Teilstruktur

ToDo - Markus

Java, C# und F# Versionen

Beispiele als Java Version

Beispiele als C# und teilweise in F#

Files

Folien, Beispiele...

Links

MSDN F#

F# Compiler Download (auch für Mono)

Einführung F#

Literatur

• Th. H. Cormen, Ch. E. Leiserson, R. Rivest, C. Stein: Algorithmen - Eine Einführung, 2.Auflage, Oldenbourg Wissenschaftsverlag GmbH 2007, ISBN 978-3-486-58262-8

• Gessner, Wacker: Dynamische Optimierung - Einführung-Modelle-Computerprogramme, 1.Auflage, Carl Hanser Verlag 1972, ISBN 3-446-11539-0

• Ch. Wagenknecht: Algorithmen und Komplexität, 1.Auflage, Carl Hanser Verlag 2003, ISBN 3-446-22314-2

• A. Iwainsky: Dynamische Optimierung - Gegenstand-Methoden-Möglichkeiten, 1.Auflage, VEB Verlag Technik Berlin 1984

• J. Hinrichsen: Branch- and Bound-Verfahren zur Lösung des Rundreiseproblems, Vandenhoeck & Ruprecht Göttingen 1975, ISBN 3-525-12432-5

• S. Wolfgang, U. Gerhard: Dissertation Duale Entartung in der lineare Optimierung, Transportproblem mit zusätzlichen Nebenbedingungen und Rundreiseproblem TU Dresden und Bergakademie Freiberg, 21.02.1975