A* Spinoff



  • @mgaeckler sagte in Problem mit Set:

    Wenn A* richtig implementiert ist, ist die erste gefundene Route auch die beste.

    Das ist falsch.


  • Administrator

    @TGGC sagte in Problem mit Set:

    @mgaeckler sagte in Problem mit Set:

    Wenn A* richtig implementiert ist, ist die erste gefundene Route auch die beste.

    Das ist falsch.

    Das musst du aber ein wenig expandieren, damit das Sinn ergibt. Je nach dem wie man "richtig implementiert" versteht und was genau man sucht, ist das schon richtig.



  • Da ist nichts zu hinzufügen. Es ist grundsätzlich falsch, in allen Varianten von Dijkstra und auch allen A* Unterarten davon. Der erste Weg ist ein upper bound für die Weglänge, man sortiert den in die Open List und findet so alle unfertigen Wege, die noch nicht länger sind und macht mit denen weiter.


  • Administrator

    @TGGC sagte in Problem mit Set:

    Da ist nichts zu hinzufügen. Es ist grundsätzlich falsch, in allen Varianten von Dijkstra und auch allen A* Unterarten davon. Der erste Weg ist ein upper bound für die Weglänge, man sortiert den in die Open List und findet so alle unfertigen Wege, die noch nicht länger sind und macht mit denen weiter.

    Gut ... kommt darauf an, wie man gefunden definiert. Wenn man es eng sehen will, hast du recht. Der Algorithmus ist erst abgeschlossen, wenn der nächste geholte Knoten aus der Open List dem Ziel entspricht. Sonst bricht man den Algorithmus vorzeitig ab.



  • Braucht man nichts definiern, das hat Dijkstra vor 60 Jahren schon. Zu jedem Zeitpunkt hat ein Knoten genau definiert einen von 3 Zuständen, es wurde noch gar kein Weg gefunden, es wurde ein Weg gefunden, dessen Optiomalität unbekannt ist oder es wurde bereits der optimale Weg gefunden. Diese Unterscheidungen sind auch wichtig. Ist der optimale Weg gefunden zu einem Knoten, darf dieser nicht mehr betrachtet werden, sonst terminiert der Algorithmus nicht. Und die unsicheren Weglängen werden benutzt um die Open List zu sortieren. So wird nicht irgendein Random Knoten wie in simpleren Algorithmen, sondern gezielt der aussichtsreichte angeschaut aber zusätzlich - noch wichtiger - beweist die Ordnung nach Weglänge, das es zum Knoten am Beginn der Openlist keinen besseren Weg mehr geben wird, wenn alle Kantengewichte positiv sind. Bei A* gilt diese Aussage nur wenn die Schätzfunktion an dem Knoten 0 ist, d.h. im Zielpunkt muss diese Funktion 0 liefern.

    D.h. die Aussage ist völliger Unsinn, sondern im Grunde müsste man sie genau umdrehen. Nicht wenn der erste Weg gefunden wurde, sondern erst wenn der letzte kürzere Weg gefunden wurde, terminiert der Algorithmus. Ohne Zielpunkt werden damit auch automatisch alle Knoten gefunden, zu denen es gar keinen Weg gibt, mit Zielpunkte alle Knoten, die näher als das Ziel liegen.

    Wäre die Aussage hingegen korrekt, müsste sie ohne Beschränkung dann auch für alle Knoten gelten, ich müsste also an keinem Knoten kürzere Wege suchen, sobald der erste Weg bekannt ist. Das ist offensichtlich Unsinn und wird in jedem hinreichend komplexen Graph falsche Ergebnisse liefern. Ein weiterer Punkt wäre, das der Algorithmus überhaupt nicht mehr terminieren kann, wenn der Zielpunkt unerreichbar ist. Man kann auch leicht einen Graph konstruieren, in dem diese Idee offensichtlich fehlschlägt. Man nehme A und B, die nicht benachbart aber über Weglänge k verbunden sein. Nun fügen man einen Knoten C in den Graph ein, sowie die Kanten BC mit Gewicht k sowie AB mit 0,5 * n, wobei n das minimale Kantengewicht zu A's Nachbarn sei. Suchen wir nun den Weg von A nach B, so wird im ersten Schritt C gefunden und mit 0,5*n nach vorn in dir Openlist kommen. Im zweiten Schritt wird B gefunden, damit ist der Weg A-B-C gefunden, der 0,5 * n + k lang ist. Da n ein positives Kantengewicht ist, ergibt sich ein Widerspruch.

    Das ist aber hier alles gar nicht das Thema und meiner Meinung auch recht trivial. Ich hoffe diese Ausführung reicht dir trotzdem.


  • Administrator

    @TGGC sagte in Problem mit Set:

    Das ist aber hier alles gar nicht das Thema und meiner Meinung auch recht trivial. Ich hoffe diese Ausführung reicht dir trotzdem.

    Für mich wäre sie nicht nötig gewesen. Ich wusste gestern Abend bereits, dass ich eigentlich hätte mehr schreiben sollen, aber war zu müde.

    Ich habe die Sache von ausserhalb des Algorithmus angeschaut. Ich dachte, dass du eigentlich darauf eingehen wolltest, dass die Heuristik nicht unbedingt die beste Route findet, je nach dem was man sucht. Also unter der ersten gefunden Route, hatte ich verstanden, was der Algorithmus zurück gibt, wenn er terminiert. Diese muss nicht die beste sein, da dies von der gewählten Heuristik abhängt.

    Das meinte ich auch damit, je nach dem wie man gefunden definiert. Also innerhalb oder ausserhalb des Algorithmus.

    Ich weiss nicht, was @mgaeckler hier genau gemeint hat.



  • Ok, du erzählst noch mehr Unsinn. Du tust so als geben Wegsuchen normalerweise eine Menge an random Wegen zurück. Als wären deren Ausgabe ein erster, zweiter, dritter Weg etc. Als ruft man sie normalerweise so lange auf bis man dann mal einen guten rausbekommt. Und netterweise bekommen wir hier den Hinweis, das wir dank dem Magic A* Algo hier uns einfach auf die erste gefundene Route verlassen können und die zweite, dritte etc. alle länger sind.

    Ausserdem sollten wir dann wohl auch die restliche Erklärung komplett ignorieren, wo es darum geht wann und wie die internen Daten sich verändern oder offensichtlich über den unfertigen Pfad geredet würden, der zu erweitern und ändern wäre. Und wenn im Satz vor meinen zitierten dann von einer Route geredet wird, ist dies sicher eine ganz andere Route als im nächsten Satz.

    Wenn du keinen Bock hast hier ordentlich mitzulesen und dich reinzudenken und schon von Anfang an die Posts nicht komplett verstehen wilst, warum kommst du dann in den Thread rein und forderst von den Diskutanten das sie irgendeinen Punkt genauer ausführen? Für dich ist die Erklärung nicht nötig, also unterstellst den restlichen Mitlesern, das sie die Erklärung nötig haben und zu dumm sind mich aus dem Context zu verstehen?


  • Administrator

    @TGGC sagte in Problem mit Set:

    Ok, du erzählst noch mehr Unsinn. Du tust so als geben Wegsuchen normalerweise eine Menge an random Wegen zurück. Als wären deren Ausgabe ein erster, zweiter, dritter Weg etc. Als ruft man sie normalerweise so lange auf bis man dann mal einen guten rausbekommt. Und netterweise bekommen wir hier den Hinweis, das wir dank dem Magic A* Algo hier uns einfach auf die erste gefundene Route verlassen können und die zweite, dritte etc. alle länger sind.

    Nein, das tue ich nicht im Ansatz.

    In der Praxis gibt es Fälle, wo du den Algorithmus mehrmals mit unterschiedlichen Heuristiken aufrufst. Zum Beispiel weil es keine beste Heuristik gibt oder die beste Heuristik aus Performance-Gründen viel zu aufwendig wäre. Dadurch hast du am Ende mehrere gefundene Routen. Jedes Mal hat es aber natürlich nur eine gefunden, nämlich die beste für die gegebene Heuristik.

    Ausserdem sollten wir dann wohl auch die restliche Erklärung komplett ignorieren, wo es darum geht wann und wie die internen Daten sich verändern oder offensichtlich über den unfertigen Pfad geredet würden, der zu erweitern und ändern wäre. Und wenn im Satz vor meinen zitierten dann von einer Route geredet wird, ist dies sicher eine ganz andere Route als im nächsten Satz.

    Was? Nein? Wieso? Wie kommst du auf diese seltsame Idee? Nicht im Ansatz habe ich irgendetwas in die Richtung behauptet. Du interpretierst viel zu viel in meine Antworten rein.

    Wenn du keinen Bock hast hier ordentlich mitzulesen und dich reinzudenken und schon von Anfang an die Posts nicht komplett verstehen wilst, warum kommst du dann in den Thread rein und forderst von den Diskutanten das sie irgendeinen Punkt genauer ausführen? Für dich ist die Erklärung nicht nötig, also unterstellst den restlichen Mitlesern, das sie die Erklärung nötig haben und zu dumm sind mich aus dem Context zu verstehen?

    Sorry, aber mal ehrlich. Das behaupte ich nicht im Ansatz. Du interpretierst so viel ... unglaublich viel ... jenseits von zu viel in meine Antworten rein. Ich verstehe nicht, wieso du dermassen beleidigt bist. Du willst unbedingt nicht verstehen, dass ich aus dem falschen Kontext deine Antwort angeschaut habe? Als du den Kontext erklärt hast, habe ich verstanden, was du gemeint hast und dir zugestimmt. Also nur noch damit es klipp und klar ist, ich bin einverstanden mit dem was du gesagt hast.

    Abgesehen davon ist es immer sinnvoll Punkte genauer zu erklären, als einfach nur kurze Sätze/Aussagen hinzuschreiben. Auch wenn deine Aussage im Kontext absolut richtig war, war die zusätzliche Erklärung danach eine riesige Bereicherung zu deiner kurzen Aussage. Sie hat mir nicht geholfen, weil ich den A* Algorithmus schon zigfach eingesetzt und selber implementiert habe. Aber für jemand neues in dem Bereich ist das definitiv ein sehr wertvoller Beitrag.


  • Mod

    @TGGC Kannst Du mal runterkommen? Deine Aussage war formal betrachtet korrekt, aber überhaupt nur fuer jemanden in ihrem intendierten Sinngehalt nachvollziehbar, wenn diese Person sich detailreich an Dijkstra erinnern kann.
    Sonst ist die sehr naheliegende Interpretation die, dass A* nicht den optimalen Weg ergebe, was pauschal einfach nicht stimmt. Da brauchst Du auch nicht überrascht zu tun wenn Dravere das entsprechend aufzeigt. Und schon gar nicht ausfallend werden.



  • @Dravere Richtig implementiert heißt:

    • Die Heuristic muß einen vernünftigen Wert liefern, beim Routing auf einer Straßenkarte kann das z.B. die Luftlinie sein + die bekannte Länge der bisherigen Route.
    • Der geschätzte Wert darf niemals schlechter sein wie der tatsächliche Wert.
    • Die erste gefundene Route heißt, wenn der gewünschte Zielknoten am Anfang der PriorityQueue steht. Es heißt nicht, wenn der gewünschte Zielknoten vom aktuellen Knoten direkt erreichbar ist.

    Hoffe jetzt sind alle Klarheiten beseitigt.

    VG Martin



  • @mgaeckler sagte in Problem mit Set:

    Der geschätzte Wert darf niemals schlechter sein wie der tatsächliche Wert

    *als



  • @LeMace sagte in Problem mit Set:

    @mgaeckler sagte in Problem mit Set:

    Der geschätzte Wert darf niemals schlechter sein wie der tatsächliche Wert

    *als

    Der durchschnittlich gebildete Preiß sollte meinen Satz auch ohne Deine Übersetzung lesen können.



  • @mgaeckler sagte in Problem mit Set:

    Die erste gefundene Route heißt, wenn der gewünschte Zielknoten am Anfang der PriorityQueue steht

    Das ist falsch.



  • @TGGC: Was soll daran falsch sein?


  • Administrator

    @Th69 sagte in Problem mit Set:

    @TGGC: Was soll daran falsch sein?

    Ich kann nur mutmassen bei einer so kurzen Aussage.

    Aber rein von der Theorie geschaut, wenn der Algorithmus läuft, ist es möglich, dass der Zielknoten am Anfang in der Priority Queue eingefügt wird und dies noch nicht, die beste Route darstellt. Erst wenn alle Nachbarn abgearbeitet worden sind und der nächste Knoten aus der Priority Queue entnommen wird und dieser dem Zielknoten entspricht, dann haben wir die beste Route gemäss der Heuristik gefunden. Es ist somit wichtig, den Zeitpunkt zu betrachten, wann der Zielknoten im Verlauf des Algorithmus am Anfang der Priority Queue steht. Nur weil irgendwann einmal der Zielknoten am Anfang steht reicht noch nicht.

    Es ist etwas pingelig.



  • Wie bereits gesagt: Der Knoten wird anhand seiner Route in die Priority Queue sortiert. Wie soll also ein Knoten, zu dem noch keine Route bekannt ist, dort am Anfang stehen? Knoten mit unbekannter Route, stehen wenn überhaupt hinten mit inf Entfernung.



  • Du scheinst etwas anderes in den Satz hineininterpetiert zu haben, das da gar nicht steht.

    Der A*-Algorithmus terminiert, sobald der Knoten mit dem geringsten Kostenwert (f) der Zielknoten ist (also am Anfang der PriorityQueue steht):

    // Knoten mit dem geringsten f-Wert aus der Open List entfernen
    currentNode := openlist.removeMin()
    // Wurde das Ziel gefunden?
    if currentNode == zielknoten then
        return PathFound
    

    Und dies ist dann die "erste gefundene Route" (Rückwärts vom Zielknoten aus die Vorgängerknoten bis zum Startknoten verfolgen bzw. um umgekehrt den Hinweg zu haben, vertauscht man Start- und Zielknoten bei der Suche)...



  • @Th69 sagte in Problem mit Set:

    Und dies ist dann die "erste gefundene Route"

    Falsch.



  • @TGGC Bist Du Dir sicher, daß Du den A*-Algorithmus verstanden hast?



  • @TGGC sagte in Problem mit Set:

    @Th69 sagte in Problem mit Set:

    Und dies ist dann die "erste gefundene Route"

    Falsch.

    Hast Du auch eine Begründung?


Log in to reply