Dynamisches Programmieren WS15-16
Aus ProgrammingWiki
Archivierte Version vom 2016-01-18T14:59:41+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
- 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
| 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 |
Berechnung
Jeder Gegenstand darf nur einmal in den Rucksack
Zeile 0: für den Anfangs leeren Rucksack Zeile 1: nur der 1. Gegenstand darf in den Rucksack -> daher 0 oder 3 Zeile 2:
2:2 -> Wert 3, da g1 Wert 3 hat;
2:3 -> Wert 7, da g2 Wert 7 hat;
2:4 -> Wert 7, da 4 kg - 3 kg = 1 kg (Verlust)-> ich gucke bei 1:1 -> Wert 0 -> 7 + 0 = 7
2:5 -> Wert 10, 3 kg hat den Wert 7, 2 kg den Wert 3 in 1:2
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)