Ein Sternalgorithmus ohne diagonale Bewegung
Situation: Ich versuche, den A * -Algorithmus in C ++ - Code zu übersetzen, wo keine diagonale Bewegung erlaubt ist, aber ich habe seltsames Verhalten.
Meine Frage : Ist es notwendig, auch die diagonalen Kosten zu berücksichtigen, auch wenn keine diagonale Bewegung möglich ist. Wenn ich die Berechnungen ohne Diagonalkosten mache (mit einem "heuristischen" Faktor 10), habe ich immer den gleichen fscore von 80 (das kann man im zweiten Bild sehen, wo ich fscore, gscore und hscore berechnet) und das scheint wirklich seltsam zu sein mich. Aus diesem Grund (fast alle Knoten haben einen fscore von 80) scheint das Algorimth nicht zu funktionieren, weil zu viele Knoten den gleichen kleinsten fscore von 80 haben.
Oder ist das normales Verhalten und wird eine A * Stern-Implementierung ohne Diagonale viel mehr Arbeit leisten müssen (weil mehr Knoten den gleichen minimalen fscore haben)?.
Ich glaube nicht, dass diese Frage etwas mit meinem Code zu tun hat, sondern mit meiner Argumentation, aber ich poste sie trotzdem:
pathFind.cpp
%Vor%node.cpp
%Vor%3 Antworten
Ich denke, Ihr Algorithmus hat kein Problem, und wenn keine diagonalen Bewegungen verfügbar sind, ist es nicht notwendig, dies zu berücksichtigen. Die Manhattan-Distanz ist eine einfache Heuristik, und wenn Sie näher am Zielknoten sind, gibt die H-Funktion kleinere Zahlen, obwohl die G-Funktion (Entfernung vom ersten Knoten bis hier) größer wird. Als Ergebnis haben viele Knoten den gleichen f-Wert.
A * ist vollständig generisch - der Graph, den Sie ihm geben, kann eine beliebige Form haben. Es interessiert nur, ob Sie von X nach Y gehen können, nicht warum. Wenn diagonale Bewegung nicht erlaubt ist, ist es egal. Und es ist ziemlich gut und legitim für viele Knoten, die gleiche f Punktzahl zu haben - es wird tatsächlich erwartet.
Ich denke, es ist egal, wie viele Quadrate die gleiche f-Punktzahl haben. Wie im Hauptalgorithmus von A * gesagt, "Für die Zwecke der Geschwindigkeit kann es schneller sein, die letzte zu wählen, die Sie der offenen Liste hinzugefügt haben". Ich hoffe, es wäre kein Problem, wenn Sie keine diagonalen Kosten in Betracht ziehen. Es scheint interessant, wie es Ergebnisse liefert.
Ich hoffe, Sie haben diesen Artikel bereits gelesen. Wenn nicht, schau es dir klar an.
Tags und Links c++ a-star path-finding