Zwei Beispiele zum dynamischen Programmieren
============================================
Wolfgang Mulzer


1) Einkaufsproblem (auch Rucksackproblem genannt)

gegeben: Eine Menge von n Artikeln, mit positiven ganzzahligen Preisen p(1),..., p(n) 
    und positiven ganzzahligen Werten w(1),..., w(n)
    Ein Budget B

gesucht: Eine Teilmenge von Artikeln A, so dass der Gesamtpreis
         p(A) höchstens B ist und der Gesamtwert w(A) maximal ist.

Lösung mit dynamischem Programmieren

a) Finde geeignete Teilprobleme:
  E[i, b] = Wert eines optimalen Einkaufs, wenn nur die Artikel
            1,..., i erlaubt sind und unser Budget auf b beschränkt ist.


b) Finde eine Rekursion für E[i,b]

  Wenn wir kein Geld haben, können wir nichts kaufen:
  E[i, 0] = 0  für i = 0,...,n
  Wenn wir nichts kaufen können, können wir keinen Wert erzielen:
  E[0, b] = 0  für b = 0,...,B

  Wenn wir den i-ten Artikel kaufen, erzielen wir einen Wert von w(i),
  haben aber nur noch B-p(i) Geld zur Verfügung. Ansonsten erzielen wir
  keinen Wert, aber haben immer noch B Geld übrig.
  
  E[i, b] = (p(i) > b) ? E[i-1, b] : max{E[i-1, b], w(i) + E[i-1, b-p(i)]}

c) Implementiere die Rekursion

  for i := 0 to n do
    E[i, 0] <- 0 
  for b := 0 to B do
    E[0, b] <- 0 
  for i := 1 to n do
    for b := 1 to B do
      if p(i) > b then 
        E[i, b] <- E[i-1, b]
      else
        E[i, b] <- max{E[i-1, b], w(i) + E[i-1, b-p(i)]}
  return E[n,B]

d) Finde einen optimalen Einkauf

  Möglichkeit 1: Führe eine zusätzliche Tabelle kaufen[i,b] ein.
    Dabei bedeutet kaufen[i, b], dass wir den Artikel i kaufen, wenn
    wir eine Budget von b zur Verfügung haben. Fülle kaufen[i,b] zusammen
    mit E aus und benutze kaufen[i,b], um hinterher den Einkauf zu bestimmen.

    Pseudocode:
      for i := 0 to n do
        E[i, 0] <- 0 
      for b := 0 to B do
        E[0, b] <- 0 
      for i := 1 to n do
        for b := 1 to B do
          if p(i) > b then 
            E[i, b] <- E[i-1, b]
	    kaufen[i, b] <- false  // ***
          else if E[i-1, b] >= w(i) + E[i-1, b-p(i)] then
            E[i, b] <- E[i-1, b]
	    kaufen[i, b] <- false  // ***
	  else 
            E[i, b] <- w(i) + E[i-1, b-p(i)]
	    kaufen[i, b] <- true  // ***
      // Ausgabe eines optimalen Einkaufs
      b <- B
      for i := n downto 1 do
        if kaufen[i, b] then
	  print Kaufe  i
	  b <- b - p(i)

  Möglichkeit 2: Benutze die Tabelle E[i, b] direkt, um einen optimalen
    Einkauf zu rekonstruieren, indem du die Einträge hernimmst, um 
    festzustellen, woher das Maximum kommt.

    Pseudocode:
      // die Tabelle E[i, b] ist mit dem obigen Algorithmus berechnet worden
      b <- B
      for i := n downto 1 do
        // der Eintrag von E[i, b] stammt entweder von E[i-1, b] oder von
	// w(i) + E[i-1, b-p(i)]. Nur in letzterem Fall wollen wir i kaufen.
        if E[i, b] != E[i-1, b] then
	  print Kaufe  i
	  b <- b - p(i)

Die Laufzeit und der Speicherbedarf des Algorithmus sind O(nB).
Dies ist nur gut, wenn B klein ist. Im allgemeinen ist die Laufzeit
nicht polynomiell in der Eingabelänge, da zur Kodierung von B nur
O(log B) Bits nötig sind. Daher sagt man, dass der obige Algorithmus
"pseudo-polynomielle Laufzeit" hat. 
Das Einkaufsproblem ist schwach NP-vollständig, also gibt es wahrscheinlich
keinen wesentlich besseren Algorithmus.

2) Rundreiseproblem (Traveling-Salesperson Problem, TSP)

gegeben: n Städte 0, 1,..., n-1 mit paarweisen Abständen d(i,j)=d(j,i) > 0.

gesucht: Eine Reihenfolge p in der die Städte besucht werden können,
  so dass die Gesamtlänge sum_{i=0}^{n-1} d(p(i), p(i+1)) minimal
  ist. Dabei beginnen wir mit Stadt 0 und enden in Stadt 0 (das Argument
  von p wird also modulo n gerechnet).

Naive Lösung: Probiere alle möglichen Besuchsreihenfolgen p durch.
  Davon gibt es (n-1)! Stück, da wir in Stadt 0 anfangen und aufhören.
  Für jede Reihenfolge benötigen wir lineare Zeit, um die Gesamtlänge
  zu berechnen. Wir erhalten also die Laufzeit O(n!), was für n > 10
  hoffnungslos ist.

Lösung mit dynamischem Programmieren

a) Finde geeignete Teilprobleme
  Sei S eine Teilmenge von {1,...,n-1} und m eine Stadt in
  {0,...,n-1} \ S. Wir definieren:

  T[S, m] = Länge einer optimalen Tour, die in Stadt 0 anfängt, in
            Stadt m aufhört, und dazwischen genau die Städte in
	    S genau einmal besucht, 


b) Finde eine Rekursion für T[S,m]

  Wenn wir zwischen 0 und m keine Städte besuchen, so ist die
  Länge der optimalen Tour von 0 nach m genau d(0,m).
  T[{}, m] = d(0, m) für m = 0,...,n-1

  Ansonsten unterscheiden wir, welche der Städte aus S, die wir
  auf der Tour von 0 nach m besuchen, die letzte ist. Wir nennen
  diese Stadt a. Dann ist die Teil-Tour von 0 nach a auch optimal,
  und besucht vorher genau die Städte aus S \ {a}.

  T[S, m] = max_{a in S} {T[S \ {a}, a] + d(a, m)}

c) Implementiere die Rekursion
d) Finde eine optimale Tour
  Übung

Man erhält eine Laufzeit von O(n^2 2^n) und Platzbedarf O(2^n).