Dynamisches Programmieren WS15-16
Aus ProgrammingWiki
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:
* (Zeile:Spalte) 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 < darüberliegende Wert 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 < darüber liegende Wert 10 -> Wert 10 wird eingetragen
<code id="569bbb38878a7">function FIB_REK(num) {
function FIB_REK(num) {
(define gegenstaende
(list->vector
'("dummy"
(2 . 3)
(3 . 7)
(4 . 2)
(5 . 9))))
;Liste wird auf Vektor abgebildet, hier von 0 bis 4, um die Nummerierung mit 1 zu starten, wird 0 nicht benutzt(dummy).
(define gewicht
(lambda(i)
(car (vector-ref gegenstaende i))))
;um auf das Gewicht zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define wert
(lambda(i)
(cdr (vector-ref gegenstaende i))))
;um auf den Wert zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define vector-copy
(lambda (v)
(let* ((l (vector-length v))
(v-duplikat (make-vector l)))
(do ((i 0 (+ i 1)))((= i l) v-duplikat)
(vector-set! v-duplikat i (vector-ref v i))))))
(define gesamtwert-iterativ
(lambda(n k)
(let ((zeileAlt (make-vector (+ k 1) 0))
(zeileNeu (make-vector (+ k 1) 0)))
(do ((z 1 (+ z 1))) ;Zeile
((> z n)(vector-ref zeileNeu k));Resultat
(set! zeileAlt (vector-copy zeileNeu))
(let ((gewicht-z (gewicht z)))
(do ((s 1 (+ s 1))) ;Spalte
((> s k))
(if (< s gewicht-z)
(vector-set! zeileNeu s (vector-ref zeileAlt s))
(vector-set! zeileNeu s
(max
(vector-ref zeileAlt s)
(+ (vector-ref
zeileAlt
(- s gewicht-z))
(wert z)))))))))))
}</code>
<run id="569bbb388791f">FIB_REK(42);</run>
==Rekursive Berechnung ohne Memorizing==
Als erstes wird die Prozedur (Quelle: [1], S. 106) ohne memoizing implementiert. Die rekursive Definition kann leicht in die Prozedur überführt werden:
* Anzahl der rekursiven Aufrufe wird ermittelt
<code id="52822a9552f91" hidden>
function FIB_REK(num) {
(define gegenstaende
(list->vector
'("dummy"
(2 . 3)
(3 . 7)
(4 . 2)
(5 . 9))))
;Liste wird auf Vektor abgebildet, hier von 0 bis 4, um die Nummerierung mit 1 zu starten, wird 0 nicht benutzt(dummy).
(define gewicht
(lambda(i)
(car (vector-ref gegenstaende i))))
;um auf das Gewicht zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define wert
(lambda(i)
(cdr (vector-ref gegenstaende i))))
;um auf den Wert zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define vector-copy
(lambda (v)
(let* ((l (vector-length v))
(v-duplikat (make-vector l)))
(do ((i 0 (+ i 1)))((= i l) v-duplikat)
(vector-set! v-duplikat i (vector-ref v i))))))
function FIB_REK(num) {
(define gegenstaende
(list->vector
'("dummy"
(2 . 3)
(3 . 7)
(4 . 2)
(5 . 9))))
(define gewicht
(lambda(i)
(car (vector-ref gegenstaende i))))
(define wert
(lambda(i)
(cdr (vector-ref gegenstaende i))))
(define vector-copy
(lambda (v)
(let* ((l (vector-length v))
(v-duplikat (make-vector l)))
(do ((i 0 (+ i 1)))((= i l) v-duplikat)
(vector-set! v-duplikat i (vector-ref v i))))))
(define gegenstaende
(list->vector
'("dummy"
(2 . 6)
(2 . 3)
(6 . 5)
(5 . 4)
(4 . 6))))
(define gewicht
(lambda (i)
(car (vector-ref gegenstaende i))))
(define wert
(lambda (i)
(cdr (vector-ref gegenstaende i))))
</code>
<code id="52822a955300f">
(define gesamtwert-rekursiv
(lambda (n k)
(let ((rek-aufrufe 0))
(letrec
((gesamtwert
(lambda (i g)
(set! rek-aufrufe (+ rek-aufrufe 1))
(cond
((= i 0) 0)
((> (gewicht i) g) (gesamtwert (- i 1) g))
(else
(max
(gesamtwert (- i 1) g)
(+ (gesamtwert (- i 1) (- g (gewicht i)))(wert i))))))))
(list (gesamtwert n k) rek-aufrufe)))))
</code>
<run id="52822ade4b41b">(gesamtwert-rekursiv 5 10)</run>
* das Ergebnis ist wie bei der iterativen Berechnung ebenfalls 10
* die Anzahl der rekursiven Aufrufe bestimmt die Zahl der zu lösenden Teilprobleme
* Deren Bearbeitungsreihenfolge wird durch den rekursiven Prozess bestimmt
* Anzahl der Aufrufe??????????????????> bei Iterativ: 20
* -> einige Tabellenwerte werden mehrfach berechnet
* Lösung des Problems: memoizing
==Rekursive Berechnung mit Memorizing==
* bevor eine Berechnung durchgeführt wird, wird überprüft, ob dieser Wert bereits existiert; wenn ja, dann wird dieser genommen; wenn nein, dann wird dieser berechnet und gespeichert
====Mit Memoizing====
Um die rekursive Prozedur (Quelle: [1], S. 107) mit memoizing zu implementieren, benötigt es nur wenige Änderungen im bereits vorhandenen Quellcode.
<code id="5282291a7f486" hidden>
(define gegenstaende
(list->vector
'("dummy"
(2 . 6)
(2 . 3)
(6 . 5)
(5 . 4)
(4 . 6))))
(define gewicht
(lambda(i)
(car (vector-ref gegenstaende i))))
(define wert
(lambda(i)
(cdr (vector-ref gegenstaende i))))
</code>
<code id="5282291a7f50d">
(define gesamtwert-rekursiv-memo
(let ((memoliste '()))
(lambda (n k)
(let ((rek-aufrufe 0))
(letrec
((gesamtwert-memo
(lambda (i g)
(let ((memowert (assoc (cons i g) memoliste)))
(if memowert
(cdr memowert)
(let ((resultat (gesamtwert i g)))
(set! memoliste
(cons (cons (cons i g) resultat) memoliste))
resultat)))))
(gesamtwert
(lambda (i g)
(set! rek-aufrufe (+ rek-aufrufe 1))
(cond
((= i 0) 0)
((> (gewicht i) g) (gesamtwert-memo (- i 1) g))
(else
(max
(gesamtwert-memo (- i 1) g)
(+ (gesamtwert-memo (- i 1) (- g (gewicht i)))(wert i))))))))
(list (gesamtwert n k) rek-aufrufe (length memoliste)))))))
</code>
<run id="5282291a7f596">(gesamtwert-rekursiv-memo 5 10)</run>
Aus dem Aufrufbeispiel > gesamtwert-rekursiv-memo 4 5)
wird einiges deutlich:
* Das Ergebnis (20) stimmt mit den Resultaten überein, die von gesamtwert-iterativ und gesamtwert-rekursiv ermittelt wurden.
* Zahl der rekursiven Aufrufe (?????) < ????? (rekursive Berechnung ohne memoizing) und < 20 bei iterativen Verfahren). Es werden nicht alle Tabelleninhalte gebraucht und mit der rekursiven Prozedur (mit und ohnememoizing) auch nicht berechnet.
* Die Länge (???) von memoliste stimmt (beinahe) mit der Anzahl der rekursiver Aufrufe überein. Der allererste kommt hinzu und sorgt für die Zahl ???.
==Fazit==
* die rekursive Berechnung ohne memoizing ist untauglich, da unnötige Mehrfachberechnung
* die memoizing- Methode ist mindestens so schnell wie die iterative Methode geben, ermöglicht eine direkte Ableitung der rekursiven Regeln und vermeidet die fehleranfällige Transformation in einen iterativen Bottom-up-Algorithmus -> rekursive Berechnung mit memoizing ist die beste Wahl
==Fazit==
Als Résumé bleibt festzuhalten, dass die Ergebnisse mit denen der iterativen Prozedur übereinstimmen. Die rekursive Berechnung ohne memoizing ist selbstverständlich nicht tauglich, da durch die unnötige Mehrfachberechnung die Zahl der rekursiven Aufrufe viel zu hoch ist. Der memoizing- Methode wiederum sollte man den Vorzug vor der iterativen Methode geben, denn sie ist mindestens so schnell wie diese, ermöglicht eine direkte Ableitung der rekursiven Regeln und vermeidet die fehleranfällige Transformation in einen iterativen Bottom-up-Algorithmus.
=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