+die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
+Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
+mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
+
+Dass die Sortiernetzwerke, die mit den Schnittmustern von
+\textsc{SN-Evolution-Cut} entstehen, keine erkennbare Struktur haben, ist
+jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der
+Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
+\emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(n)$ und
+$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-k)$-Netzwerk.
+
+\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
+
+Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
+genauso effizient und schnell wie das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
+Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
+\oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
+tabellarisch.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 19 & & & & & & & & & & & & & & & \\
+ 10 & 19 & 26 & & & & & & & & & & & & & & \\
+ 11 & 19 & 26 & 31 & & & & & & & & & & & & & \\
+ 12 & 19 & 26 & 31 & 37 & & & & & & & & & & & & \\
+ 13 & 19 & 26 & 31 & 37 & 41 & & & & & & & & & & & \\
+ 14 & 19 & 26 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
+ 15 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
+ 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
+ 17 & 19 & 26 & 31 & 38 & 41 & 48 & 53 & 59 & 63 & & & & & & & \\
+ 18 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & & & & & & \\
+ 19 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & & & & & \\
+ 20 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & & & & \\
+ 21 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & & & \\
+ 22 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & & \\
+ 23 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & \\
+ 24 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
+\hline
+\end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-oes-efficiency}
+\end{table}
+
+\begin{figure}
+ \centering
+ \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{17} erzeugt.]{\input{images/11-ec-from-oes17-fast.tex}\label{fig:11-ec-from-oes17-fast}}
+ \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{18} erzeugt.]{\input{images/12-ec-from-oes18-fast.tex}\label{fig:12-ec-from-oes18-fast}}
+ \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
+ 11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+ erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
+ sind.}
+ \label{fig:ec-oes-fast_networks}
+\end{figure}
+
+Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
+schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
+$m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
+Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
+war allerdings in allen beobachteten Fällen nur dann möglich, wenn
+zusätzliche Komparatoren in Kauf genommen wurden. In den
+Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
+Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
+beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
+Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
+
+Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim
+\emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die
+Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war
+jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere
+Geschwindigkeit zu erreichen.
+
+In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von
+\textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots
+19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles
+19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die
+resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit
+$k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
+\emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in
+13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 6 & & & & & & & & & & & & & & & \\
+ 10 & 6 & 8 & & & & & & & & & & & & & & \\
+ 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
+ 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
+ 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
+ 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
+ 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
+ 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
+ 17 & 6 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
+ 18 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
+ 19 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
+ 20 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
+ 21 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
+ 22 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
+ 23 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
+ 24 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\oes{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\end{tabular}
+ \end{center}
+ \caption{Anzahl der Schichten der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-oes-speed}
+\end{table}
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 91 & 14 \\
+ 21 & 91 & 14 \\
+ 22 & 91 & 14 \\
+ 23 & 91 & 14 \\
+ 24 & 91 & 14 \\
+ 25 & 91 & 14 \\
+ 26 & 91 & 14 \\
+ 27 & 91 & 14 \\
+ 28 & 91 & 14 \\
+ 29 & 95 & 13 \\
+ 30 & 93 & 13 \\
+ 31 & 93 & 13 \\
+ 32 & 93 & 13 \\
+ 33 & 93 & 13 \\
+ 34 & 93 & 13 \\
+ 35 & 93 & 13 \\
+ 36 & 93 & 13 \\
+ 37 & 93 & 13 \\
+ 38 & 93 & 13 \\
+ \hline
+ \bs{19} & 98 & 14 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Komparatoren und Schichten von Sortiernetzwerken, die von
+ \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$
+ ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die
+ Effizienz von 91~Komparatoren nicht mehr erreichbar.}
+ \label{tbl:ec-oes-19}
+\end{table}
+
+In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
+viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
+Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
+$\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen
+Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten
+unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen.
+Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut}
+gestartet mit $\operatorname{OES}(32)$ sehr schnell\footnote{Ein
+entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen
+geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe
+Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf
+derzeitigen Computern.} ein gutes 16-Schnittmuster findet.
+
+Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
+bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
+$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
+8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
+Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
+Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-oes32-cut.tex}
+ \end{center}
+ \caption{Visualisierung eines 16-Schnittmusters, das auf
+ $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
+ bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
+ resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
+ dargestellt.}
+ \label{fig:16-ec-from-oes32-cut}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-oes32.tex}
+ \end{center}
+ \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
+ Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
+ einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
+ berechnet wurde. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
+ \label{fig:16-ec-from-oes32}
+\end{figure}
+
+Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
+4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
+Beobachtung kann man das regelmäßige Schnittmuster
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
+ -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
+Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
+Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
+32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
+ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-ec-from-oes64.tex}
+ \end{center}
+ \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
+ Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
+ \label{fig:32-ec-from-oes64}
+\end{figure}
+
+Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
+erzeugten Sortiernetzwerke die Effizienz des
+\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
+beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
+43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
+beider Sortiernetzwerke ist mit 10~Schichten identisch.
+
+Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
+und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
+verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
+Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
+22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
+Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
+Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
+werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
+gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
+werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
+16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
+dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
+sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
+angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
+\oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
+
+\begin{figure}
+ \centering
+ \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
+ 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk generiert
+ wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
+ \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
+ das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
+ generiert
+ wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
+ \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
+ Ergebnis von der Bewertungsfunktion ab.}
+ \label{fig:12-ec-from-oes24}
+\end{figure}