Dynamisches Programmieren WS15-16

Aus ProgrammingWiki

Archivierte Version vom 2016-01-18T14:33:55+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Thematischer Einstieg und Motivation
2 Rucksackproblem
3 Rundreiseproblem
4 Anwendung
5 Quellen

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

function FIB_REK(num) {
    if(num == 1) {return 1;}
    if(num == 2) {return 1;}
    return (FIB_REK(num - 1) + FIB_REK(num - 2));
}

FIB_REK(42);

function FIB_MEMO(num) {
    var cache = { 1: 1, 2: 1 };
    function innerFib(x) {
       if(cache[x]) { return cache[x]; }
       cache[x] = (innerFib(x-1) + innerFib(x-2));
       return cache[x];
    }
    return innerFib(num);
}

FIB_MEMO(42);

function FIB_DYN(num) {
    var n2 = 0;
    var n1 = 1;
    var helper;
    for(var i=0; i<(num - 2); i++) {
        helper = n2;
        n2 = n1;
        n1 = n1 + helper;
    }
    return (n2 + n1); 
}

FIB_DYN(42);

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	1	2	3	4	5
0	0	0	0	0	0
1	0	3	3	3	3
2	0	3	7	7	10
3	0	3	7	7	10
4	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

Dynamisches Programmieren WS15-16

Inhaltsverzeichnis

Thematischer Einstieg und Motivation

Was ist dynamisches Programmieren?

Bottom-up

Optimalitätskriterium

Dynamisches Programmieren vs Memoizing

Vergleich anhand Fibonacciberechnung

Rucksackproblem

Iterative Berechnung

Instanz eines 0/1-Rucksackproblems mit K = 5

Lösung

Berechnung

Rekursive Berechnung mit Memorizing

Lösung des Rundreiseproblems

Rundreiseproblem

Anwendung

Quellen

Suche