DE 
EnglishStandard
Українська
Polski🧭 A*-Pfadsuche
Beobachten Sie, wie A* den kürzesten Pfad auf einem Gitter mit f(n)=g(n)+h(n) findet. Malen Sie Wände, ziehen Sie Start und Ziel, wechseln Sie die Heuristik und vergleichen Sie A*, Dijkstra und Greedy-Suche.
Über die A*-Pfadsuche
A* (gesprochen „A-Stern“) ist ein Best-First-Graphensuchalgorithmus, der den kürzesten Pfad zwischen zwei Punkten findet, indem er Dijkstras garantiert optimale bisherige Kosten (g) mit einer heuristischen Schätzung der verbleibenden Distanz (h) kombiniert und jedem Knoten einen Prioritätswert f = g + h zuweist. Entwickelt von Hart, Nilsson und Raphael 1968.
Diese Simulation lässt Sie zwischen A*, Dijkstra (h = 0) und Greedy Best-First (g = 0) auf einem Gitter wählen, auf dem Sie Wände und gewichtetes Gelände (Kosten ×5) malen, Start- und Zielknoten ziehen, eine Heuristik (Manhattan, Euklidisch oder Chebyshev) wählen, Diagonalbewegungen umschalten und die Knotenexpansion Schritt für Schritt beobachten können.
Häufig gestellte Fragen
Was bedeutet f = g + h?
Bei A* wird jeder Knoten in der offenen Menge mit f(n) = g(n) + h(n) bewertet, wobei g(n) die exakten Kosten des bisher gefundenen günstigsten Pfads vom Start zu Knoten n sind und h(n) die heuristische Schätzung der Kosten von n zum Ziel ist.
Was ist eine zulässige (admissible) Heuristik?
Eine Heuristik h ist zulässig, wenn sie die wahren Kosten zum Ziel niemals überschätzt — formal h(n) ≤ h*(n) für alle n. Die Manhattan-Distanz ist auf einem 4-verbundenen Gitter ohne Diagonalbewegung zulässig.
Wie unterscheidet sich A* von Dijkstras Algorithmus?
Dijkstras Algorithmus setzt h = 0, sodass er Knoten in der Reihenfolge ihrer exakten Kosten ab dem Start expandiert und sich gleichmäßig in alle Richtungen ausbreitet. A* addiert die Heuristik, um die Suche gezielt in Richtung Ziel zu lenken.
Was zeigen die Farben auf dem Gitter?
Grün markiert den Startknoten, Rot das Ziel. Blaue Zellen bilden die aktuelle Grenze (offene Menge), Dunkelblau markiert bereits besuchte (geschlossene) Knoten, und Gelb hebt den gerade expandierten Knoten hervor. Gewichtete Zellen erscheinen braun.