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
**Im Gegensatz dazu müssen die Teilprobleme nicht unabhängig voneinander sein
==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 iterative 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
*Berechnungsprozess wird iterativ abgewickelt
===Berechnungsprozess===
*wird iterativ organisiert
**das heißt, dass die entsprechende Tabelle nacheinander ausgefüllt wird
*für jedes Feld einer Tabelle oder einer Matrix mit der Form (z,s )muss genau ein Resultat ermittelt werden
**diese Berechnungsmethode könnte sozusagen aus Aufwandsgründen der rekursiven vorgezogen werden
;Bei Lösungen, welche rekursiv definiert sind und durch rekursive Prozeduren berechnet wurden, können Mehrfachberechnungen von Teilausdrücken vorkommen.
[[Bild:Erklaerung_fib.PNG]]
*Aufwand für wiederholte und damit hinfällige Berechnungen wird bei der dynamischen Programmierung vermieden
**das geht aber nicht so einfach, man spricht von so genannten "überlappenden Teilproblemen"
*um das zu bewirken werden alle Teillösungen berechnet
**auch die, welche für die optimale Gesamtlösung am Schluss unrelevant sind und somit eigentlich keine Bedeutung haben
*schwieriger ist es, den Top-Down-Ansatz in einen Bottom-Up-Algoritmus umzuformen
**Bottom-Up-Algorithmen durchlaufen zweidimensionale Tabellen mittels verschachtelter Schleifen
**daher kann die Umwandlung schwierig sein und einen hohen mentalen Zeitaufwand mit sich bringen
**zudem ist sie dadurch sehr fehleranfällig
;Durch "Memorizing" kann man diesem Problem aus dem Weg gehen. Die Idee besteht darin, rekursiv erzeugte Teilprobleme einmal zu berechnen und in eine Tabelle zu speichern. Vor jeder Berechnung wird dann geprüft, ob der Wert schon vorhanden ist. Wenn das der Fall ist, wird der Wert übernommen, ansonsten wird er berechnet und danach in die Tabelle eingetragen.
=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 ==
Rekursive Berechnung, naiver Ansatz
<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>
Rekursive Berechnung mit Memoizing
<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>
Berechnung mit dynamischem Programmieren
<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>
==Schritte zum Algorithmus mit dynamischer Programmierung==
1. Struktur einer optimalen Lösung analysieren:
Problem zerlegen, Teilprobleme formulieren
2. Rekursionsgleichung für die optimale Lösung suchen
3. Rekursive Lösung mit Memoizing formulieren
4. (Umwandlung in Bottom-Up-Ansatz)
5. Lösungswege aus Berechnungen konstruieren
Problem: Bottom-Up Ansatz kann schwer zu finden sein
==Bierproblem==
[[Bild:Alpreu_Sixer-becks.jpg |mini| 300x300px]]
Informatikertreffen → Fachdiskussion
'''Problemstellung:'''
*Wieviele Möglichkeiten gibt es 3 Flaschen Bier dem Sixpack zu entnehmen?
**Wie löst man das als Informatiker?
*Mathematik: Binomialkoeffizient
*${n \choose k} = \frac{n!}{(n-k)! k!}$ also ${6 \choose 3} = \frac{6!}{(6-3)! 3!}$
*Rekursion!
**${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$
*Pascalsches Dreieck
[[Bild:Alpreu_Pascal-dreieck.jpg | mini | 300x300px]]
*Ergebnis in Zeile[n+1], Spalte [k]
**Antwort: es gibt 20 Möglichkeiten (Zeile 7, Spalte 3)
*Wir können das Problem mit einer Dreiecksmatrix lösen
**Wir berechnen unnötige Werte
**Für $Wert[i][j]$ werden nur $Wert[i-1]j-1]$ und $Wert[i-1][j]$ benötigt
**Alle Werte mit $j>n$ werden nicht benötigt, Matrix braucht in jeder Zeile nur bis Spalte $n$ ausgefüllt werden
=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="569e6f2bcf4d6">
(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="569e6f2bcf554">(gesamtwert-iterativ 10 120)</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=
;Gegeben: $n$ Städte, Entfernungsmatrix \begin{array}M = (m<sub>ij</sub>), m<sub>ij</sub>\end{array}
*Entfernung von Stadt $i$ nach Stadt $j$
;Gesucht: Rundreise über alle Städte mit minimaler Länge, also Permutation \begin{array}{rcl}π = {1,...,n} -> {1,...,n}\end{array} sodass $c(p) = \sum_{i=1}^n-1 m<sub>π(i), π(i+1)</sub> + m<sub>π(n), π (1)</sub>$ minimal ist
=Anwendung=
*Bioinformatik
**Sequenzierung von Genen und Proteinen
***[https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm Needleman-Wunsch-Algorithmus (Bioinformatik, Vergleich von Nukleotidsequenzen)]
*Linguistik
**[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
*http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html
*http://people.cs.clemson.edu/~bcdean/dp_practice/
*http://20bits.com/article/introduction-to-dynamic-programming
*https://www2.cs.fau.de/teaching/SS2010/HalloWelt/DP_2010.pdf
*https://www2.informatik.uni-erlangen.de/teaching/SS2005/HalloWelt/dyn_programming.beamer.pdf
*http://www.informatik.uni-leipzig.de/lehre/Heyer0001/AD2-Vorl2/sld016.htm