# 11 Dynamische Programmierung 2
[TOC]
[comment]: # (Zuerst ein paar LaTeX-Makros:)
$\newcommand{\N}{\mathbb{N}}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\O}{\mathcal{O}}$
*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an grafdan@ethz.ch.
Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).
## Einführung
### Beispiel: Partitionierungsproblem
Nehmen Sie an, Sie haben zu Ostern Schokolade in diversen Formen und Grössen erhalten. Nun möchten Sie die Schokolade möglichst gleichmässig mit jemandem teilen.
Formal: Gegeben sind $n$ verschiedene Zahlen. Wir möchten die Zahlen in zwei Mengen aufteilen, sodass die Summen der Elemente in beiden Menge gleich gross sind.
17 145 280 92 ...
Gegeben sind $a_1, a_2, ..., a_n$
Gesucht:
$$halbierbar(a_1, a_2, \ldots, a_n) =
\begin{cases}
true & \text{falls } \exists I \subseteq \{1, \ldots, n \} \text{ sodass } \Sigma_{i \in I} {a_i} = \Sigma_{i \not\in I} {a_i}, \\
false & \text{sonst.}
\end{cases}
$$
Es scheint schwierig, die Gleichung $\Sigma_{i \in I} {a_i} = \Sigma_{i \not\in I} {a_i}$ zu gebrauchen, um wie letztes mal hier induktiv vorzugehen. Wir können das ganze aber umformulieren, denn wir wissen ja, wie gross die beiden Summen je sein sollten: Je genau die Hälfte. Wir setzen also $s = \frac{\Sigma_{i = 1}^n {a_i}}{2}$ und suchen stattdessen nach einer Teilmenge der Zahlen, welche summiert genau $s$ ergibt. Dies nennt man auch das Subset-Sum-Problem.
### Subset-Sum-Problem
Gegeben sind die Elemente $a_i \in \N$ mit $i=1,\dots,n$, sowie eine vorgegebene Summe $s \in \N$.
Frage: $\exists I \subseteq \{1,\dots,n\}$ s.t. $\Sigma_{i \in I} a_i = s$ ?
$$erreichbar(a_1, a_2, \ldots, a_n,s) =
\begin{cases}
true & \text{falls } \exists I \subseteq \{1, \ldots, n \} \text{ sodass } \Sigma_{i \in I} {a_i} =s, \\
false & \text{sonst.}
\end{cases}
$$
Wir könnten naiverweise alle möglichen Teilmengen $I$ ausprobieren. Dann müssten wir aber $2^n$ mögliche Teilmengen berücksichtigen.
a_i= 5 3 2 7, z = 11
0 0 0 0 -> 0
0 0 0 1 -> 7
0 0 1 0 -> 2
0 0 1 1 -> 9
...
Das $i$-te Bit einer Zeile sagt aus, ob die $i$-te Zahl Teil der Menge $I$ ist oder nicht.
Neue Idee: Wir merken uns welche Summen wir mit den ersten $i$ Zahlen erreichen können. Die Summe $0$ können wir beispielsweise mit jeder Eingabe erreichen; wir wählen einfach keine der Zahlen.
0 1 2 3 4 5 6 7 8 9 10 11=z
keine Zahlen Y N N N N N N N N N N N
a_1 = 5 Y N N N N Y N N N N N N
a_2 = 3 Y N N Y N Y N N Y N N N
Wir definiern $err(i,z)=1$ falls die Summe $z$ mit den ersten $i$ Zahlen erreichbar ist. Wenn $z$ mit den ersten $i$ Zahlen erreichbar sind, haben wir entweder die $i$-te Zahl nicht genommen und können $z$ bereits mit den ersten $i-1$ Zahlen erreichen, oder wir haben die $i$-te Zahl genommen und können mit den ersten $i-1$ Zahlen die Summe $z-a_i$ erreichen:
$$
err(i,z) = err(i-1,z) \vee err(i-1,z-a_i)
$$
#### Rekursiv
Das einfach rekursiv auszurechnen hat Laufzeit $2^n$
#### Bottom up
Wir können jedoch eine DP-Tabelle *err* der Grösse $n\cdot s$ verwenden, in der der Eintrag *err[i,z]* der obigen Definition von $err(i,z)$ entspricht.
```javascript=
for i,j = 0 to n
err[i,j] = False
err[0,0] = True
for i=1 to n
for z = 0 to s
if ( err[i-1,z] ) then
err[i,z] = True
else if ( (z-a_i) >= 0 and err[i-1,z-a_i] ) then
err[i,z] = True
end if
end for
end for
```
Sobald wir die Tabelle berechnet haben, wissen wir ob die Summe erreichbar ist oder nicht, indem wir den Eintrag $err[n,s]$ betrachten. Wollen wir auch eine Menge finden, die diese Summe ergibt, so müssen wir von diesem Eintrag aus zurückverfolgen, welchen vorherigen Eintrag wir verwendet haben um den aktuellen Eintrag auf True zu setzen.
*Achtung*: $s$ kann sehr gross sein: In linearer Eingabelänge können wir eine exponentiell grosse Zahl darstellen. Wir können also mit einer relativ kleinen Eingabe ein riesiges Tableau erzeugen. Daher ist unser Algorithmus *pseudopolynomiell*, was soviel heisst wie: Der Algorithmus läuft polynomiell in den Zahlen, welche in der Eingabe repräsentiert werden. Falls alle Zahlen in der Eingabe also klein sind (polynomiell in $n$), so läuft dieses dynamische Programm polynomiell schnell in der Eingabelänge, aber im Allgemeinen nicht.
Andere Formulierung: Wenn die Eingabezahlen nicht binär, sondern unär (quasi als Strichlisten) dargestellt werden, dann läuft der Algorithmus linear in der Eingabelänge. Aber die Eingabelänge quasi künstlich zu verlängern ist ja ein wenig geschummelt.
Jetzt haben wir zwei Algorithmen: die Laufzeit des einen ist exponentiell in $n$ und die des anderen ist pseudopolynomiell. Können wir diese beiden Algorithmen irgendwie kombinieren? Hier hat der Kollege Schöning aus Ulm einen guten Trick gefunden:
Gegeben sei ein Array mit Zahlen. Um zu wissen, ob zwei dieser Zahlen zusammen eine Zielzahl $s$ ergeben, könnten wir alle Paare von Zahlen anschauen. Geht es schneller?
Wir können das Array sortieren und dann die grösste und kleinste Zahl betrachten. Falls die Summe dieser beiden Zahlen zu gross ist, müssen wir die grösste Zahl nie wieder betrachten, da jede andere Zahl mit dieser Zahl zusammen eine grössere Summe ergibt. Analog müssen wir die kleinste Zahl nicht betrachten, wenn die Summe der kleinsten und der grössten Zahl kleiner als die Zielsumme ist. Mit dieser Idee können wir nach dem Sortieren in linearer Zeit berechnen, ob die Zielsumme mit zwei Zahlen erreichbar ist. Beispiel:
1 2 17 26 56 111
^ ^
| |
Die Summe ist zu gross, weshalb wir die zweitgrösste Zahl betrachten.
1 2 17 26 56 111
^ ^
| |
Die Summe dieser Zahl und der kleinsten Zahl ist wieder zu gross; wir betrachten also die nächstkleinere Zahl, usw.
Auf diese Weise verschieben wir den rechten Zeiger nach links oder den linken Zeiger nach rechts bis wir die Zielsumme erreicht haben oder sich die beiden Zeiger treffen.
Wie können wir diese Beobachtung nun für unser Problem nutzen? Wir teilen die gegebenen Zahlen in zwei Hälften auf und bilden für jede Hälfte alle möglichen Teilsummen (höchstens $2^{\frac{n}{2}}$ viele):
Beispiel: Wir teilen die Zahlen 5 3 2 7 auf in 5 3 und 2 7.
5 3 2 7
-------- --------
0 0 -> 0 0 0 -> 0
0 1 -> 3 0 1 -> 7
1 0 -> 5 1 0 -> 2
1 1 -> 8 1 1 -> 9 (Alle Teilmengen)
Nun sortieren wir auf beiden Seiten die Folge der berechneten Teilsummen:
$0,3,5,8$ (alle Summen die mit 3 und 5 erreichbar sind) und $0,2,7,9$ (diejenigen, die mit 2 und 7 erreichbar sind).
Wir gehen in einer Folge mit einem Zeiger von links nach rechts und gleichzeitig in der anderen mit einem zweiten Zeiger von rechts nach links durch. Falls die aktuelle Summe zu gross ist, verschieben wir wie vorher den zweiten Zeiger nach links, ist sie zu klein den ersten Zeiger nach rechts.
0 3 5 8 0 2 7 9
^ ^
| |
Der Algorithmus arbeitet also wie folgt:
- Teile in 2 Mengen der Grösse $\frac{n}{2}$
- Berechne die Summen aller Teilmengen der beiden Mengen. Die Laufzeit ist $2^{n/2} \cdot 2 \cdot n/2$, weil es für beide Hälften $2^{n/2}$ Teilmengen gibt.
- Sortiere diese Summen in Laufzeit $\O(2^{n/2} \cdot \log(2^{n/2})) = \O(2^{n/2} \cdot {n/2})$.
- Suche nach einem Summenpaar, das genau $S$ ergibt. Dafür benötigen wir einen linearen Durchgang. Dieser hat Laufzeit $\O(2^{n/2})$.
Insgesamt haben wir also eine Laufzeit von $\O(n/2 \cdot 2^{n/2}) = \O(n/2 \cdot \sqrt{2}^n)$.
Ist das jetzt viel besser als $2^n$? Ja! Bei exponentiellen Algorithmen ist auch die kleinste Verbesserung an der Basis wichtig. Selbst $1.99^n$ ist exponentiell viel schneller als $2^n$.^[$1.99^n$ wächst im Vergleich zu $2^n$ um einen Faktor $\left(\frac{2}{1.99}\right)^n = 1.005^n$ langsamer. Somit ist ein Algorithmus mit Laufzeit $1.99^n$ um einen exponentiellen Faktor, und damit auch asymptotisch, schneller als einer mit Laufzeit $2^n$. Es gilt also $1.99^n \in \O(2^n)$ aber $2^n \notin \O(1.99^n)$.]
Diese Idee hat also die exponentielle Basis deutlich reduziert, aber wenn alle Zahlen in der Eingabe klein sind, dann ist unser dynamisches Programm (Laufzeit O($n \cdot s$)) unter Umständen deutlich schneller.
## Beispiel: Rucksack-Problem (Knapsack).
Wir betrachten nun ein weiteres bekanntes Problem: Angenommen Sie brechen in ein Juweliergeschäft ein und müssen nun ihren Rucksack möglichst optimal mit teuren Schmuckstücken füllen. Wie können Sie sich "schnell" entscheiden?
Formal: Sie haben $n$ Gegenstände. Jeder Gegenstand hat ein gewisses Gewicht und einen gewissen Wert. Wir möchten einen Rucksack packen und die Gegenstände möglichst so wählen, dass der Gesamtwert der gepackten Gegenstände möglichst gross ist. Der Rucksack kann allerdings nur ein gewisses Gesamtgewicht fassen, bevor er bricht.
*Gegeben*: $v_i$ und $w_i$ für $i=1, \ldots, n$, also Wert (value) und Gewicht (weight) der $n$ Gegenstände, sowie ein Gesamtgewicht $W$, das in den Rucksack passt.
Wir wollen nun die Gegenstände, die wir in den Rucksack nehmen, so wählen, dass wir möglichst viel Wert haben und dass wir Gesamtgewicht, das in den Rucksack passt, nicht überschreiten.
*Gesucht*: $I \subseteq \{1,..,n\}$, so dass $\sum_{i\in I} w_i \leq W$ und $\sum_{i \in I} v_i$ maximal.
*Beispiel*:
v 5 7 8 (values)
w 3 2 4 (weights)
**Erste Idee: Greedy / gierig:**
Wir sortieren die Gegenstände absteigend nach $v/w$ und nehmen dann fortlaufend den nächsten Gegenstand, solange dieser noch in den Rucksack passt.
Ist das gut? Gar optimal? Oder mindestens eine gute Approximation?
Es kann sehr schlecht werden. Angenommen es gibt zwei Gegenstände:
$v_1 = w_1 \cdot (1+\epsilon)$ mit $w_1$ sehr klein
$v_2 = w_2 = W$
oder konkreter:
$v_1 = 3$, $w_1=2$
$v_2 = 999999$, $w_2=999999$
mit $W=1000000$
Dann nehmen wir den ersten Gegenstand, weil er die höhere Wertdichte hat als der zweite Gegenstand, und haben dann für den zweiten. Damit sind wir beliebig schlechter als die optimale Lösung, die nur den zweiten Gegenstand nimmt.
#### Erster DP-Ansatz
Nun wollen wir ähnlich wie bei Subset-Sum vorhin einen DP-Ansatz verfolgen: Wir nehmen an, dass wir uns eine kleinere Gewichtsgrenze vorgeben und dann schauen wollen ob wir mit den ersten $i$ Gegenständen einen Mindestwert erreichen können. Also:
$machbar(i,v,w)=1$ wenn mit den ersten $i$ Gegenständen ein Gesamtgewicht $w$ nicht überschreiten und einen Gesamtwert $v$ mindestens erreichen können, und $machbar(i,v,w)=0$ falls nicht.
Das ist nur eine von vielen möglichen Formulierungen, aber eine, die sehr nach Induktion riecht. Denn nun gilt wiederum, dass $machbar(i,v,w)$ wahr ist, wenn wir $v$ und $w$ bereits mit den ersten $i-1$ Gegenständen erreichen können oder wenn wir mit den ersten $i-1$ Gegenständen den Wert $v-v_i$ und $w-w_i$ erreichen können. Es gilt also
$$
machbar(i,v,w) = machbar(i-1,v,w) \vee machbar(i-1,v-v_i,w-w_i).
$$
*Initialisierung*: Wenn die Gewichtsschranke negativ ist, dann ist die Antwort "Nein".
Wenn die Gewichtsschranke nicht negativ ist und der Mindestwert nicht positiv, dann ist die Antwort "Ja". Sonst bestimmen wir die Antwort mit einem Tableau.
*Aufruf*: Um zu prüfen, ob das gesamte Juweliergeschäft in den Rucksack passt, betrachten wir $machbar(n,\sum_{i=1}^n v_i,W)$. Doch das wird im Normalfall nicht möglich sein. Wir müssen daher $machbar(n,V,W)$ für alle $V \leq \sum_{i=1}^n v_i$ betrachten, um den maximalen Wert zu finden, den wir ergattern können.
Dies ergibt ein dreidimensionales Tableau der Grösse $n \cdot \sum_{i} {v_i} \cdot W$.
Die Berechnung jedes Eintrags kostet jeweils konstante Zeit. Als totale Laufzeit erhalten wir also Tableau-Grösse $\cdot$ Eintragsberechnungsdauer $= \O(n \cdot W \cdot \sum_i v_i)$. Ist dies bereits eine gute Laufzeit oder geht es noch schneller?
#### Zweiter DP-Ansatz
Überlegen wir uns, wo im Tableau die Antwort zu finden ist: Wir müssen für $i=n$ und $w=W$ den maximalen Mindestwert suchen, für den die Antwort Ja ist. Für fixierte $i$ und $w$ haben wir also ein derartiges Muster von Einträgen (aufsteigend nach Mindestwert v):
Y Y Y Y Y Y Y Y N N N N N
Wir finden das grösste Y also mit binärer Suche und können es uns merken.
Wenn wir aber schon wissen, dass die Einträge für fixe $i$ und $w$ die Form $(Y)^*(N)^*$ haben, dann können wir das Tableau auch einfach so abändern, dass wir uns nur gerade merken, wo die Y aufhören und die N beginnen. Wir merken uns also den maximalen erreichbaren Mindestwert.
Unser neues Tableau hat also die Grösse $n\cdot W$ und ein Eintrag $[i,j]$ enthält den maximalen Wert, den man mit den ersten $i$ Gegenständen und einer Gewichtsschranke $j$ erreichen kann. Ein Eintrag wird wie folgt berechnet:
$$ \text{erreichbarerWert} (i,w) = \max\begin{cases}
\text{erreichbarerWert} (i-1,w) \\
\text{erreichbarerWert} (i-1,w-w_i)+v_i) \\
\end{cases}$$
Somit erhalten wir ein neues Tableau der Grösse $n \cdot W$, und die Berechnung jedes Eintrages erfolgt weiterhin aus nur zwei vorhergehenden Einträgen. Die Gesamtlaufzeit des neuen dynamischen Programs ist also $\O(n \cdot W)$.
Das ist wiederum eine pseudopolynomielle Lösung. Bei sehr grossem $W$ kann es also immer noch sehr lange dauern, die Lösung zu berechnen. Deshalb wollen wir nun noch nach Lösungen suchen, die schnell laufen und Lösungen finden, die zwar vielleicht nicht optimal sind, aber immerhin sehr sehr nahe am Optimum sind.
#### Approximationsansatz
Wir wollen nun also versuchen, eine Näherung zu berechnen. Wir geben uns damit zufrieden, eine sehr gute, aber nicht optimale, Lösung zu finden. Wir möchten eine Garantie haben, dass die Lösung nicht wesentlich schlechter ist als die optimale Lösung. Das Ziel ist also eine Lösung $I$, sodass
$$
\sum_{i\in I} v_i \ge (1-\varepsilon) \sum_{i\in OPT} v_i,
$$
wobei $OPT$ die optimale Lösung bezeichnet. Wir möchten also, dass unsere Lösung garantiert nur um ein $\varepsilon$ von der optimalen Lösung abweicht.
Wir versuchen dies wiederum mit einem Tableau, in welchem wir das erreichbare minimale Gewicht für einen bestimmten Wert mit den Gegenständen 1 bis $i$ notieren.
0 1 ... n*Vmax
0
1
2
.
.
.
n
Wir haben also in Zeile $i$ die ersten $i$ Gegenstände zur Verfügung und in Spalte $v$ einen bestimmten möglichen Wert. Ein Eintrag $[i,v]$ sagt, welche Gewichtsgrenze nötig ist, damit man mit den ersten $i$ Gegenständen den Wert $v$ erreichen kann.
$$ \text{errGewicht}(i, v) = \min\begin{cases}
\text{errGewicht} (i-1,v)\\
\text{errGewicht} (i-1,v-v_i)+w_i)\\
\end{cases} $$
Die Tabellengrösse ist $\O(n \cdot \sum_i v_i)$ und die Berechnung eines Eintrags erfolgt in konstanter Zeit. Insgesamt haben wir also eine Laufzeit von $\O(n \cdot \sum_i v_i) = \O(n \cdot n \cdot v_{max})$
Was passiert nun, wenn wir bei jedem Gegenständen die letzten drei Stellen des Wertes $v_i$ streichen und hoffen dass dabei nicht viel kaputt geht?
*Approximation*:
- Bilde $v_i' = {\lfloor}{\frac{v_i}{K}}{\rfloor}$ für alle $i$. Wir bezeichnen mit *Problem'* das Rucksackproblem für die neue Eingabe $v_i', w_i, W$.
- Löse *Problem'* mit DP (Die Tabelle hat Grösse $n \cdot \sum_i v_i'$)
- Nimm die Lösung für Problem' als Lösung für das ursprüngliche Problem.
Ist das gut oder schlecht? Genauer: Ist das schnell? Und ist die Qualität gut?
Schauen wir uns unsere Tabelle an um die Laufzeit zu bestimmen. Da wir jeden Wert durch $K$ teilen und abrunden, wird die Summe der Werte mindestens $K$ mal kleiner. Vergleichen wir also $v_{max} = \max_i(v_i)$ (es gilt $\sum_i v_i \leq n \cdot v_{max}$) mit $v_{max}'= \max_i(v_i')$, dann sehen wir, dass das Tableau von Problem' Grösse $\O(n \cdot n \cdot \frac{v_{max}}{K})$ hat. Damit läuft der Algorithmus $K$ mal schneller.
Wie schlecht kann die Lösung dieser Approximation werden?
Beim Abrunden verlieren wir höchstens $K$, d.h. also
$$v_i - K \leq K \cdot {\lfloor}\frac{v_i}{K}{\rfloor} \leq v_i$$
Wir bezeichnen nun mit
$OPT$ ist die exakte optimale Lösung des Problems und mit
$OPT'$ ist die optimale Lösung des skalierten Problems. Dann gilt
$$\sum_{i \in OPT} v_i - n \cdot K
\leq \sum_{i \in OPT} v_i - \sum_{i \in OPT} K \\
\leq \sum_{i \in OPT} (v_i - K) \\
\leq \sum_{i\in OPT} K \cdot \lfloor v_i/K \rfloor\\
= K \cdot \sum_{i\in OPT} \lfloor v_i/K \rfloor \\
\leq K \cdot \sum_{i \in OPT'} \left\lfloor\frac{v_i}{K}\right\rfloor \\
= \sum_{i\in OPT'} K \cdot \lfloor v_i/K \rfloor \\
\leq \sum_{i \in OPT'} \frac{v_i}{K}
$$
Wir wollten höchstens $\varepsilon$ von der optimalen Lösung abweichen. Das können wir erreichen, indem wir $K$ so wählen, dass $nK = \varepsilon \sum_{i \in OPT} v_i$ gilt.
Das Optimum kennen wir zwar nicht, aber wir wissen, dass es mindestens $v_{max}$ ist (unter der Annahme, dass kein Gegenstand ein grösseres Gewicht hat als in den Rucksack überhaupt reinpassen; sonst könnten wir diesen Gegenstand sofort entfernen, da wir ihn sicher nicht einpacken). Also wählen wir $K$ stattdessen so, dass $nK = \varepsilon \cdot v_{max}$ gilt, also
$$K = \frac{\varepsilon \cdot v_{max}}{n}.$$
Also haben wir eine $(1-\varepsilon)$-Approximation in Zeit $\O(n^2\cdot \frac{v_{max}}{K}) = \O(\frac{n^3}{\varepsilon})$
Die Laufzeit hängt jetzt nur noch von $n$ und dieser Approximationsstellschraube $\varepsilon$ ab und ist völlig unabhängig von den Gewichten.
Sowas nennt man ein *Approximationsschema*: Sobald wir ein $\varepsilon$ gewählt haben, ist $\epsilon$ quasi eine Konstante und der Algorithmus hat dann polynomielle Laufzeit. Die Laufzeit ist also ein Polynom in $n$ und in $\frac{1}{\varepsilon}$. In diesem Fall nennt man das Approximationsschema dann voll-polynomielles Approximationsschema *(engl. FPTAS -- fully polynomial-time approximation scheme)*.
Hier haben wir ein Riesenglück, denn solche Algorithmen sind sehr selten. Häufig kommt es vor, dass z.B. $\frac{1}{\varepsilon}$ nicht als multiplikativer Faktor, sondern als Exponent auftaucht, z.B eine Laufzeit wie $\O(n^{\frac{1}{\varepsilon}})$. Für ein fixes $\varepsilon$ ist dies dann zwar immer noch polynomiell, aber die Potenz hängt nun von $\varepsilon$ ab.
## Rundreiseproblem (ergänzt HS 2017)
Wir erinnern uns an das Problem des Handlungsreisenden aus der allerersten Vorlesung. Gegeben sind $n$ Städte, nummeriert von $1$ bis $n$, mit einem Distanzmass $d_{i,j}$, welches für jedes $i\neq j$ die (gerichtete!) Distanz von Stadt $i$ nach $j$ beschreibt. Gesucht ist die kürzeste Rundreise, also eine Reise, welche jede Stadt genau einmal besucht und bei derselben Stadt startet und endet.
Gesucht ist also eine Permutation der Städte. Für $n=4$ und die Permutation $\pi = (2,3,1,4)$ sind die Kosten für die vier Teilstrecken aufsummiert $d_{\pi(1), \pi(2)} + d_{\pi(2), \pi(3)} + d_{\pi(3), \pi(4)} + d_{\pi(4), \pi(1)} = d_{2,3}+d_{3,1}+d_{1,4}+d_{4,2}$.
Warum wollen wir jede Stadt genau einmal besuchen? Könnte es nicht kürzer sein gewisse Städte mehrfach zu besuchen? Ja, das kann sein. In vielen (sinnvollen) Graphen gilt aber die Dreiecksungleichung $d_{i,j} \leq d_{i,k} + d_{k,j}$ für jedes $i,j,k$ weshalb sich dann Doppelbesuche nicht mehr lohnen. Ausserdem nehmen wir an, dass jede Stadt mit jeder anderen verbunden ist.
**Naive Lösung:** Die naive Lösung für dieses Problem wäre es alle $n!$ Permutationen durchzutesten, was wir in Zeit $\O(n\cdot n!)$ erledigen könnten. Das ist aber sehr langsam.
**Induktive Lösung:** Wir betrachten nun einzelne Reisestücke, also keine kompletten Rundreisen, sondern einfach einige aufeinanderfolgend besuchte Städte. Wir beschreiben ein Reisestück durch seinen Startknoten $i$, seinen Endknoten $j$ und die Menge der besuchten Knoten $S$.
Nach dem Optimalitätsprinzip wissen wir, dass für jedes Reisestück aus einer optimalen Rundreise gilt, dass es kürzest möglich ist. Für einen Reiseabschnitt mit fixem $i$, $j$ und $S$ benutzen wir also immer den kürzesten Weg unter allen Wegen, die von $i$ nach $j$ ebenfalls genau die Knotenmenge $S$ benutzen.
Damit bauen wir folgende Rekursion:
$$D(S,i,j) = \min_{k \in S,k \neq j}\left(D(S\setminus\{j\},i,k)+d_{k,j}\right)$$
Wir unterscheiden also welche Stadt wir als letztes besuchen. Dies führt zu einer Induktion über $|S|$, da die rekursiven Aufrufe jeweils weniger Städte besuchen.
Da wir eine Rundreise suchen, können wir den Startknoten beliebig fixieren. Sei beispielsweise immer $1 \in S$. Dann schreiben wir:
$$D(S,j) = \min_{k \in S, k\neq j}\left(D(S\setminus\{j\},k)+d_{k,j}\right)$$
Wir starten mit der Verankerung $D(\{1\},1)=0$ und wollen schliesslich $D([n],1)$ berechnen.
```javascript=
D({1},1)=0
for z = 2 to n do
for each S \subseteq {1,...,n} mit |S|=z und 1 in S:
D(S,1) = inf
for each j in S, j ≠ 1 do
D(S,j) := min_{k in S, k ≠ j}(D(S\{j},k)+d_{k,j})
return min_j(D([n],j)+d_{j,1})
```
*Laufzeit*: Wir haben ein Tableau der Grösse $n \cdot 2^n$ und benötigen $\O(n)$ Zeit, um einen Eintrag zu berechnen. Die Gesamtzeit von $\O(n^2 \cdot 2^n)$ ist immer noch viel, aber drastisch weniger als $\O(n!)$.
Sign in with Wallet
Connect another wallet