Denkanstoss bei A-Stern Algorithmus..

[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