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

• entity: Sachverhalt oder Gegenstand
• control: Ablauf, Steuerungs- oder Berechnungsvorgang
• abstract: ohne konkrete Objekte
• interface: abstrakte Schnittstelle zur logischen Strukturierung
• boundary: konkrete Schnittstelle durch Objekt realisiert
• primitive: Standardklassen, Klassen kleiner Objekte ·
• enumeration: Aufzählungen, Wertemengen
• structure, type, ...

• allgemein: (der) Schl"ussel zu vielen algorithmischen Problemen =
  Zerlegung des Problems in Teilprobleme
• Beispiele: `` Divide-and-Conquer'' (Rekursion)²⁴
• DP: oft bei Optimierungsproblemem
• Optimierungsproblem:
  • wichtige (allgemeine) Problemklasse
  • Optimierungsprobleme:
    • gegeben: Menge von m"oglichen L"osungen + Ma"s f"ur die G"ute eine L"osung
    • gesucht: beste aller L"osungen
  • Beispiele: k"urzeste Pfade, minimale Spannb"aume, maximaler Flu"s, Problem des Handlungsreisenden, String-- und andere Matchingprobleme und unendlich viele mehr.
• Kompromi"s zwischen
  greedy-Strategie « Exhaustive Suche
• Þ dynamische Programmierung

• die n-te Fibonacci-Zahl F_n:²⁵: F₀ = 0, F₁ = 1, F_n+2 = F_n + F_n+1.
  
  
  

  ---

  fib(n) =        // fibonacci; naive, recursive solution
    if       n=0 then return 0
    else  if n=1 then return 1
    else  return fib(n-1) + fib(n-2)
    fi fi

  ---

  
  
  
• Problem: exponentielle Laufzeit
• Bild: Aufrufbaum
• alternativ: Speichere alle Werte F_i:²⁶
  

  ---

  fib(n) =    // Fibonacci: speichere alle $F_i$
    $F_0 = 0$; $F_1 = 1$;
    for i = 1 to n do
      $F_i = F_{i-1} + F_{i-2}$
    done;

  ---

• Þ lineare Laufzeitkomplexit"at.

• Probleml"osung durch Zerteilen (wie D& C)
• D&C: getrennte Teilprobleme, hier "uberlappenden Unterprobleme
• Þ Vermeidung von wiederholter Berechnung durch Speichern von Zwischenl"osungen.
• meist bei Optimierungproblemen

• Problem: ``gerechte'' Aufteilung der B"ucher eines Buchregals, Loadbalancing wechsel
• gegeben: Sequenz S = (s₁, s₂,..., s_n), s_i Î , und nat"urliche Zahl k ³ 1
• gesucht: Partition der Sequenz in k Teilsequenzen S₁, S₂, ..., S_k, wobei die maximale Teilsequenzen-Summe minimal sei Þ Problem der linearen Partitionierung
• verschiedene Heuristiken denkbar, aber: um sicher das Optimum zu finden: exhaustive Suche
• Rekursiver Ansatz:²⁷: M(n,k) sei das gesuchte Optimum. Bild

  M(n,k) = n min i=1 max (M(i,k-1), n å j=i+1 sj) M(1,k) = s1    f"ur k>0 M(n,1) = n å i=1 si

• Komplexit"at: direkt "uber Rekurrenzgleichungen: exponentiell
• Speichern u. Wiederverwendung von Zwischenergebnisse:
  • Darstellung der Funktionswerte von M(n,k) als Matrix M[n,k].
  • Komplexit"at:
    • Anzahl der Eintr"age: k n
    • Zeit pro Berechnung eines Eintrags:²⁸ O(n²)
    • Þ Zeitkomplexit"at:²⁹O(k n³)
• Berechnung ``bottom-up'': Durchlaufen der Matrix, da"s Matrixeintr"age immer bereits da sind, wenn gebraucht Þ Schleifen von kleineren Indizes zu gr"o"seren.

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