Denkanstoss bei A-Stern Algorithmus..

[kai]

hallo zusammen,

ich habe eine, für mich , sehr gute beschreibung des A*-Algorithmus
gefunden, die folgender massen aussieht:

Generiere eine OPEN Liste
Generiere eine CLOSED Liste
Generiere einen Startknoten und nenne ihn STARTKNOTEN
Generiere einen Zielknoten und nenne ihn ZIELKNOTEN
Füge den Startknoten der OPEN Liste hinzu
Solange der Zielknoten nicht erreicht ist
    (
         Für jeden Knoten
             (
             Setze einen Zeiger auf den PARENT-Knoten
             Schätze H
             Berechne die Kosten nach der Formel K = Kb + H
             Wenn sich der gleiche Knoten bereits in der OPEN Liste befindet und seine Kosten K
             geringer oder gleich hoch sind, verwerfe den neuen Knoten
             Wenn sich der gleiche Knoten bereits in der CLOSED Liste befindet und seine Kosten
             K geringer oder gleich hoch sind, verwerfe den neuen Knoten.
             Andernfalls lösche alle gleichen Knoten aus der OPEN- und der CLOSED Liste.
             Füge den aktuellen Knoten der OPEN Liste hinzu
             )
    )

...........
mir ist eigentlich alles klar an diesem vorgang , nur eins
versteh ich einfach nicht ...
jeder knoten hat ja nacbarknoten die an irgend einem punk in die
OPEN liste aufgenommen werden müssen.. aber wann ?? und wieso
wird der knoten wenn er die geringsten kosten hat in die OPEN
liste eingefügt ?? .. für mein verständniss ist er da doch schon drin.
und müsste er nicht eher in die close liste ??

viele dank schonmal für denkanstösse ...
ich steh vermulich selber auf der leitung :-)

cu
kai

[Rouven]

Hello,

viele dank schonmal für denkanstösse ...
ich steh vermulich selber auf der leitung :-)

hmh, nur nicht aufgeben. Ich vermute es liegt vielleicht an einem Missverständnis bzgl. aktueller und "neuer" und "alter" Knoten.
OPEN = Knoten die noch nicht genauer untersucht wurden, u.U. aber einen guten Weg zum Ziel (gemäß der aktuellen Heuristik) versprechen.
CLOSED = Knoten deren Untersuchen bzgl. ihres Weges zum Ziel abgeschlossen sind. Der einzige Grund einen derartigen Knoten nochmal "anzufassen" wäre, wenn man nach seiner Erstbetrachtung einen besseren Weg ZU diesem Knoten findet.

Mit dem Wissen können wir uns jetzt an eine beliebige Entscheidungsstelle "mitten in der Suche" begeben. Wir schauen uns nun alle Knoten in der Liste OPEN an und - na ja, bei uns war es so gemacht - wählst den besten Kandidaten, also denjenigen der im Moment die geringsten Kosten für den Restweg hat. Dessen Nachbarn sind nun interessant.
Schritt (1): Wir packen den gewählten Knoten in CLOSED, weil er ja nun fertig analysiert ist (machen wir gerade).
Schritt (2): Wir schauen uns alle seine Nachbarn an, und nun kommt deine Liste der Kriterien zum Einsatz. Zunächst berechnen wir für den Nachbar x seine Reststrecke zum Ziel auf Basis der gewählten Heuristik. Nun stellt sich die Frage "lohnt es sich den Knoten in Zukunft weiter zu betrachten" - wi wollen ja einen intelligenten Algorithmus, der NICHT alle Wege nachschaut sondern nur die vielversprechenden. Vielversprechend ist er dann wenn
(1) er noch gar nicht in OPEN oder CLOSED ist (weil wir noch gar nichts über den Weg wissen)
ODER
(2) er zwar schon in CLOSED ist, der aktuelle Weg aber besser ist als der Weg auf dem wir ihn damals dort eingetragen haben
Beschließen wir, dass der Knoten relevant ist, kommt er also zur weiteren Analyse in die OPEN-Liste, andernfalls verwerfen wir ihn.

-> Durch den Schritt (2) werden alle Nachfolger des "aktuellen" Knotens bewertet und im Falle einer vielversprechenden Lösung in die OPEN-Liste übernommen.

Fazit: ich weiß nicht, ob ich's klar rübergebracht habe, frag mich sonst einfach nochmal...
w
MfG
Rouven