Dynamische Programmierung

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

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

Speicher-- vs. Laufzeit: das Karnickelproblem

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.

Dynamische Programmierung

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

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

Linear Partitionieren

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

M(1,k) = s₁ f"ur k>0

M(n,1) =

n

å

i=1
s_i

Linear Partitionieren (2)

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

February 5, 2002