SN-Evolution: Versuche mit dem Odd-Even-Mischer überarbeitet.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 8e7beca..98dd41e 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -1460,13 +1460,20 @@ Im vorherigen Abschnitt wurde gezeigt, dass der
 Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
 \emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
 Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
-wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung
-des \emph{Odd-Even}-Mischers findet, erreichen das
+erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
+\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
 \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
 nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
-Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Wenn $n$ keine
-Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke
-ausgeben, die schneller als \oes{n} sind.
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
+
+Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
+mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
+beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
+\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
+\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
+Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
+sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.
 
 %\begin{figure}
 %\begin{center}
@@ -1500,6 +1507,43 @@ ausgeben, die schneller als \oes{n} sind.
 %\label{fig:10-e2-1239014566}
 %\end{figure}
 
+\begin{table}\label{tbl:sn-ev-oem-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
+\cline{2-5}
+          & Komp. & Schichten & Komp. & Schichten \\
+\hline
+        8 &   19 &         6 &         19 &         6 \\
+        9 &   26 &         8 &         26 &         8 \\
+       10 &   31 &         9 &         31 &         9 \\
+       11 &   38 & \Gcell  9 & \Gcell  37 &        10 \\
+       12 &   43 & \gcell  9 & \gcell  41 &        10 \\
+       13 &   48 &        10 &         48 &        10 \\
+       14 &   53 &        10 &         53 &        10 \\
+       15 &   59 &        10 &         59 &        10 \\
+       16 &   63 &        10 &         63 &        10 \\
+       17 &   74 &        12 &         74 &        12 \\
+       18 &   82 &        13 &         82 &        13 \\
+       19 &   93 & \Gcell 13 & \Gcell  91 &        14 \\
+       20 &   97 &        14 &         97 &        14 \\
+       21 &  108 & \Gcell 14 & \Gcell 107 &        15 \\
+       22 &  117 & \gcell 14 & \gcell 114 &        15 \\
+       23 &  129 & \Gcell 14 & \Gcell 122 &        15 \\
+       24 &  128 &        15 & \gcell 127 &        15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+  unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
+  Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
+  gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
+  nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
+  1$, $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
 %\input{shmoo-aequivalenz.tex}
 
 \newpage