Literatur zum A*-Algorithmus

Der A*-Algorithmus

Sie kennen bereits einige Methoden zur Suche von kürzesten Wegen im Graphen, z.B. den Dijkstra-Algorithmus oder Greedy. Ist die Suchumgebung ein zweidimensionales Feld, haben beide Algorithmen Nachteile: Dijkstra durchsucht die Umgebung des Startpunkts unterschiedslos in jede Richtung und findet dabei optimale Wege zu allen Knoten in diesem Umfeld - wir suchen aber nur den Weg zu einem einzelnen Punkt, könnten daher mit deutlich weniger Rechenzeit auskommen. Greedy verwendet eine Heuristik und sucht vom Startpunkt aus geradewegs in Richtung des Ziels, lässt sich aber von Hindernissen verwirren und findet dann suboptimale Wege.

Der A*-Algorithmus (sprich: A-Stern) kombiniert die Vorteile beider Methoden, indem er sowohl die Länge des bereits zurück gelegten Weges betrachtet, als auch eine Greedy-ähnliche Heuristik verwendet. A* findet immer den kürzesten Weg und das bei guter Wahl der Heuristik auch in optimaler Rechenzeit. Der Algorithmus wird daher in der Regel bei der Entwicklung von Computerspielen verwendet.

Literatur zu A*

A* wurde bereits sehr oft - und sehr gut - beschrieben. Wir haben uns daher das Verfassen eines eigenes Tutorials gespart und verweisen hier auf einige im Internet verfügbare Beschreibungen. Wenn Sie mögen, basteln Sie sich ein provisorisches Spielfeld aus einem zweidimensionalen char-Array und testen Ihre eigene Heuristik.

Falls Sie selbst gute Quellen zum Thema kennen, setzen Sie uns bitte mit einer kurzen Beschreibung davon in Kenntnis. Wir verlinken die Quelle dann hier.

Fragen zum Thema beantwortet Ihnen Oliver Ullrich.