Dynamisches Programmieren WS15-16

Aus ProgrammingWiki

Archivierte Version vom 2016-01-18T21:02:15+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Thematischer Einstieg und Motivation
2 Rucksackproblem
3 Rundreiseproblem
4 Anwendung
5 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 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); 
}

FIB_DYN(42);

Rucksackproblem

Iterative Berechnung

Instanz eines 0/1-Rucksackproblems mit K = 5

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

Gegenstand/Gewicht	1	2	3	4	5
0	0	0	0	0	0
1	0	3	3	3	3
2	0	3	7	7	10
3	0	3	7	7	10
4	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

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)))))))))))

}

FIB_REK(42);

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

(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)))))

(gesamtwert-rekursiv 5 10)

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: 16 > 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.

(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)))))))

(gesamtwert-rekursiv-memo 5 10)

Aus dem Aufrufbeispiel > gesamtwert-rekursiv-memo 4 5)

wird einiges deutlich:

Das Ergebnis (10) stimmt mit den Resultaten überein, die von gesamtwert-iterativ und gesamtwert-rekursiv ermittelt wurden.
Zahl der rekursiven Aufrufe 15 < 16 (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 14 von memoliste stimmt (beinahe) mit der Anzahl der rekursiver Aufrufe überein. Der erste kommt hinzu und sorgt für die Zahl 15.

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

Rundreiseproblem

Anwendung

Needleman-Wunsch-Algorithmus (Bioinformatik, Vergleich von Nukleotidsequenzen)

CYK-Algorithmus (Theoretische Informatik, Parsen von kfGs)

Berechnung der Levenshtein Distanz (Unterschiede zwischen zwei Sätzen)

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

Iterative Berechnung

Instanz eines 0/1-Rucksackproblems mit K = 5

Lösung

Berechnung

Rekursive Berechnung ohne Memorizing

Rekursive Berechnung mit Memorizing

Mit Memoizing

Fazit

Rundreiseproblem

Anwendung

Quellen

Suche