AuK/Dynamisches Programmieren WS13-14

Wiki-Quelltext dieser Seite.

'''Autoren'''

[mailto://s3jeklin@stud.hszg.de Jens Klinger]
 
[mailto://s3jeklin@stud.hszg.de Daniel Franke]



== Einführung ==

Das Prinzip "Teile und Herrsche" dient als Grundlage für viele Algorithmen: Um ein umfangreiches Problem zu lösen, zerlegt man es in kleinere Teilprobleme, die unabhängig voneinander gelöst werden können. In der dynamischen Programmierung wird dieses Prinzip aufgegriffen und weiterentwickelt. Im Gegensatz zu "Teile und Herrsche" wird das bottom-up-Verfahren angewendet. D.h. dynamische Programmierung führt dann zu einer Lösung, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und sich eine optimale Gesamtlösung des Problems aus optimalen Teillösungen zusammensetzt. Zu diesem Zweck werden alle Teilproblem "von-unten-her" berechnet und die Tabelle eingetragen um eine erneute Berechnung zu vermeiden. 

Bei der Anwendung der dynamischen Programmierung können immer folgende Schwierigkeiten auftreten:

# Es ist nicht immer möglich, die Lösungen kleinerer Probleme so zu kombinieren, dass sich die optimale Lösung eines größeren Problems        ergibt.
# Die Anzahl der zu lösenden Teilprobleme kann unvertretbar groß werden.
# Die Zerlegung in unabhängige und überlappungsfreie Teilprobleme ist häufig Illussion.

Es gibt daher viele Probleme, für die die dynamische Programmierung nicht anwendbar bzw. ineffizienter ist als Standardalgorithmen. In diesem Wiki werden daher einige Probleme vorgestellt für die die dynamische Programmierung sehr effizient ist. 


== Vorgehensweise ==

Die Entwicklung eines dynamischen Programms kann in vier Schritte unterteilt werden:

# Charakterisierung der Struktur eines Programms.
# Definieren des Wertes einer optimalen Lösung rekursiv.
# Berechnung des Wertes einer optimalen Lösung durch den bottom-up-Ansatz.
# Konstruktion einer zugehörigen optimalen Lösung aus den schon berechneten Daten. 



== Bottom-Up ==

== Iterative versus rekursive Berechnung ==

== Rundreiseproblem ==

== Aufwandsbetrachtung und Einsatzgebiete ==

== Fazit ==