Dynamisches Programmieren WS15-16
Aus ProgrammingWiki
Archivierte Version vom 2016-01-17T15:30: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