Dynamisches Programmieren WS15-16

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
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

{| class="wikitable"
|-
! 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 ==
<code id="569bbb38878a7">function FIB_REK(num) {
    if(num == 1) {return 1;}
    if(num == 2) {return 1;}
    return (FIB_REK(num - 1) + FIB_REK(num - 2));
}</code>
<run id="569bbb388791f">FIB_REK(42);</run>
<code id="569bb93656843">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);
}</code>
<run id="569bb9861da1c">FIB_MEMO(42);</run>
<code id="569bbe4494d5d">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); 
}</code>
<run id="569bbe4494e02">FIB_DYN(42);</run>

=Rucksackproblem=
==Iterative Berechnung==

===Instanz eines 0/1-Rucksackproblems mit K = 5===


{| class="wikitable"
|-
| 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

{| class="wikitable"
|-
| 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

Gegenstand 0:
* für den Anfangs leeren Rucksack

Gegenstand 1: 

* nur der 1. Gegenstand darf in den Rucksack -> daher 0 oder 3

Gegenstand 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

Gegenstand 3:

* fängt bei 4 kg an -> vorige Werte können daher übernommen werden

+ 3:4 -> Wert wäre 2, aber 2 < 7 -> daher wird 7 genommen

* 3:5 -> g3 Wert 2, 5 kg - 4 kg = 1 kg Verlust -> bei 2:1 Wert 0 -> 2 + 0 = 2 -> 2 < 10 -> geht nicht -> Wert 10 eintragen

Gegenstand 4:

* fängt bei 5 kg an -> vorige Werte können daher übernommen werden

* 4:5 -> Wert wäre 9, aber 9 < 10 -> Wert 10 wird eingetragen

==Rekursive Berechnung mit Memorizing==
==Lösung des Rundreiseproblems==

=Rundreiseproblem=
=Anwendung=
[https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm Needleman-Wunsch-Algorithmus (Bioinformatik, Vergleich von Nukleotidsequenzen)]

[https://en.wikipedia.org/wiki/CYK_algorithm CYK-Algorithmus (Theoretische Informatik, Parsen von kfGs)]

[https://en.wikipedia.org/wiki/Levenshtein_distance Berechnung der Levenshtein Distanz (Unterschiede zwischen zwei Sätzen)]

=Quellen=
*http://www.theory.informatik.uni-kassel.de/veranstaltungen/EntwurfWS2013-14/vorlesung/EAvAKap3.pdf
*http://www.mathe.tu-freiberg.de/~ernst/Lehre/AD/Folien/adKapitel11.pdf