Dynamisches Programmieren WS15-16

Aus ProgrammingWiki

Archivierte Version vom 2016-01-18T19:19:52+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 5, 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

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

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

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

Rundreiseproblem

Anwendung

Quellen

Suche