Der A* (A-Star)-Algorithmus ist ein heuristischer Suchalgorithmus, der in der Informatik verwendet wird, um den kürzesten Weg zwischen zwei Knoten in einem Diagramm zu finden. Es handelt sich um eine Erweiterung des Dijkstra-Algorithmus, der den kürzesten Weg findet, aber keine Heuristik verwendet.
Intuition
A* verwendet Heuristiken, also Informationen über die Problemdomäne, die bei der Suche helfen. Diese Heuristiken werden oft als zulässige Heuristiken oder Distanzheuristiken bezeichnet, da sie niemals die tatsächlichen Kosten für das Erreichen des Ziels überschätzen. In vielen Fällen findet A* optimale Lösungen, obwohl dies nicht immer garantiert ist.
Wie funktioniert A*?
A* verwaltet während seiner Suche zwei Knotensätze:OPEN (Fringe) und CLOSED
ÖFFNEN enthält alle Knoten, die generiert, aber noch nicht vollständig ausgewertet wurden. Sie ist nach der F-Punktzahl (siehe unten) ihrer Mitglieder geordnet, wobei die niedrigste F-Punktzahl an erster Stelle steht.
GESCHLOSSEN enthält alle Knoten, die vollständig ausgewertet wurden.
Der Algorithmus beginnt damit, dass der Startknoten auf OFFEN gesetzt wird, während sich der Zielknoten zunächst auf GESCHLOSSEN befindet. Bei jedem Schritt des Algorithmus entfernt A* den Knoten in OPEN mit dem niedrigsten F-Score, erweitert ihn und fügt alle seine Nachbarn zu OPEN hinzu. Wenn sich ein Nachbar nicht bereits in OFFEN oder GESCHLOSSEN befindet, berechnet A* für ihn einen G-Score (die tatsächlichen Kosten, um den Nachbarn vom Startknoten aus zu erreichen) und einen H-Score (eine Schätzung der Kosten, um das Ziel vom Nachbarn aus zu erreichen). und fügt es zu OPEN hinzu. Wenn sich ein Nachbar bereits im OPEN-Modus befindet, wird der neue G-Score mit dem aktuellen G-Score verglichen, und wenn der neue G-Score niedriger ist, wird der Nachbar aktualisiert. Befindet sich ein Nachbar bereits im Zustand GESCHLOSSEN, wird der neue G-Score mit dem aktuellen G-Score verglichen. Wenn der neue G-Score niedriger ist, wird der Nachbar von GESCHLOSSEN nach OFFEN verschoben und aktualisiert.
Kündigung
Der Algorithmus terminiert auf eine von zwei Arten. Wenn zunächst ein Nachbar des zu erweiternden Knotens das Ziel ist, gibt der Algorithmus den Pfad zum Ziel zurück. Zweitens:Wenn OPEN leer wird, wird der Algorithmus erfolglos beendet, was darauf hinweist, dass es keinen gültigen Pfad vom Startknoten zum Ziel gibt.
Komplexität
Die Zeitkomplexität des A*-Algorithmus im ungünstigsten Fall ist exponentiell in der Größe des Diagramms. In der Praxis schneidet A* jedoch bei vielen Problemen gut ab und findet oft in angemessener Zeit optimale Lösungen.
