A * Manhattan Entfernung

Question

Ich suchte nach dem Algorithmus/Pseudocode von A * Ich folgte ihm und kodierte es. Ich benutzte Manhattan Entfernung für h (n). (F (n) = g (n) + h (n)) Und das ist das Ergebnis,

Dies immer passieren, wenn es keine Wände, die die Art und Weise zu blockieren, aber wenn ich eine Menge setzen von Wänden scheint es, dass es den kürzesten Weg nimmt. Ist das der kürzeste Weg? Ich meine, warum ist es nicht so unten?

Dies ist auch A * Manhattan, und sie haben die gleiche Größe (19x19). Dies ist von http://qiao.github.com/PathFinding.js/visual/

Answer 1

Beide Pfade haben den gleichen Manhattan-Abstand. Daher ist es implementierungsabhängig, welcher Pfad gewählt wird. Um zu erklären, warum dieser spezifische Teil ausgewählt wurde, müssten wir uns den Code dieser spezifischen A * Implementierung ansehen.

Hinweis: Jeder Pfad von einer Quelle zu einer Zielzelle, die nur Von Neumann neighborhood verwendet (dh nicht diagonal geht) und keinen Schritt in die "falsche" Richtung macht (dh in Ihrem Beispiel nie nach oben oder links geht)) hat die gleiche Manhattan-Entfernung. Also, wenn Sie in New York sind, ist es egal, welche Kreuzung Sie nehmen, um einen bestimmten Platz in Manhattan zu erreichen :)

Answer 2

Mit der Manhattan-Entfernung ist die erste ein kürzester Weg. Es zählt einfach die Anzahl der horizontalen und vertikalen Schritte. Wenn Sie etwas suchen, das eher wie ein kürzester Weg in der euklidischen Entfernung aussieht, können Sie versuchen, Ihren Algorithmus so zu ändern, dass bei horizontaler oder vertikaler Verschiebung an einer Stelle die horizontale ausgewählt wird, wenn die horizontale Entfernung größer ist als die vertikale eins und umgekehrt.

Answer 3

Sie müssen eine Sichtlinie (pythagoreisch/euklidisch) vom Startpunkt bis zu jedem Punkt (des manhattan/A * Ergebnisses) bis zum Ende werfen. Wenn eine Linie zu einem bestimmten Punkt durch das Hindernis blockiert/verdeckt wird, verwendest du den zuvor gegossenen Punkt und beginnst, eine weitere Linie von diesem blockierten Punkt aus zu werfen und dann weiter bis zum Ende. Ein blockierter Punkt ist, wenn ein Punkt durch die Sichtlinie des Anfangspunkts des Segments/der Linie verdeckt wird. So wie es ist:

Erste Zeile: Start ---------> S + N (vor blockierten Punkt)

Zweite/Middle Line/s: Blockierte Punkt ------ ----> S + N (vor einem anderen blockierten Punkt) wiederhole es erneut (neue Linie/Segment), bis eine Sichtlinie zum Ziel hergestellt ist.

Letzte Zeile: Blockierte Punkt -------------> Ziel

Schließen Sie alle Linien und Sie haben einen viel kürzeren kürzesten Weg bekommen. Sie können erneut ausführen, aber umgekehrt, um eine weitere Genauigkeit hinzuzufügen, sodass die Sichtlinie vom Ziel bis zum Start beginnt.