A*-Suche

g(n) bezeichnet die bereits angefallenen Kosten vom Start bis zum Knoten n. h(n) schätzt die noch nötigen Kosten bis zum Ziel. A* addiert beides zu f(n) und priorisiert kleine Werte. g ist aus dem bekannten Weg berechnet, h dagegen eine Prognose. Beide Größen müssen dieselbe Kostenart und Einheit verwenden, etwa Sekunden oder Meter. Eine Distanzschätzung darf nicht ungeprüft mit Fahrzeit addiert werden, selbst wenn beide für dieselbe Route relevant erscheinen. In einer Implementierung sollte außerdem klar sein, ob die Knoten- oder Kantengewichte addiert werden und wie Gleichstände in der offenen Menge behandelt werden.

Eine Heuristik ist zulässig, wenn sie die tatsächlichen minimalen Restkosten an keinem Knoten überschätzt und am Ziel null ist. Auf einem Raster mit vier Richtungen und Schrittpreis eins ist die Manhattan-Distanz zulässig: Jede horizontale oder vertikale Abweichung erfordert mindestens genau so viele Züge. Gibt es diagonale Bewegungen oder billigere Sonderkanten, gilt dieser Beweis nicht automatisch. Die Schätzung muss aus den tatsächlich erlaubten Bewegungen und Preisen hergeleitet werden. Ein guter Gegencheck besteht darin, für kleine Testgraphen die Heuristikwerte mit exakt berechneten Restwegen zu vergleichen.

Konsistenz verlangt für jede Kante u→v die Ungleichung h(u)≤c(u,v)+h(v). Sie ähnelt der Dreiecksungleichung: Eine Schätzung am Anfang der Kante darf nicht höher sein als Kantenpreis plus Schätzung am Ende. Dadurch steigen die f-Werte entlang eines Weges nicht. Bei üblicher Graphsuche muss ein bereits geschlossener Knoten dann nicht erneut geöffnet werden. Ist h nur zulässig, kann A* trotzdem optimal sein, wenn die Implementierung verbesserte Wege korrekt wieder aufnimmt. Bei inkonsistenten Schätzungen muss eine bessere Distanz zu einem bereits besuchten Knoten die Suche gegebenenfalls erneut öffnen.

Setzt man h(n)=0, wird die Priorität f(n)=g(n). A* wählt dann den offenen Knoten mit den kleinsten bekannten Startkosten; bei nichtnegativen Kanten ist das Dijkstra. Die optimale Antwort bleibt erhalten, aber die Suche verliert ihre Richtung zum Ziel und kann mehr Knoten untersuchen. Der Nullheuristik-Fall ist deshalb eine gute Korrektheitsreferenz: Eine kompliziertere Heuristik sollte Wege nicht verfälschen und idealerweise weniger Sucharbeit verursachen. So lässt sich der Suchaufwand mit der Dijkstra-Baseline vergleichen, ohne die optimale Lösung als Qualitätsmaß zu verlieren. Die Auswahl des nächsten Knotens hängt daher sowohl von den Pfadkosten als auch von der Güte der Schätzung ab.

Vom Rasterstart (0,0) zum Ziel (3,2) sind mindestens fünf Einzelschritte nötig. Beim Zwischenknoten (1,1) wurden zwei Schritte bezahlt, also g=2. Es bleiben zwei horizontale und ein vertikaler Schritt, daher h=3 und f=5. Ohne Hindernisse erreicht die Schätzung die tatsächlichen Restkosten. Hindernisse können einen Umweg erzwingen und den echten Preis erhöhen, aber keine zulässige Manhattan-Schätzung unterbieten. So prüft man zugleich Koordinaten, bisherige Kosten und Restweg. Das Verfahren bewertet hier Anzahl der Schritte; bei unterschiedlichen Wegkosten müssen auch die bisher bezahlten Kosten gewichtet summiert werden.