diff options
Diffstat (limited to 'buch/papers/verkehr')
| -rw-r--r-- | buch/papers/verkehr/section1.tex | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 40c8edf..05c53c5 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -45,7 +45,7 @@ Der A*-Algorithmus geht auf seine Erfinder Peter Hart, Nils Nilsson und Bertram 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 wird als Verallgemeinerung gehandhabt und gilt als Erweiterung des Dijkstra-Algorithmus. +Der A*-Algorithmus gilt als Erweiterung des Dijkstra-Algorithmus. \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 die optimalste Lösung darstellt.\\ |