Dynamisches Programmieren WS15-16
Aus ProgrammingWiki
Archivierte Version vom 2016-01-18T14:01:59+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 |
Vergleich anhand Fibonacciberechnung
Rucksackproblem
Iterative Berechnung
Instanz eines 0/1-Rucksackproblems mit K = 5
| i | 1 | 2 | 3 | 4 |
| g | 2 | 3 | 4 | 5 |
| w | 3 | 7 | 2 | 9 |
Lösung
- eine Zeile 0 für den Anfangs leeren Rucksack
- Spaltenköpfe für alle möglichen Gewichtsumen von 0 bis K
| Gegenstand/Gewicht | 0 | 1 | 2 | 3 | 4 | 5 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 | |
| 2 | 0 | 0 | 3 | 7 | 7 | 10 | |
| 3 | 0 | 0 | 3 | 7 | 7 | 10 | |
| 4 | 0 | 0 | 3 | 7 | 7 | 10 |
- bei Gegenstand 1 darf nur dieser in betracht gezogen werden
- bei Gegenstand 2 darf der 2. und der 1. Gegenstand in betracht gezogen werden
- bei Gegenstand 3 alle 3
- bei Gegenstand 4 alle
Rekursive Berechnung mit Memorizing
Lösung des Rundreiseproblems
Rundreiseproblem
Anwendung
Needleman-Wunsch-Algorithmus (Bioinformatik, Vergleich von Nukleotidsequenzen)
CYK-Algorithmus (Theoretische Informatik, Parsen von kfGs)
Berechnung der Levenshtein Distanz (Unterschiede zwischen zwei Sätzen)