Erläuterungen zu A*

1 files changed, 6 insertions, 14 deletions

diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex
index 4a27737..6f8f2b7 100644
--- a/buch/papers/verkehr/section1.tex
+++ b/buch/papers/verkehr/section1.tex
@@ -20,27 +20,19 @@ Vorteilhaft ist die einfache Implementierung. Abhängig von der Programmiersprac
 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$).
 
-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$.
+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$. Ausschlaggebend für die folgende Auswahl ist die Summe der kummulierten Kantengewichte und des Kantengewichts des nächsten Knotens. Als Beispiel zur Erreichung von Knoten $k$ über Knoten $j$:
+\begin{equation}
+\vec{d}(k)=\vec{d}(j)+A(k,j)
+\end{equation}
 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.
-Der A*-Algorithmus geht auf seine Erfinder Peter Hart, Nils Nilsson und Bertram Raphael zurück, die den Algorithmus erstmals im Jahr 1968 beschrieben.
-Der A*-Algorithmus ist ein heuristischer Suchalgorithmus, der den kürzesten Pfad zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten berechnet.
-Im Gegensatz zu einfachen Suchalgorithmen, wird beim A*-Algorithmus eine Schätzfunktion, die sogenannte Heuristik, verwendet. Dies ermöglicht ein zielgerichtetes Suchen und gleichzeitig wird die Laufzeit verringert.
-Ausserdem findet der A*-Algorithmus immer eine optimale Lösung, sofern eine vorhanden ist.
-Der A*-Algorithmus gilt als Erweiterung des Dijkstra-Algorithmus.
+Der A*-Algorithmus basiert auf dem Dijkstra-Algorithmus, verwendet jedoch eine Heuristik zur Abschätzung der günstigsten Suchrichtung. Somit handelt es sich um einen informierten Greedy-Algorithmus, der abhängig von der verwendeten Heuristik auch optimal sein kann. Er wurde von Peter Hart, Nils Nilsson und Bertram Raphael entwickelt.
 
 \subsection{Anwendung A*-Algorithmus}
 Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch eine optimale Lösung darstellt.\\
 
-Die Kantengewichte werden für jeden Knoten in Form einer Funktion dargestellt
-\begin{equation}f(n)=g(n)\end{equation} mit
-\begin{equation}g(n)=\text{Summe aller Kantengewichte vom Startknoten bis n}\end{equation}\\
-Der A*-Algorithmus erweitert die Vorgehensweise des Algorithmus von Dijkstra um die Heuristik $h(n)$, die für jeden Knoten $n$ die geschätzte Entfernung zum Zielknoten beschreibt.
-Somit gilt:
-\begin{equation}f(n)=g(n)+h(n)\end{equation}\\
-Wie auch der Algorithmus von Dijkstra findet der A*-Algorithmus die optimalste Lösung.
+Der A*-Algorithmus unterscheidet sich vom Dijkstra-Algorithmus dahingehend, dass bei der Auswahl des Folgeknotens, nicht nur die Summe der Kantengewichte $\vec{d}(j)+A(k,j)$, sondern zusätzlich die für jeden Knoten definierte Abschätzfunktion $f(k)$ hinzuaddiert wird. Dies passiert jedoch nur bei der \emph{Auswahl} des Folgeknotens. Der Wert von $f(k)$ wird nicht im Eintrag $\vec{d}(k)$ gespeichert. Somit wird gewährleistet, dass der gefundene Pfad, der Summe der Kantengewichte entspricht.
 
 \subsection{Floyd-Warshall-Algorithmus}
 Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt.