- Aktuell
- In der Warteschlange
- Endgültig
- Weg
- Luftlinien-Schätzung
A*-Suche
Die A*-Suche findet einen kürzesten Weg von einem Start zu einem Ziel, wie der Dijkstra-Algorithmus, weiß aber ungefähr, wo das Ziel liegt. Jeder Knoten bekommt eine Schätzung des noch verbleibenden Abstands, die Luftlinie zum Ziel, und die Suche macht immer bei dem Knoten mit dem kleinsten bisherigen Abstand plus Schätzung weiter. Klicken Sie auf einen Knoten, um dort zu starten, wählen Sie ein Ziel und gehen Sie Schritt für Schritt vor: Die Suche steuert auf das Ziel zu und lässt ganze Ecken des Graphen unberührt. Drücken Sie Abspielen, um der Suche zuzusehen, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Klicken Sie auf einen Knoten, um ihn zum Start zu machen; stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten, um ihn zum Ziel zu machen. Die Zahl auf jeder Kante ist ihre Länge, die Zahl auf jedem Knoten sein bisheriger Abstand, und die gestrichelte Linie die Luftlinien-Schätzung des noch verbleibenden Abstands. Die Reihe unter dem Graphen ist die Warteschlange, die niedrigste Bewertung zuerst, jeweils mit ihrer Bewertung: bisheriger Abstand plus Schätzung. Neuer Graph erzeugt einen anderen Graphen; wählen Sie, wie viele Knoten und Kanten er hat. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Klicken Sie auf einen Knoten, um ihn zum Start zu machen. Stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten, um ihn zum Ziel zu machen.
- Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück schrittweise vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
- Beobachten Sie die Bewertungen in der Warteschlange und die gestrichelte Luftlinien-Schätzung. Vergleichen Sie am Ende, wie viele Knoten A* gebraucht hat und wie viele der Dijkstra-Algorithmus.
So funktioniert die A*-Suche
Der Start bekommt Abstand 0 und kommt in eine Warteschlange. Jeder Knoten in der Warteschlange hat eine Bewertung: seinen bisherigen Abstand plus eine Schätzung des noch verbleibenden Abstands. Wiederholen Sie: Nehmen Sie den Knoten mit der niedrigsten Bewertung und markieren Sie seinen Abstand als endgültig. Ist es das Ziel, hören Sie auf. Sonst addieren Sie für jeden Nachbarn, der nicht endgültig ist, die Länge der Kante zum Abstand des Knotens; ist das kürzer als der bisherige Abstand des Nachbarn, senken Sie ihn, merken Sie sich den Knoten als Weg dorthin und legen Sie den Nachbarn mit seiner neuen Bewertung in die Warteschlange.
Warum die Schätzung nie zu lang sein darf
A* findet einen kürzesten Weg, solange die Schätzung das Ziel nie weiter entfernt angibt, als es wirklich ist: eine zulässige Schätzung. Die Luftlinie ist eine, denn keine Straße zwischen zwei Orten ist kürzer als die Luftlinie. Eine zu lange Schätzung kann A* den besten Weg übersehen lassen; eine Schätzung von 0 überall macht A* zum Dijkstra-Algorithmus, der sicher ist, aber in alle Richtungen sucht. Je besser die Schätzung, desto weniger Knoten braucht A*. In der App ist jede Kante so lang, wie sie gezeichnet ist, aufgerundet, also ist die Luftlinie eine sichere Schätzung.
Häufig gestellte Fragen
Was ist die A*-Suche?
Ein Algorithmus zur Wegfindung, der einen kürzesten Weg von einem Start zu einem Ziel findet. Er arbeitet wie der Dijkstra-Algorithmus, ordnet seine Warteschlange aber nach bisherigem Abstand plus einer Schätzung des noch verbleibenden Abstands. So steuert er auf das Ziel zu, statt sich in alle Richtungen auszubreiten.
Was ist eine zulässige Heuristik?
Eine Schätzung des Abstands zum Ziel, die nie länger ist als der echte kürzeste Abstand. Mit einer zulässigen Schätzung findet A* immer einen kürzesten Weg. Das klassische Beispiel ist die Luftlinie auf einer Karte.
Ist A* schneller als der Dijkstra-Algorithmus?
Meistens, wenn Sie den Weg zu einem Ziel brauchen und eine gute Schätzung haben: A* macht weniger Knoten endgültig, weil Knoten abseits des Ziels hohe Bewertungen bekommen. Mit einer Schätzung von 0 tut A* genau dasselbe wie der Dijkstra-Algorithmus. Der Dijkstra-Algorithmus ist die bessere Wahl, wenn Sie die Abstände zu allen Knoten brauchen.
Wo wird A* eingesetzt?
In Videospielen, um Figuren um Hindernisse herum zu bewegen, in Routenplanern, in der Bewegungsplanung von Robotern und in Puzzle-Lösern, etwa für das 15-Puzzle, wo die Schätzung zählt, wie weit die Steine von ihren Plätzen entfernt sind.
Wird mein Graph irgendwohin gesendet?
Nein. Der Graph wird in Ihrem Browser erzeugt und durchsucht, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor