\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\N} {\mathset {N}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem} {Satz}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}


\title{Zwei Beispiele zum dynamischen Programmieren}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Einkaufsproblem (auch Rucksackproblem genannt)}

\textbf{gegeben}: Eine Menge von $n$ Artikeln, mit 
positiven ganzzahligen Preisen $p_1, \dots , p_n \in \N$ 
und positiven ganzzahligen Werten $w_1, \dots, w_n \in \N$.
Ein Budget $B \in \N$.

\textbf{gesucht}: Eine Teilmenge von Artikeln 
$A \subseteq \{1, \dots, n\}$, so dass der Gesamtpreis
$p_A \leq B$ ist und der Gesamtwert $w_A$ maximal ist.

\textbf{L\"osung mit dynamischem Programmieren}:

\begin{enumerate}
\item Finde geeignete Teilprobleme:
  Sei $\texttt{E}[i, b]$ der Wert eines optimalen Einkaufs, wenn 
  nur die Artikel $1,\dots, i$ erlaubt sind und unser Budget auf 
  $b$ beschr\"ankt ist.


\item Finde eine Rekursion f\"ur $\texttt{E}[i,b]$:

  Wenn wir kein Geld haben, k\"onnen wir nichts kaufen:
  \[
  \texttt{E}[i, 0] = 0, \qquad  \text{f\"ur } i = 0, \dots, n.
  \]
  Wenn wir nichts kaufen k\"onnen, k\"onnen wir keinen Wert erzielen:
  \[
  \texttt{E}[0, b] = 0, \qquad  \text{f\"ur } b = 0, \dots, 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\"ugung. Wenn wir den
  $i$-ten Artikel nicht kaufen, erzielen wir
  keinen Wert, aber haben immer noch $b$ Geld \"ubrig.
 \[ 
  \texttt{E}[i, b] = 
 \left\{
\begin{array}{ll}
      \texttt{E}[i - 1, b], & \text{falls } p_i > b, \\
       \max\{\texttt{E}[i - 1, b], w_i + \texttt{E}[i-1, b-p_i]\},& 
       \text{sonst}.\\
\end{array} \right. 
\]

\item Implementiere die Rekursion:

\begin{verbatim}
    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]
\end{verbatim}

\item Finde einen optimalen Einkauf:

  M\"oglichkeit 1: F\"uhre eine zus\"atzliche Tabelle 
  $\texttt{kaufen}[i,b]$ ein.  Dabei bedeutet $\texttt{kaufen}[i, b]$, 
  dass wir den Artikel $i$ kaufen, wenn wir eine Budget von $b$ 
  zur Verf\"ugung haben.  F\"ulle $\texttt{kaufen}[i,b]$ zusammen
  mit $\texttt{E}[i,b]$ aus und benutze $\texttt{kaufen}[i,b]$, um 
  hinterher den Einkauf zu bestimmen.

\begin{verbatim}
    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)
\end{verbatim}

M\"oglichkeit 2: Benutze die Tabelle $\texttt{E}[i, b]$ direkt, 
um einen optimalen Einkauf zu rekonstruieren, indem du die Eintr\"age 
hernimmst, um festzustellen, woher das Maximum kommt.

\begin{verbatim}
    // 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)
\end{verbatim}
\end{enumerate}

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\"ange, da zur Kodierung von $B$ nur
$O(\log B)$ Bits n\"otig sind. Daher sagt man, dass der obige Algorithmus
\emph{pseudo-polynomielle Laufzeit} hat. 
Das Einkaufsproblem ist 
\emph{schwach \textup{NP}-vollst\"andig}, also gibt es 
wahrscheinlich
keinen wesentlich besseren Algorithmus.

\section{Rundreiseproblem (Traveling-Salesperson Problem, TSP)}

\textbf{gegeben}: $n$ St\"adte 
$0, 1, \dots, n - 1$ mit paarweisen Abst\"anden 
$d(i, j) = d(j, i) > 0$.

\textbf{gesucht}: Eine Reihenfolge $\pi$,
 welche die Gesamtl\"ange 
$\sum_{i = 0}^{n - 1} d(\pi(i), \pi(i+1))$ minimiert. 
Dabei beginnen wir mit Stadt $0$ und enden in Stadt $0$ (das Argument
von $\pi$ wird also modulo $n$ gerechnet).

\textbf{Naive L\"osung}: 
Probiere alle m\"oglichen Besuchsreihenfolgen $\pi$ durch.
Davon gibt es $(n-1)!$ St\"uck, da wir in Stadt $0$ anfangen und aufh\"oren.
F\"ur jede Reihenfolge ben\"otigen wir lineare Zeit, um die Gesamtl\"ange
zu berechnen. Wir erhalten also die Laufzeit $O(n!)$, was f\"ur $n > 10$
hoffnungslos ist.

\textbf{L\"osung mit dynamischem Programmieren}:

\begin{enumerate}
\item Finde geeignete Teilprobleme:
  Sei $S$ eine Teilmenge von $\{1,\dots,n-1\}$ und 
  $m \in \{0, \dots, n - 1\} \setminus S$ eine Stadt. Wir definieren
  $\texttt{T}[S, m]$ als die L\"ange einer optimalen Tour, die in Stadt $0$ 
  anf\"angt, in Stadt $m$ aufh\"ort, und dazwischen genau die St\"adte aus
  $S$ genau einmal besucht. 

\item Finde eine Rekursion f\"ur $\texttt{T}[S, m]$:

  Wenn wir zwischen $0$ und $m$ keine St\"adte besuchen, so ist die
  L\"ange der optimalen Tour von $0$ nach $m$ genau $d(0,m)$.
  \[
    \texttt{T}[\emptyset, m] = d(0, m), 
    \qquad \text{f\"ur } m = 0,\dots,n-1.
  \]

  Ansonsten unterscheiden wir, welche der St\"adte 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 sie besucht vorher genau die St\"adte aus $S \setminus \{a\}$.

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

\item Implementiere die Rekursion: \"Ubung
\item Finde eine optimale Tour: \"Ubung
\end{enumerate}

Man erh\"alt eine Laufzeit von $O(n^2 2^n)$ und Platzbedarf $O(2^n)$.
\end{document}