Ich arbeite mit einem A-Sterne-Algorithmus, wobei ich ein 2D-Gitter und einige Hindernisse habe. Jetzt habe ich nur vertikale und horizontale Hindernisse, aber sie können dicht variieren.
Nun funktioniert der A-Stern gut (dh der kürzeste Pfad wird für die meisten Fälle gefunden), aber wenn ich versuche, von oben links nach unten rechts zu gelangen, dann sehe ich manchmal, der Pfad ist nicht kürzest, dh dort ist etwas Ungeschicklichkeit im Pfad.
Der Pfad scheint von dem abzuweichen, was der kürzeste Pfad sein sollte.
Hier ist nun, 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 Stopp.
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.
A-Sterne liefern garantiert den kürzesten Pfad gemäß Ihrer metrischen Funktion (nicht unbedingt "wie der Vogel fliegt"), vorausgesetzt, Ihre Heuristik ist "zulässig", dh sie überschreibt niemals die verbleibende Entfernung.
Überprüfen Sie diesen Link: Ссылка
Um Sie bei der Bestimmung Ihres Implementierungsfehlers zu unterstützen, benötigen wir Details sowohl zu Ihrer Metrik als auch zu Ihrer Heuristik.
Aktualisieren :
Die metrische Funktion von OP ist 10 für eine orthogonale Bewegung und 14 für eine diagonale Bewegung.
OP Heuristik 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 von:
verwenden%Vor%
was die Möglichkeit eines direkten diagonalen Pfades sehr leicht unterschätzt und daher auch performant sein sollte.
Update # 2:
Um die Leistung wirklich zu drosseln, ist dies nahe an einem Optimum und trotzdem sehr schnell:
7 * min (deltaX, deltaY) + 10 * (max (deltaX, deltaY) - min (deltaX, deltaY))
Update # 3:
Das obige 7 ergibt sich aus 14/2, wobei 14 die Diagonalkosten in der Metrik sind.
Nur Ihre Heuristik ändert sich; Die Metrik ist "eine Geschäftsregel" und treibt den Rest an. Wenn Sie an A-Stern für ein hexagonales Gitter interessieren, überprüfen Sie mein Projekt hier: Ссылка
Update # 4 (auf Leistung):
Mein Eindruck von A-Stern ist, dass er zwischen Regionen mit O (N ^ 2) Performance und Bereichen mit fast O (N) Performance taumelt. 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 .
Ich bin mir 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 sich Wiki-Seiten an, in denen Sie alle Informationen finden, um Ihr Problem zu lösen.
Tags und Links algorithm a-star path-finding