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
==Vorgehensweise==
#Darstellung der Struktur einer optimalen Lösung.
#Entwerfen einer rekursiven Methode, um den Wert der optimalen Lösung zu bestimmen.
#Berechnung des Wertes einer optimalen Lösung durch eine bottom-up-Methode.
#Bestimmung einer optimalen Lösung aus den bereits berechneten Daten.
Dabei könnnen aber immer Schwierigkeiten auftreten:
*Lösungen kleiner Probleme können nicht immer so kombiniert werden, dass sich eine optimale Lösung für ein größeres Problem ergibt
*Menge der zu lösenden Teilproblemen kann unlösbar hoch werden
*Aufspaltung in eigenständige Teilprobleme ist oft nicht möglich
==Bottom-up==
Bei dem Dynamischen Programmieren wird ein Bottom-up-Ansatz verwendet
*Um ein umfangreiches Problem zu lösen, wird es in kleine Teilprobleme zerlegt
*Alle Teillösungen werden unabhängig von einander "von unten her" gelöst und in eine Tabelle gespeichert
*Durch die speicherung in die Tabellen wird eine neue Berechnung vermieden
*Erwartung, dass eine optimale Lösung aus allen Teillösungen entsteht
**Lösung kann aber nicht immer als optimale Lösung betrachtet werden, da verschiedene Lösungen möglich sind mit dem optimalen Wert
==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===
<table border="1" bordercolor="#000000" style="background-color:#FFFFFF" width="20%" cellpadding="2" cellspacing="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$i$</td>
<td style="text-align: center;width: 5mm;">1</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">4</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$g_i$</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$w_i$</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">7</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">9</td>
</tr>
</table>
====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"
|-
|-
| 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 ||
|}
<table border="1" bordercolor="#000000" style="background-color:#FFFFFF" width="40%" cellpadding="2" cellspacing="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$n/K$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$0$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$1$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$2$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$3$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$4$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$5$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$6$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$7$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$8$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$9$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$10$</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$0$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$1:(g_i=2; w_i=6)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<th style="text-align: center;width: 5mm;">6</th>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$2:(g_i=2; w_i=3)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<th style="text-align: center;width: 5mm;">9</th>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$3:(g_i=6; w_i=5)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">14</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$4:(g_i=5; w_i=4)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">10</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">13</td>
<td style="text-align: center;width: 5mm;">14</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$5:(g_i=4; w_i=6)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">12</td>
<td style="text-align: center;width: 5mm;">12</td>
<th style="text-align: center;width: 5mm;">15</th>
<td style="text-align: center;width: 5mm;">15</td>
<td style="text-align: center;width: 5mm;">15</td>
</tr>
</table>
====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 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 183
* die Anzahl der rekursiven Aufrufe bestimmt die Zahl der zu lösenden Teilprobleme
* Deren Bearbeitungsreihenfolge wird durch den rekursiven Prozess bestimmt
* Anzahl der Aufrufe: 2026 > bei Iterativ: 1200
* -> 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
Um die rekursive Prozedur 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 10 120)
'(183 502 501)
wird einiges deutlich:
* Das Ergebnis (183) stimmt mit den Resultaten überein, die von gesamtwert-iterativ und gesamtwert-rekursiv ermittelt wurden.
* Zahl der rekursiven Aufrufe 502 < 2026 (rekursive Berechnung ohne memoizing) und < 1200 bei iterativen Verfahren). Es werden nicht alle Tabelleninhalte gebraucht und mit der rekursiven Prozedur (mit und ohnememoizing) auch nicht berechnet.
* Die Länge (501) von memoliste stimmt (beinahe) mit der Anzahl der rekursiver Aufrufe überein. Der erste kommt hinzu und sorgt für die Zahl 502.
==Fazit==
* bei einer geringen Anzahl an Gegenständen, wie hier dargestellt, ist der unterschied zwischen den Lösungsansätzen nicht signifikant
* der Signifikante Unterschied ist bei i = 10 K = 120 deutlich sichtbarer
* 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
=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