A* Spinoff


  • 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?



  • @mgaeckler sagte in Problem mit Set:

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

    Ja bin ich. Begründungen kannst du nachlesen.



  • @TGGC sagte in Problem mit Set:

    @mgaeckler sagte in Problem mit Set:

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

    Ja bin ich. Begründungen kannst du nachlesen.

    Wo? Hier hab ich noch keine gefunden.



  • Dann kann ich dir leider nicht weiterhelfen.



  • @TGGC Das betrachte ich nicht als Verlust.


  • Mod

    @TGGC @Dravere etc. keine Ahnung was das hier werden soll, aber es sieht immer peinlich aus, wenn Computerwissenschaftler sich erfolglos darüber streiten, was irgendeine völlig vage Phrase wie 'erste gefundene Route' in einem Algorithmus bedeutet (sie ist vage—auch wenn ich spüre, wie TGGC bereits seinen Widerspruch aufschreibt, weil er ja unbedingt die Zweckmässigkeit seiner Tiraden verteidigen muss....). Es geht in einer Wissenschaft nicht um die Bedeutung von Begriffen, sondern um die Wahrheit von Aussagen. Die Aussage war hier einfach nicht sinnvoll artikuliert. Naechstes mal @TGGC produktivere Beitraege zur Diskussion liefern, bitte. Closed.


Anmelden zum Antworten