Dynamisches Programmieren WS15-16

Aus ProgrammingWiki

Archivierte Version vom 2016-01-17T16:16:59+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Thematischer Einstieg und Motivation
2 Rucksackproblem
- 2.1 Memorizing
  - 2.1.1 rekursiver Algorithmus
3 Rundreiseproblem
4 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 n1 = 1;
    var n2 = 1;
    for(var i=0; i<(num-2); i++) {
        n2 = n1;
        n1 = n1+n2;
    }
    return (n2 + n1); 
}

FIB_DYN(42);

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

Memorizing

rekursiver Algorithmus

Rundreiseproblem

Quellen

Suche