Ich brauche Hilfe bei meiner Implementierung des A * -Algorithmus. Wenn ich den Algorithmus ausführe, findet er das Ziel, aber der Pfad ist definitiv nicht der kürzeste :-P
Hier ist mein Code, bitte hilf mir die Fehler zu finden! Ich denke, es könnte der Rekonstruktionsweg sein, der mein Problem ist, aber ich bin mir nicht sicher.
%Vor%}
Danke an alle für die tollen Antworten! Mein A * -Algorithmus funktioniert jetzt perfekt dank euch! : -)
Dies war mein erster Beitrag und dieses Forum ist wirklich erstaunlich!
Sie ändern die Priorität eines Elements in PriorityQueue , nachdem Sie es eingefügt haben. Dies wird nicht unterstützt, da die Prioritätswarteschlange nicht erkennt, dass ein Objekt geändert wurde. Sie können das Objekt entfernen und erneut hinzufügen, wenn es sich ändert.
Die Priorität wird in der Zeile geändert: y.f_score = y.g_score + y.h_score; . Diese Zeile wird angezeigt, nachdem y zur Prioritätswarteschlange hinzugefügt wurde. Beachten Sie, dass das einfache Verschieben der Zeile openset.add(y); nach der Berechnung der Kosten nicht ausreicht, da y möglicherweise in einer vorherigen Iteration hinzugefügt wurde.
Es ist auch nicht klar aus Ihrem Code, ob die von Ihnen verwendete Heuristik zulässig ist. Wenn dies nicht der Fall ist, werden Sie auch suboptimale Pfade erhalten.
Abschließend noch ein Leistungshinweis: Die Methode contains für ArrayList und PriorityQueue benötigt eine lineare Ausführungszeit, wodurch die Laufzeit Ihrer Implementierung nicht optimal wird. Sie können dies verbessern, indem Sie den Knoten boolesche Eigenschaften hinzufügen, um anzuzeigen, ob sie sich in den geschlossenen / offenen Mengen befinden, oder indem Sie eine festgelegte Datenstruktur verwenden.
Die Prioritätswarteschlange aktualisiert die Position des Elements nicht, wenn Sie die Priorität ändern. Daher hält die Heap-Eigenschaft nicht. Die geänderte Priorität wirkt sich auf das Hinzufügen / Entfernen anderer Elemente aus, repariert jedoch die Heap-Eigenschaft nicht.
deshalb bekommst du nicht das beste Item von open - & gt; Du findest den kürzesten Weg nicht.
Sie können: 1) Schreiben Sie Ihren eigenen Heap und pflegen Sie den Index darin 2) füge ein weiteres Objekt in PQ hinzu und markiere das alte als ungültig (du musst anstelle eines Knotens ein Objekt mit einem Gültigkeits-Flag und einem referenzierenden Knoten in die Warteschlange setzen).
2) haben schlechtere Leistung und ich rate davon ab, aber einige Navigationssoftware verwendet diesen Ansatz (oder zumindest einige Jahre zurück verwendet).
edit: Best Practice ist, fügen Sie unveränderliche Objekte (oder zumindest mit einfügbaren Teilen, die Priorität bedeuten) in PriorityQueue
ein