Dynamisches Programmieren WS15-16
Aus ProgrammingWiki
Archivierte Version vom 2016-01-17T16:03:39+00:00. Aktuelle Version
Inhaltsverzeichnis |
Leonard Mory, Frank Ehrlich, Alexander Preuss
Thematischer Einstieg und Motivation
Was ist dynamisches Programmieren?
- Kein Algorithmus, eher eine Lösungsstrategie
- Begriff kommt aus der Zeit, wo Programmieren Tabellenmethoden bezeichnete
- Optimierungsverfahren, kein Programmieren
- "Teile und Herrsche" dient als Grundlage
- Um ein umfangreiches Problem zu lösen, wird es in kleine Teilprobleme zerlegt
- Diese werden unabhängig von einander gelöst und in eine Tabelle geschrieben
- Anders als bei "Teile und Herrsche" wird bei dem Dynamischen Programmieren ein Bottom-up-Ansatz verwendet
Bottom-up
Optimalitätskriterium
Dynamisches Programmieren vs Memoizing
- beide vermeiden wiederholte Berechnung durch Speichern
- ⇒Tradeoff: Speicher statt Zeit
| Memoization | Dynamisches Programmieren |
|---|---|
| Top-Down, Depth-First Ansatz | Bottom-Up, Breadth-First Ansatz |
| Beschreibung bleibt unverändert | Beschriebung wird verändert |
| Vermeidet unnötige Berechnungen | Kann unnötige Berechnungen nicht vermeiden |
| Kann Speicher leicht verschwenden | Kann Speicher einsparen, indem unnötige Resultate vermieden werden |
| Muss prüfen ob Berechnung bereits vorliegt | keine Prüfung nötig durch neue Beschreibung |
| Komplexität hängt von Schnelligkeit des "Nachschlagens" ab | Komplexität hängt von Speichermethode ab |