Previous Contents Next

12   Dynamische Programmierung

Literatur: Siehe Kapitel 43 aus [Sed90] und Kapitel 3 aus aus [Ski97]. Zu dynamischer Programmierung findet sich auch in [CLR90] etwas, vor allem in Kapitel 16, aber auch sonst "uber das Buch verteilt.
Inhalt Probleml"osung durch Zergliederung Optimierungsprobleme Ansatz der dynamischen Programmierung Rekursiver Probleme mit gemeinsamen Teilstrukturen Beispiel: lineares Partitionieren Beispiel: k"urzeste Pfade Anwendungsbereich von DB
Dynamische Programmierung


Speicher-- vs. Laufzeit: das Karnickelproblem


Dynamische Programmierung


  1. Charakterisiere die Struktur der optimalen L"osung
  2. Definiere rekursiv die optimale L"osung
  3. Berechne den Wert der opt. L"osung bottom-up
  4. ggf: berechne/rekonstruiere die opt. L"osung selbst.


Linear Partitionieren
Linear Partitionieren (2)


Partition(S,k) =   // linear Partitionieren
  p[0] = 0;        // P = Teilsummen
  for i = 1 to n do 
    p[i] := p[i-1] + $S_i$
  done; // Initialisierung der ``Raender''
  for i = 1 to n do M[i,1] := p[i] done;
  for j = 1 to k do M[1,j] := $s_1$ done;
  for i = 2 to n 
  do
    for j = 2 to k do
      M[i,j] := $\infty$;
      for x = 1 to i-1 
      do
        s = max(M[x,j-1],p[i]-p[x]);
        if    M[i,j] > s 
        then  M[i,j] = s;    // glob. Minimum
       D[i,j] = x     // Zur Rekonstruktion 
        fi
      done
    done
  done
  





February 5, 2002
Previous Contents Next