-         
+ Antworten
Ergebnis 1 bis 9 von 9

Thema: "A Stern" Algorithmus

  1. #1
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    13.03.2004
    Ort
    Bremen
    Alter
    26
    Beiträge
    308

    "A Stern" Algorithmus

    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

  2. #2
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    10.03.2004
    Ort
    München
    Alter
    33
    Beiträge
    286
    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...

  3. #3
    Super-Moderator Robotik Visionär Avatar von PicNick
    Registriert seit
    23.11.2004
    Ort
    Wien
    Beiträge
    6.835
    Hi, eine recht brauchbare erläuterung gibt's in Wikipedia
    (Über Google Suche "A STERN")
    Ui, da wird der Robby aber stöhnen ! mfg

  4. #4
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    10.03.2004
    Ort
    München
    Alter
    33
    Beiträge
    286
    da hatte wohl jemand die gleiche idee wie ich

  5. #5
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    13.03.2004
    Ort
    Bremen
    Alter
    26
    Beiträge
    308
    @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

  6. #6
    Super-Moderator Robotik Visionär Avatar von PicNick
    Registriert seit
    23.11.2004
    Ort
    Wien
    Beiträge
    6.835
    Na ja, besser zweimal das gleiche als einmal nix mfg

  7. #7
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    10.03.2004
    Ort
    München
    Alter
    33
    Beiträge
    286
    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...

  8. #8
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    13.03.2004
    Ort
    Bremen
    Alter
    26
    Beiträge
    308
    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

  9. #9
    Erfahrener Benutzer Robotik Einstein Avatar von Felix G
    Registriert seit
    29.06.2004
    Ort
    49°32'N 8°40'E
    Alter
    33
    Beiträge
    1.780
    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.
    So viele Treppen und so wenig Zeit!

+ Antworten

Berechtigungen

  • Neue Themen erstellen: Ja
  • Themen beantworten: Ja
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •