A*-Algorithmus

[Network]

Hi,

ich möchte den A-Stern Algorithmus umsetzen (Wegfindung in disem Fall), jetzt habe ich schon so einige Texte darüber gelesen, verstehe die Umsetzung jedoch nicht.
Wie ich das bis jetzt mit dem Quelltext verstanden habe - und das ist widersprüchlich mit den zugehörigen Texten - werden einfach alle Punkte die möglich wären und gefunden werden, in eine Liste gepackt und hintereinander abgearbeitet.
Ich finde in den Quelltexten jedoch einfach nirgendwo die Heuristik. Wenn man jeden Punkt hintereinander abarbeitet, breitet sich das Suchmuster Ringförmig um den Anfangspunkt aus und nicht wie nach diesem Prinzip: http://de.Wikipedia.org/

Besonderst, wie setzt man diese überhaupt um? Gibt es eine Liste, die jeweils 2 Einträge wie eine HashMap besitzt und die Einträge nach ihrem Entfernung (Einer der Einträge) hin sortiert?

Vielen Dank und
Gruß
Network

 

[JohannisderKaeufer]

Die Heuristik ist das wichtigste an der ganzen Geschichte.

Wenn du tatsächlich eine Route auf einer Landkarte berechnen möchtest, dann wäre eine valide Heuristik die Luftlinie zu deinem Ziel. (Pythagoras: also sqrt(x² + y²) )

Der Wert einer Heuristik muß zwingend kleinergleich dem tatsächlichen Wert zum Ziel sein. Luftlinie ist z.B. immer kürze als der Weg über die Straße, wegen Kurven, Kreuzungen, etc.

Dadurch suchst du nun nicht Ringförmig, (außer deine Heuristik ist schlecht und gibt für jeden Punkt 0 an, was auch valide wäre)

Du sortierst nun deine Punkte nach

Tatsächliche Entfernung von Start zu Zwischenziel, plus Luftlinie Zwischenziel mit Ziel.

Bei jedem Zwischenziel suchst du neue Zwischenziele und fügst sie sortiert in deine Liste ein.
Nach diesem Schema:

Start -> ZZ1 -> ZZ2 -(Luftlinie)> Ziel

-> tatsächliche Strecke
-(Luftlinie)> heuristik

Bis die heuristik, die "überoptimistisch ist" Weggefallen ist

Start -> ZZ1 -> ZZ2 -> ZZ3 -> ZZ4 -> Ziel

Und schon hast du deinen Weg gefunden.

 

[Network]

Danke schonmal, genau so habe ich das auch kapiert.
Dann stellt sich nur die Frage nach der Umsetzung. Und genau hier waren meine Ansätze mit Beispielcode zu suchen fehlgeschlagen.

Was mir fehlt ist nähmlich, dass ich ja den nächstbesten Punkt untersuchen sollte. Dafür muss ich aber erstmal Wissen welcher der Nächstbeste ist.
Heißt das, ich soll die Liste jetzt jedesmal durchgehen und nach dem besten durchsuchen? Dadurch geht ja eig. sehr viel Arbeitsspeicherzeit und Berechnungszeit drauf.

Deshalb die Frage wie man genau das löst... In den Quelltexten in denen ich "gewühlt" habe, (und um ehrlich zu sein nicht sehr gründlich, weil ich bei der Suche jedesmal verzweifle) werden die Punkte einfach in die OpenList geworfen und eins nach dem anderen abgearbeitet werden ohne sie nach Nähe zu sortieren.

 

[Marco13]

Soweit ich mich erinnere verwendet man da üblicherweise eine PriorityQueue (Java Platform SE 6) die die Punkte (für den Benutzer "unsichtbar") nach ihrer Entfernung sortiert.

(Ich glaube, man muss da an einer Stelle aufpassen: Wenn sich die geschätzte Entfernung (bzw. allgemein der Wert, nach dem die Punkte in der Queue verglichen werden) ändert, wird natürlich NICHT automatisch die Queue aktualisiert. In diesem Fall muss man den Punkt rausnehmen, den Wert ändern, und den Punkt neu einfügen. Das ginge mit einem (Fibonacci)-Heap effizienter, weil der direkt Methoden bietet, um sich zu aktualisieren, aber so einen implementieren ist frickelig...)

 

[JohannisderKaeufer]

Die Effizienz bei diesem Algorithmus kommt von der Heuristik.
Für jeden Punkt muß nur einmal ein Heuristik-Wert berechnet werden, der sich prinzipiell nicht mehr verändern sollte.

Da die Liste sortiert/geordnet ist, kann da auch einfach einsortiert werden.

Durch das, daß sich der Algorithmus anhand der Luftline/Heuristik seinen Weg sucht, fallen viele unsinnige Berechnungen Weg. Dieser Effekt wiegt in der Regel am stärksten.

Siehe auch Complexität im Wiki Artikel.

 

[Network]

@Marco13
Vielen Dank, exakt was ich gesucht hatte.
Zum Glück wird hier Comparator unterstützt, denn mit Comparable konnte ich mir keine schöne mögliche A*-Quelltext-Lösung vorstellen.

&@Johannis
Dem schließe ich mir an. Es sollte sich nicht mehr verändern, und wenn es sich mittendrin verändert ist der gesammte Algorithmus nicht mehr zu gebrauchen.

Vielen Dank
Gruß
Net