Skip to content
Snippets Groups Projects

forbetter the example

Merged forbetter the example
(removed):master into master
Merged Dominic Meiser requested to merge (removed):master into master
Compare
and
1 file
+ 43
− 34
Compare changes
  • Side-by-side
  • Inline
suchbaum/suchbaum.tex
+ 43
− 34
@@ -11,6 +11,7 @@
\usepackage{tikz}
\usepackage{cclicenses}
\usepackage[left=2.00cm, right=2.00cm, top=2.00cm, bottom=2.00cm]{geometry}
\usepackage{multicol}
\begin{document}
\section{Optimale Suchbäume}
@@ -21,7 +22,7 @@
w_{i,j} = \sum_{k=i}^{j}p_k,\ mit\ 1 \leq i \leq j \leq n
\end{equation}
Weiterhin ist $w_{i, j} = 0$, falls $1 \leq i \leq j \leq n$ nicht gilt.
Ein Baum der die Schlüssel $i$ bis $j$ enthält, wird im Erwartungswert bei einer Suche nach einem zufälligen Schlüssel $w_{i, j}$ mal besucht.
Ein Baum, der die Schlüssel $i$ bis $j$ enthält, wird im Erwartungswert bei einer Suche nach einem zufälligen Schlüssel $w_{i, j}$ mal besucht.
\begin{equation}
\label{eq:eij}
@@ -47,7 +48,6 @@
\subsection{Konstruktion des optimalen Suchbaumes}
Der optimale Suchbaum wird durch $e_{1, n}$ dargestellt. Bei der Berechnung von $e_{1, n}$ wurde folgender Term berechnet: $\min_{i \leq r \leq j} (e_{i, r - 1} + e_{r + 1, j})$. Um diesen auszurechnen wurde ein eindeutiges r (Wurzelknoten) gewählt. Dieser ist nun die Wurzel unseres Baumes. Um den vollständigen Baum aufzubauen berechnen wir nun rekursiv die Teilbäume $e_{1, r - 1}$ und $e_{r + 1, n}$. $e_{i, j}$ mit $i > j$ wird zu einem leeren (Teil-)Baum. $e_{i, i}$ wird zu einem Blatt.
\newpage
\section{Aufgabenbeispiel}
Konstruieren Sie einen optimalen Suchbaum für die Schlüssel A, B, C, D. Auf diese wird mit den Wahrscheinlichkeiten 0.2, 0.3, 0.1 und 0.4 zugegriffen.
@@ -84,34 +84,27 @@
\begin{tabular}{c | cccc}
$w_{i, j}$ & A & B & C & D \\ \hline
A & 0.2 & & & \\
B & 0 & \underline{0.3} & \dashuline{0.4} & \cellcolor[HTML]{c0c0c0} \\
B & 0 & \underline{0.3} & \cellcolor{green!70!white}0.4 & \cellcolor[HTML]{c0c0c0} \\
C & 0 & 0 & \underline{0.1} & \\
D & 0 & 0 & 0 & \dashuline{\underline{0.4}}
D & 0 & 0 & 0 & \cellcolor{green!70!white}\underline{0.4}
\end{tabular}
\end{wraptable}
Wir gehen im folgenden davon aus, dass wir die Tabelle bereits wie rechts berechnet haben. Schauen wir uns eine arbiträre Zelle der Tabelle an, beispielsweise $w_{B, D}$ (grau eingefärbt). Diese wird durch die Formel folgendermaßen berechnet (unterstrichen in der Tabelle eingezeichnet): $w_{B,D} = \sum_{k=B}^{D}p_k = p_B + p_C + p_D$. Nutzen wir an dieser Stelle dynamische Programmierung\footnote{\href{https://de.wikipedia.org/wiki/Dynamische\_Programmierung}{https://de.wikipedia.org/wiki/Dynamische\_Programmierung}}, können wir den bereits berechneten Wert $w_{B, C}$ nehmen und dort $w_{D, D}$ aufaddieren (Unterstrichen mit Unterbrechungen). Mit diesen Informationen können wir nun die vollständige Tabelle errechnen:\\
\begin{tabular}{c | cccc}
$w_{i, j}$ & A & B & C & D \\ \hline
A & 0.2 & 0.5 & 0.6 & 1.0 \\
B & 0 & 0.3 & 0.4 & 0.8 \\
C & 0 & 0 & 0.1 & 0.5 \\
D & 0 & 0 & 0 & 0.4
\end{tabular}
\subsection{Ausfüllen der $e_{i, j}$ Tabelle}
\begin{wraptable}{r}{7.5cm}
\vspace{-2.5em}
Wir gehen im folgenden davon aus, dass wir die Tabelle bereits wie rechts berechnet haben. Schauen wir uns eine arbiträre Zelle der Tabelle an, beispielsweise $w_{B, D}$ (grau eingefärbt). Diese wird durch die Formel folgendermaßen berechnet (unterstrichen in der Tabelle eingezeichnet):
$$ w_{B,D} = \sum_{k=B}^{D}p_k = p_B + p_C + p_D $$
Da wir $ p_B + p_C $ bereits berechnet haben, können wir an dieser Stelle dynamische Programmierung\footnote{\href{https://de.wikipedia.org/wiki/Dynamische\_Programmierung}{https://de.wikipedia.org/wiki/Dynamische\_Programmierung}} benutzen. Wir addieren also den bereits berechneten Wert $w_{B, C}$ mit $w_{D, D}$ (grün markiert). Damit können wir nun die vollständige Tabelle errechnen:\\
\begin{center}
\begin{tabular}{c | cccc}
$e_{i, j}$ & A & B & C & D \\ \hline
\underline{A} & \dotuline{0.2 (A)} & \dashuline{0.7 (B)} & \cellcolor[HTML]{c0c0c0} & \\
B & 0 & 0.3 (B) & \underline{0.5 (B)} & \\
C & 0 & 0 & \dotuline{0.1 (C)} & \\
D & 0 & 0 & \dashuline{\ \ 0\ \ } & 0.4 (D)
$w_{i, j}$ & A & B & C & D \\ \hline
A & 0.2 & 0.5 & 0.6 & 1.0 \\
B & 0 & 0.3 & 0.4 & 0.8 \\
C & 0 & 0 & 0.1 & 0.5 \\
D & 0 & 0 & 0 & 0.4
\end{tabular}
\end{wraptable}
\end{center}
Wir gehen im folgenden davon aus, dass wir die Tabelle bereits wie rechts berechnet haben. Schauen wir uns eine arbiträre Zelle der Tabelle an, beispielsweise $e_{A, C}$ (grau eingefärbt). Diese wird durch die Formel folgendermaßen berechnet:
\subsection{Ausfüllen der $e_{i, j}$ Tabelle}
Wir gehen im folgenden davon aus, dass wir die Tabelle bereits wie unten berechnet haben. Schauen wir uns eine arbiträre Zelle der Tabelle an, beispielsweise $e_{A, C}$ (grau eingefärbt). Wir erinnern uns daran, dass alle Werte außerhalb der Tabelle sowie unterhalb der Diagonale immer $0$ sind. Unsere Tabellenzelle wird durch die Formel folgendermaßen berechnet:
\begin{equation}
\begin{split}
e_{A, C} & = w_{A,C} + \min_{A \leq r \leq C} (e_{A, r - 1} + e_{r + 1, C}) \\
@@ -122,15 +115,31 @@
& = 0.9 (B)
\end{split}
\end{equation}
(Beachte, dass wegen dem Hinweis zu Formel \ref{eq:eij}, gilt: $e_{A, A - 1} = 0 = e_{C + 1, C}$)\\
An dieser Stelle haben wir als r (Wurzelknoten) bei unserem Minimum den Knoten B gewählt. Die Knoten A und C erzeugen an der Stelle $\min_{A \leq r \leq C} (e_{A, r - 1} + e_{r + 1, C})$ einen höheren Wert und werden somit nicht ausgewählt. Die verschiedenen Teile aus der Menge von der wir das Minimum berechnen sind in der Tabelle durch Unterstreichung, Unterstreichung mit Punkten und Unterstreichung mit Strichen dargestellt. Führen wir die Berechnung für allen anderen Zellen fort, entsteht folgende Tabelle:\\
\begin{tabular}{c | cccc}
$e_{i, j}$ & A & B & C & D \\ \hline
A & 0.2(A) & 0.7 (B) & 0.9 (B) & 1.8 (B) \\
B & 0 & 0.3 (B) & 0.5 (B) & 1.3 (D) \\
C & 0 & 0 & 0.1 (C) & 0.6 (D) \\
D & 0 & 0 & 0 & 0.4 (D)
\end{tabular}
Anders ausgedrückt: Wir schauen uns jede mögliche Wurzel von $A$ bis $C$ an, addieren die Erwartungswerte und merken uns davon den Kleinsten. Es ergeben sich folgende Möglichkeiten:
\begin{center}
\scriptsize
\setlength{\tabcolsep}{3pt}
\begin{tabular}{ccccc | c | cccc | c | cccc}
\hspace*{15pt} & \cellcolor{green!70!white} A & B & C & D & $e_{i,j}$ & A & \cellcolor{orange!60!white} B & C & D & $e_{i,j}$ & A & B & \cellcolor{blue!45!white} C & D \\ \hline
\cellcolor{green!70!white} & 0.2 (A) & 0.7 (B) & \cellcolor[HTML]{c0c0c0} & & A & \cellcolor{orange!60!white} 0.2 (A) & 0.7 (B) & \cellcolor[HTML]{c0c0c0} & & A & 0.2 (A) & \cellcolor{blue!45!white} 0.7 (B) & \cellcolor[HTML]{c0c0c0} & \\
& 0 & 0.3 (B) & \cellcolor{green!70!white} 0.5 (B) & & B & 0 & 0.3 (B) & 0.5 (B) & & B & 0 & 0.3 (B) & 0.5 (B) & \\
& 0 & 0 & 0.1 (C) & & C & 0 & 0 & \cellcolor{orange!60!white} 0.1 (C) & & C & 0 & 0 & 0.1 (C) & \\
& 0 & 0 & 0 & 0.4 (D) & D & 0 & 0 & 0 & 0.4 (D) & D & 0 & 0 & \cellcolor{blue!45!white} 0 & 0.4 (D) \\
\end{tabular}
\setlength{\tabcolsep}{6pt}
\end{center}
Wir sehen also, dass wir das Minimum von $0+0.5$ (mit Wurzel A), $0.2+0.1$ (mit Wurzel B) und $0.7+0$ (mit Wurzel C) suchen. Dies wird genau durch obige Formel beschrieben. Dieses Minimum liegt bei dem Wert $0.3$ für die Wurzel B. Achtung: Diese Wurzel ist optimal für den von uns betrachteten Teilbaum von A bis C, nicht zwingendermaßen für den gesamten Baum! Führen wir die Berechnung für allen anderen Zellen fort, entsteht folgende Tabelle:\\
\begin{center}
\begin{tabular}{c | cccc}
$e_{i, j}$ & A & B & C & D \\ \hline
A & 0.2(A) & 0.7 (B) & 0.9 (B) & 1.8 (B) \\
B & 0 & 0.3 (B) & 0.5 (B) & 1.3 (D) \\
C & 0 & 0 & 0.1 (C) & 0.6 (D) \\
D & 0 & 0 & 0 & 0.4 (D)
\end{tabular}
\end{center}
\subsection{Konstruktion des optimalen Suchbaums}
Nun können wir den optimalen Suchbaum konstruieren. Hierzu müssen wir den Wurzelknoten von $e_{A, D}$ als Wurzel schreiben. Nun müssen wir noch $e_{A, A}$ und $e_{C, D}$ aus der Tabelle ablesen. $e_{A, A}$ hat als Wurzel $A$ und keine Kinder. $e_{C, D}$ hat als Wurzel (siehe Tabelle) D, also muss noch $e_{C, C}$ abgelesen werden. Nun haben wir den vollständigen Baum aufgebaut.\\
@@ -163,5 +172,5 @@
Von links nach rechts wird der Baum langsam aufgebaut. Dabei wurden Rekursionen, die auf der gleichen Höhe des Baumes sind, zeitlich durchgeführt.
\section{Autor und Lizenz}
Dieses Werk wurde erstellt von Maximilian Hippler. Bei Fragen, Anregungen oder Kritik stehe ich gerne unter \href{mailto:maximilian.hippler@rwth-aachen.de}{maximilian.hippler@rwth-aachen.de} zur Verfügung. Dieses Werk ist lizenziert unter einer \href{http://creativecommons.org/licenses/by-nc-sa/4.0/}{Creative Commons Namensnennung - Nicht-kommerziell - Weitergabe unter gleichen Bedingungen 4.0 International Lizenz} \byncsa. Version \today{}. Die aktuellste Version dieses Dokuments befindet sich stets unter \href{https://git.rwth-aachen.de/maxemann96/dsal}{https://git.rwth-aachen.de/maxemann96/dsal}
Dieses Werk wurde erstellt von Maximilian Hippler. Bei Fragen, Anregungen oder Kritik stehe ich gerne unter \href{mailto:maximilian.hippler@rwth-aachen.de}{maximilian.hippler@rwth-aachen.de} zur Verfügung. Dieses Werk ist lizenziert unter der \href{http://creativecommons.org/licenses/by-nc-sa/4.0/}{Creative Commons BY-NC-SA 4.0 International License} \cc\byncsa. Version von \today{}. Die aktuellste Version dieses Dokuments befindet sich stets unter \href{https://git.rwth-aachen.de/maxemann96/dsal}{https://git.rwth-aachen.de/maxemann96/dsal}
\end{document}
\ No newline at end of file