Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
-$\mathcal{NP}$. Das heißt, dass keine Verfahren bekannt sind, die diese
-Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese Probleme
-außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine Konsequenz,
-dass es effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls
-sich hingegen herausstellt, dass diese Probleme neben $\mathcal{NP}$ auch in
-der Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es
-ist jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr
-groß sein würden, so dass der praktische Nutzen fraglich bleibt.
-
-Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
-die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen
-Lösungen}, als einzige Ausgabe des Algorithmus zuzulassen, wird eine
-"`möglichst gute"' Lösung ausgegeben. Viele dieser Optimierungsalgorithmen
-orientieren sich an Vorgängen in der Natur. Beispielsweise imitieren die
-„Ameisenalgorithmen“ das Verhalten von Ameisen auf der Futtersuche, um kurze
-Rundreisen auf Graphen zu berechnen.
+$\mathcal{NP}$-vollständig. Das heißt, dass keine Verfahren bekannt sind, die
+diese Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese
+Probleme außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine
+Konsequenz, dass es für diese Probleme keine effizienten exakten Algorithmen
+gibt. Stellt sich hingegen heraus, dass diese Probleme neben
+$\mathcal{NP}$-vollständig auch in der Komplexitätsklasse~\textit{P} liegen,
+gibt es effiziente Algorithmen. Es ist jedoch wahrscheinlich, dass die
+Zeitkonstanten solcher Algorithmen sehr groß wären, so dass der praktische
+Nutzen fraglich bleibt.
+
+Aus diesem Grund besteht die Notwendigkeit, einen Kompromiss einzugehen: Statt
+die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen Lösungen}
+als einzige Ausgabe des Algorithmus zuzulassen, wird eine "`möglichst gute"'
+Lösung ausgegeben. Dafür verringert sich die Laufzeit des Algorithmus. Viele
+dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur.
+Beispielsweise imitieren die „Ameisenalgorithmen“ das Verhalten von Ameisen
+auf der Futtersuche, um kurze Rundreisen auf Graphen zu berechnen.
Bei {\em Evolutionären Algorithmen} stand die Evolution Pate. Die Grundidee
ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
-% \todo{Drei oder vier Verfahren?}
+\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.}
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
verleiht dem Sortiernetzwerk seinen Namen.
Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
-Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
+Instanzen des Netzwerks, deren Leitungszahl $n = 2^d$ eine Zweierpotenz ist.
Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.
-Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
+Für den wichtigen Spezialfall, dass $n = m = 2^{d-1}$ beträgt, lässt sich die
Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
erste Rekursionsschritt der OEM-Konstruktion fügt
$\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
\end{displaymath}
Komparatoren eingespart. Damit ergibt sich
\begin{displaymath}
- K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
+ K\left(n = 2^{d-1}, n = 2^{d-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
\end{displaymath}
-für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
+für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^d)$
benötigt werden.
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
(n)\right)^2\right)$ enthalten ist.
-Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
+Für den wichtigen Spezialfall, dass $n = 2^d$ eine Zweierpotenz ist, kann die
Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
\begin{displaymath}
- k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
+ k(n = 2^d) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
\end{displaymath}
gilt.
projects / diplomarbeit.git / blobdiff