Kann mir jemand den A*-Algorithmus erklären?
Danke.

Aye.
Also in P3 wird der gar nicht so genau durchgenommen.
Ich weiß nur das der A* Algorithmus nicht nur die kürzeste Strecke berechnet, sondern auch die schnellste in Abhängigkeit von anderen Faktoren.

Du hast eine Schätzfunktion h die für jeden Knoten (unter-)schätzt, wie weit es noch zum Ziel ist. Eine Möglichkeit wäre zum beispiel den Abstand über Luftlinie zu berechnen.
Gut. Man fängt ja bei einem Startknoten an und kennt dessen Nachbarn. Der bisherige Weg g ist 0 = g(Startknoten). Dann sucht man sich den Knoten raus, wo h am kleinsten ist und guckt sich dessen Nachbarn an. Allerdings braucht man ja eine gewissen Distanz zu dem neuen Knoten, die dann in g(neuer_Knoten) festgehalten wird. Um zu entscheiden, welchen der alten oder neuen Nachbarn man als nächstes überprüft, wird der Nachbar mit dem kleinsten (g+h) gewählt. Das heißt wenn der erste Schritt nicht gut war (dann ist g groß), dann werden auch zuerst die anderen alten Nachbarn überprüft.

naja, so funktioniert der und dann kann man schön beweisen, warum der Alg. immer den kürzesten Weg findet und sowas alles :)

http://3773.rapidforum.com/topic=101785183880