aboutsummaryrefslogtreecommitdiffstats
path: root/buch
diff options
context:
space:
mode:
authorPascal Schmid <81317360+paschost@users.noreply.github.com>2021-07-27 09:15:21 +0200
committerGitHub <noreply@github.com>2021-07-27 09:15:21 +0200
commitf102e60cf34adc068ccdc717b9c27d4179d208f8 (patch)
tree316950d495245ad24772c0ff5fa82a63da4415e2 /buch
parentTypo (diff)
downloadSeminarMatrizen-f102e60cf34adc068ccdc717b9c27d4179d208f8.tar.gz
SeminarMatrizen-f102e60cf34adc068ccdc717b9c27d4179d208f8.zip
Erläuterung zu A*
Diffstat (limited to '')
-rw-r--r--buch/papers/verkehr/section1.tex2
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.\\