Erläuterungen zu Dijkstra

1 files changed, 6 insertions, 28 deletions

diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex
index 756f6e1..4a27737 100644
--- a/buch/papers/verkehr/section1.tex
+++ b/buch/papers/verkehr/section1.tex
@@ -15,35 +15,13 @@ Weiter wird zwischen informierten und uninformierten Algorithmen differenziert.
 Eine besondere Art von Suchalgorithmen stellen die sogenannten Greedy-Algorithmen, zu deutsch gierige Algorithmen, dar. Sie zeichnen sich dadurch aus, dass stets der günstigste Weg verfolgt wird und davon ausgehend der darauffolgende, günstigste Folgezustand ausgewählt wird. Am Beispiel eines Verkehrsnetzes ist somit gewährleistet, dass beim Antreffen des Zielknotens auch der günstigste Pfad gefunden wurde.
 
 \subsection{Dijkstra-Algorithmus}
-Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden.
-Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann.
-Vereinfacht wird beim Dijkstra-Algorithmus, ausgehend von einem Startknoten so lange dem kürzesten Pfad gefolgt, bis der Zielknoten erreicht wird. Dabei muss für jeden besuchten Knoten die Kostenfunktion als auch der Pfad dahin (vorheriger Knoten) gespeichert werden.
-Dadurch wird hingegen garantiert, dass, wenn der Zielknoten erreicht wird, auch der kürzeste Pfad gefunden wurde.
-Grundlegende Voraussetzung für den Dijkstra-Algorithmus ist die strikte Positivität der Kantengewichte. Andernfalls würde ein wiederholtes Ablaufen einer Kante mit negativem Gewicht zu einer stetigen Reduktion der Kostenfunktion führen, was zu einer unendlichen Schlaufe führen würde.
-
-Gegeben sei ein Netzwerk mit $n$ Knoten und dem Startknoten $a$.
-Alle Kanten sind mit $k(i, j)$ bewertet.
-Gesucht wird der kürzeste Pfad zwischen dem Startknoten und dem Knoten im Netz.
-$D(i)$ ist die kürzeste Distanz vom Startknoten $a$ zum Knoten $i, V(i)$ ist der unmittelbare Vorgängerknoten vom Knoten $i$ auf dem kürzesten Weg vom Startknoten $a$ zum Konten $i$ und die Menge $M$ ist die Menge einer bestimmten Auswahl an Knoten.
-
-Dabei gilt
-\begin{equation}M={a}\end{equation}
-\begin{equation}D(a)=0\end{equation} wobei
-\begin{equation}D(i)=\infty\end{equation} und
-\begin{equation}i \neq a \end{equation}
-Ausserdem gilt \begin{equation}V(i)=(-) \text{für alle Knoten $i$}\end{equation}\\
+Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Informatikprofessor Edsger Dijkstra. Er gehört zur Klasse der uninformierten Greedy-Algorithmen. Zudem ist die Optimalität bei strikter Positivität des Graphen gewährleistet.
+Vorteilhaft ist die einfache Implementierung. Abhängig von der Programmiersprache sind zwischen 30 und 40 Zeilen an Code ausreichend, damit er den kürzesten Pfad zwischen einem Startknoten $a$ und Zielknoten $b$ finden kann. Die für dieses Paper verwendete Funktion verwendet eine abgewandelte Form der gewichteten Adjazenz-Matrix $A$, für welche gilt:
+Der Matrix-Eintrag $A_{i,j}$ weist das Kantengewicht der Kante von Knoten $j$ nach $i$ auf. Falls keine Kante zwischen $j$ und $i$ vorhanden ist, beträgt der Eintrag $\infty$. Dies vereinfacht die Implementierung zur Bestimmung des nächst-günstigsten Pfades.
+Zudem werden zwei Hilfs-Vektoren $\vec{d}$ und $\vec{b}$ der Länge $n$ eingeführt, wobei $n$ die Anzahl Knoten des Graphen ist. Im Vektoreintrag $\vec{d}(i)$ wird das kummulierte Kantengewicht zur Erreichung von Knoten $i$ vom Startknoten $a$ gespeichert. Der Eintrag $\vec{d}(a)$ beträgt somit $0$. Im Vektor $\vec{b}$ wird zudem vermerkt, falls ein Knoten bereits als Ziel eines kürzesten Pfads gefunden wurde und somit für die weitere Suche nicht mehr berücksichtigt werden muss ($\vec{b}(i)=1$, sonst $\vec{b}(i)=0$).
 
-%THEORIE...
-Iteration
-
-1. Auswahl eines Knotens \begin{equation} K\in M \text{mit} D(K)=D(i);i\in M\end{equation}
-
-2. Für alle Nachfolger $N(j)$ vom Knoten $K$ gilt:
-\begin{equation}D(K) + k_Kj < D(j)\end{equation} dann wird \begin{equation}D(j) = D(K) + k_Kj, V(j) = K\end{equation} gesetzt und somit wird der Knoten $j$ in die Menge $M$ aufgenommen.
-
-3. Der ausgewählte Knoten \begin{equation}K\in M\text{wird aus der Menge herausgelöscht}\end{equation}\\
-Diese drei Schritte werden so lange wiederholt bis gilt
-\begin{equation}M=\{\}\end{equation}
+Ausgehend vom Startknoten $a$ wird nun anhand der Matrix $A$ in der Spalte $a$ nach dem kleinsten Eintrag gesucht. Somit wird der Folgeknoten $c$ gefunden. Dieser Vorgang wird nun wiederholt, wobei jedoch sämtliche von Knoten $a$ und $c$ erreichbaren Knoten berücksichtigt werden, die noch nicht besucht wurden. In anderen Worten alle nicht verschwindenden Einträge $i$ der Spalten $a$ und $c$ der Matrix $A$, für welche gilt $\vec{b}(i)=0$.
+Diese Iteration wird solang durchgeführt, bis der Folgeknoten dem Zielknoten entspricht.
 
 \subsection{A*-Algorithmus}
 Suchalgorithmen werden nach einfachen (uninformierte) und heuristischen (informierten) Algorithmen unterschieden. Während einfache Algorithmen den Suchraum intuitiv durchsuchen, beziehen heuristische Algorithmen Wissen über den Suchraum mit ein.