22 lines
945 B
TeX
22 lines
945 B
TeX
\section{Metrisches TSP}
|
|
\begin{tasks}
|
|
\item
|
|
Der Algorithmus für Minimale Spannbäume von Prim fügt in jedem Schritt die den Schnitt
|
|
kreuzende Kante zum Baum hinzu, deren Kosten unter allen anderen kreuzenden Kanten minimal ist.
|
|
|
|
\algt{CompleteHamilton} fügt denselben Knoten hinzu, da der Knoten $v$ nicht in $C$ liegt, also den Schnitt kreuzt und den kleinsten Abstand zu den Knoten in $C$ hat.
|
|
\points{2}
|
|
|
|
\item
|
|
In jedem Schritt von \algt{CompleteHamilton} wird eine Kante $wu$ in $C$ durch zwei Kanten
|
|
$wv$ und $vu$ ersetzt. Da $wv$ die minimale kreuzende Kante ist und $G$ die Dreiecksungleichung erfüllt, ist $c(v, u) \leq c(u, w) + c(w, v)$ und ist somit nicht länger als der
|
|
doppelte Minimale Spannbaum, der analog zu \algt{CompleteHamilton} berechnet wird.
|
|
Damit gilt wieder:
|
|
$$
|
|
c(Kreis) = 2 \cdotp c(MSB) \leq 2 \cdotp OPT
|
|
$$
|
|
Da eine TSP-Tour mit einer Kante weniger ein Spannbaum ist.
|
|
\points{4}
|
|
|
|
|
|
\end{tasks}
|