"A Stern" Algorithmus

[robotxy]

Hi!
Ich brauche für meinen Roboter einen Algorithmus der den schnellsten Weg zwischen zwei Punkten findet. Ich habe ein bisschen gegoogelt und bin auf den "A Stern" Algorithmus gestoßen. Irgendwie habe ich keine verständlichen Erklärungen gefunden. Hat jemand von euch ihn schon einmal verwendet und könnte mir erklären wie er funzt?
MfG
Rasmus

[nestler]

Meiner Meinung nach ist das Ganze hier sehr gut erklärt:
http://de.wikipedia.org/wiki/A-Stern-Algorithmus

Da ich aber gerade sehe, dass du erst 14 bist, vermute ich mal, dass
dir mathematische Bäume und Graphen nicht allzu viel sagen.

Falls du also ein paar Begriffe nicht verstehst, frag einfach nochmal
nach...

[PicNick]

Hi, eine recht brauchbare erläuterung gibt's in Wikipedia
(Über Google suche "A STERN")
Ui, da wird der Robby aber stöhnen ! :-) mfg

[nestler]

da hatte wohl jemand die gleiche idee wie ich ;-)

[robotxy]

@Nestler
Genau du hast Recht, ich verstehe zwar das er die ganzen Felder nach ihrem Abstand zum Startpunkt über den schnellsten Weg bewertet, aber wie das ganze genau Aufgebaut ist, ist mir ein Geheimnis.
MfG
Rasmus

[PicNick]

Na ja, besser zweimal das gleiche als einmal nix :-) mfg

[nestler]

Also:

Die Vorraussetzungen vom Algorithmus sind die folgenden:

a) Es wird eine Liste A von "aktuellen Knoten" verwaltet.
b) Zu jedem Knoten wird sein Abstand von s auf dem kürzesten bisher
gefundenen Pfad gespeichert.
c) Soll außer der Länge des kürzesten Pfades auch der Pfad selbst
gefunden werden, wird bei jedem Knoten in Schritt 4. auch sein
Vorgänger gespeichert.

Das heisst wir legen eine Art Tabelle an für alle Knoten, und speichern
die Entfernung zu unserem Startpunkt s....

d) Nimm den Startknoten s in A auf
e) Für jeden Knoten aus A: Berechne die Summe aus seinem Abstand
von s und seiner Schätzfunktion und ermittle den Knoten vmin mit der
geringsten Summe
f) Wenn vmin = e dann wurde der kürzeste Weg gefunden
g) Ansonsten nimm die Nachfolger von vmin in A auf (vmin
wird "aufgelöst") und gehe zu 2. Ist einer der Nachfolger bereits in A
enthalten, nehme die Variante mit dem geringeren Abstand von s.

Wir starten also beim Knoten s. Dann schauen wir uns an, welcher der
Knoten aus A am günstigsten liegt (also: möglichst nah an s, und gleich-
zeitig möglichst nah an e). Dieser Knoten heisst vmin. Sind wir bei e,
dann sind wir fertig. Ansonsten machen wir das gleiche Spielchen noch-
mal mit dem Knoten vmin.

Der Algorithmus sucht also in jedem Schritt einen Knoten, der möglichst
weit Richtung Ziel geht, und dabei aber möglichst nahe am Start liegt.

- Ich hoffe, das Prinzip ist jetzt etwas klarer...

[robotxy]

Jedes Feld auf der Karte ist doch ein Knoten,oder?
Wir bewerten also am Anfang alle Punkte um S und suchen uns den aus, der am nächsten am Ziel ist(Luftlinie),das ist dann VMin,von diesem Wiederholen wir das ganze und suchen wir den Punkt der am nächsten an e ist. Wenn wir bei E sind müssen wir alles nur noch zurückverfolgen,oder habe ich einen Denkfehler gemacht?
MfG
Rasmus

[Felix G]

Das Thema gabs hier letztens schon...

Wenn man das weiss, und man benutzt die Suchfunktion kriegt man diesen link:
http://www.mds-5.de/temp/AStar.doc


Da wird das Verfahren ganz hervorragend erklärt, allerdings auf Englisch.