Ist A-Stern garantiert den kürzesten Weg in einem 2D-Gitter zu geben

Question

Ich arbeite mit A-Sterne-Algorithmus, wo ich ein 2D-Gitter und einige Hindernisse habe. Jetzt habe ich nur vertikale und horizontale Hindernisse, aber sie können dicht variieren.

Jetzt funktioniert der A-Stern gut (dh kürzeste Weg gefunden für die meisten Fälle), aber wenn ich versuche, von der oberen linken Ecke nach unten rechts zu erreichen, dann sehe ich manchmal, der Weg ist nicht kürzester, dh da ist etwas Ungeschicklichkeit im Pfad.

Der Pfad scheint von dem abzuweichen, was der kürzeste Pfad sein sollte.

Jetzt ist hier, was ich mit meinem Algorithmus mache. Ich beginne von der Quelle und bewege mich nach außen, während ich den Wert der Nachbarn für die Entfernung von Quelle + Entfernung vom Ziel berechne. Ich wähle weiterhin die minimale Zelle und wiederhole es, bis die Zelle, auf die ich stoße, das Ziel ist halt.

Meine Frage ist, warum ist A-Stern nicht garantiert, um mir den kürzesten Weg zu geben. Oder ist es? und ich mache etwas falsch?

Danke.

Answer 1

Der A-Stern liefert garantiert den kürzesten Pfad gemäß Ihrer metrischen Funktion (nicht unbedingt "wie der Vogel fliegt"), vorausgesetzt Ihre Heuristik ist "zulässig", dh sie überschreibt nie die verbleibende Entfernung.

prüfen Sie diesen Link: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Um bei der Bestimmung Ihrer Implementierungsfehler zu unterstützen, müssen wir Details sowohl auf dem metrischen und Ihre Heuristik.

aktualisieren:
OPs metric Funktion 10 für eine orthogonale Bewegung, und 14 für eine diagonale Bewegung.

Die Heuristik von OP berücksichtigt nur orthogonale Bewegungen und ist daher "unzulässig"; es überschätzt, indem es die billigeren diagonalen Bewegungen ignoriert.

Die einzigen Kosten für eine zu konservative Heuristik sind, dass zusätzliche Knoten besucht werden, bevor der minimale Pfad gefunden wird. Die Kosten einer zu aggressiven Heuristik sind ein nicht optimaler Pfad, der zurückgegeben werden kann. OP sollte eine Heuristik verwenden:

 7 * (deltaX + deltaY) 

, die auf die Möglichkeit eines direkten Weg diagonal eine sehr leichte Untertreibung ist, und so auch performant sein sollte.

Update # 2:
wirklich Leistung herauszupressen, ist dies auf eine optimale Nähe, während immer noch sehr schnell zu sein:

7 * min (deltaX, deltaY) + 10 * (max (deltaX, deltaY) - min (deltaX, deltaY))

Update # 3:
Die oben ist abgeleitet von 14/2, wobei 14 die Diagonalkosten in der Metrik ist.

Nur Ihre Heuristik ändert sich; Die Metrik ist "eine Geschäftsregel" und treibt den Rest an. Wenn Sie Interesse an der A-Sterne für einen hexagonalen Gitter sind, überprüfen Sie mein Projekt hier aus: http://hexgridutilities.codeplex.com/

Update # 4 (auf die Leistung):
Mein Eindruck von A-Star ist, dass es zwischen den Regionen von O taumelt (N^2) Leistung und Bereiche von fast O (N) Leistung. Aber dies ist so abhängig von dem Raster oder der Grafik, der Platzierung des Hindernisses und den Start- und Endpunkten, die schwer zu verallgemeinern sind. Für Gitter und Graphen bekannter spezieller Formen oder Geschmacksrichtungen gibt es eine Vielzahl von effizienteren Algorithmen, aber sie werden oft auch komplizierter; TANSTAAFL.

Answer 2

Ich bin sicher, dass Sie etwas falsch machen (Vielleicht ein Implementierungsfehler, Ihre Idee mit A * klingt korrekt). A * -Garantie gibt den kürzesten Weg, das lässt sich in Mathematik nachweisen.

Sehen Sie diese wiki pages Wille gibt Ihnen alle Informationen, um Ihr Problem zu lösen.

Answer 3

NO

A * eine der am schnellsten Pathfinder Algorithmen, sondern es den kürzesten Weg nicht unbedingt geben. Wenn Sie im Laufe der Zeit nach Korrektheit suchen, ist es am besten, den Algorithmus von Dijkstra zu verwenden.