Entfernung metrisch heuristische Informiert

Question

Manhattan Distanz Heuristik und eine Heuristik, die die

greater value of (square root(x1-x2),square root(y1-y2)) 

nimmt Wie würden Sie ihre Informiert betrachten und sie sind Zul den kürzesten Weg in einem Raster von a nach b in der Suche, wo nur horizontal und vertikale Bewegungen sind erlaubt?

Die zweite Heuristik nimmt in allen Fällen die diagonalen Wege und manchmal ist ihre Anzahl an erkannten Knoten wesentlich kleiner als Manhattan. Aber das ist nicht immer der Fall, und das verwirrt mich.

Answer 1

gegebenen aktuellen Punkt a = (x1, y1) und Ziel b = (x2, y2). Ich lasse dist1(a, b) die Manhattan-Entfernung angeben, und dist2(a, b) bezeichnen diese andere Heuristik, die Sie vorschlagen. Wir haben:

dist1(a, b) = |x1 - x2| + |y1 - y2|

dist2(a, b) = max(sqrt(|x1 - x2|), sqrt(|y1 - y2|))

Beachten Sie, dass ich Ihre neue vorgeschlagene Heuristik ein wenig verändert, die Quadratwurzel der absoluten Differenzen zu nehmen, statt nur Unterschiede, da die Quadratwurzel einer negativen Zahl würde zu Problemen führen. Wie auch immer, es sollte leicht zu sehen sein, dass für alle a und b, dist1(a, b) >= dist2(a, b).

Da beide Heuristiken zulässig sind im Falle eines Rasters mit nur vertikaler und horizontaler Bewegung, sollte dies typischerweise bedeuten, dass die größte Heuristik der beiden (die Manhattan-Distanz) effektiver ist, da sie näher beieinander liegt die Wahrheit.

Im OP haben Sie tatsächlich erwähnt, dass Sie die Anzahl der gefundenen Knoten messen und dass diese für die zweite Heuristik manchmal kleiner (besser) ist. Damit gehe ich davon aus, dass Sie meinen, dass Sie den A * -Algorithmus ausführen und dass Sie die Anzahl der Knoten messen, die aus der Grenz-/offenen Liste/Prioritätswarteschlange/welchem ​​Termin auch immer entfernt werden sollen benutzen.

Meine Vermutung ist, dass was passiert ist, dass Sie schlechte Tie-Breaking haben in Fällen, in denen mehrere Knoten eine gleiche Punktzahl in der Grenze (oft als f bezeichnet) haben. Die von Ihnen vorgeschlagene zweite Heuristik würde in der Tat dazu neigen, Knoten entlang der Diagonale zwischen dem aktuellen Knoten und dem Ziel zu bevorzugen, während die Manhattan-Distanz keine solche Tendenz aufweist. Ein guter Tie-Breaker, wenn mehrere Knoten in der Grenze einen gleichen Wert haben (f), wäre die Priorisierung von Knoten mit hohen realen Kosten (oft als g bezeichnet) und niedrigen heuristischen Kosten (oft als h bezeichnet)). Dies kann entweder in der Praxis implementiert werden, indem g oder h Scores explizit verglichen werden, wenn f Scores gleich sind, oder indem Sie einfach alle Ihre heuristischen Scores mit einer Zahl multiplizieren, die etwas größer ist als 1 (zum Beispiel 1.0000001). Weitere Informationen hierzu finden Sie unter http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties