Ist der Manhattan-Abstand monoton, wenn er als heuristische Funktion verwendet wird?

25

Ich habe eine quadratische Karte. Es sind nur horizontale und vertikale Bewegungen zulässig (keine Diagonalen). Die Bewegungskosten betragen immer 1.

Ich implementiere einen A * -Algorithmus auf dieser Karte und verwende die Manhattan-Entfernung als Entfernungsheuristik. Ist diese Heuristik konsistent? Kann ich vermeiden, g(node)nach Knoten zu suchen, die sich im CLOSED-Satz befinden?

Edit: Mit konsequent meine ich monoton.

tiles path-finding geometry Emiliano
quelle
1
Wenn Ihre Bewegungskosten für jedes Plättchen gleich sind, können Sie A * durch Jump Point Search
Nick Caplinger,
Hey, das ist schön!
Emiliano

Antworten:

10

Um Ihre Frage tatsächlich zu beantworten: Die Manhattenentfernung ist konsistent, wenn Sie sich nur vertikal / horizontal entlang eines ungewichteten Rasters bewegen müssen (dies kann durch die Definition auf Wikipedia leicht angezeigt werden) . Also ja, in Ihrem Fall können Sie die erneute Überprüfung von Knoten in der geschlossenen Menge vermeiden.

Wenn Sie jedoch eine diagonale Bewegung oder Bewegung in einem beliebigen Winkel zulassen, wird der Abstand zum Schüttgut unzulässig, da die Kosten für die Diagonale überschätzt werden. Dies bedeutet zwangsläufig, dass die Bewegung nicht konsistent ist.

BlueRaja - Danny Pflughoeft
quelle
Ja, das ist genau die Antwort, nach der ich gesucht habe. Es wäre schön zu wissen, was passiert, wenn die heuristische Funktion ist h(x) = min(manhattan(p1), manhattan(p2))(dh entweder p1 oder p2 sind gute Endpunkte und ich möchte den nächsten erreichen). Ist das h(x)noch monoton?
Emiliano
1
@happy_emi: Ja, wenn h(x, p1)und h(x, p2)sind konsistent, dann min(h(x,p1), h(x,p2))wird auch konsistent sein. Dies ist aus der Definition in Wikipedia leicht ersichtlich (wir müssten dies min(h(x, p1), h(x, p2)) <= distance(x,y) + min(h(y, p1), h(y, p2))für alle Knoten xund ymit einer Kante zwischen ihnen anzeigen. Nehmen wir nun an, dass dies h(x, p1)das Minimum ist. Können Sie <=anhand der Tatsache, dass dies definitiv die rechte Seite ist, nachweisen, dass dies der Fall ist?) Beide Heuristiken sind konsistent?)
BlueRaja - Danny Pflughoeft
31

Ja, der Manhattan-Abstand zwischen zwei Punkten ist immer der gleiche wie der normale Abstand zwischen ihnen. Sie können sich den Manhattan-Abstand als die X- und Y-Komponente einer Linie vorstellen, die zwischen den beiden Punkten verläuft.

Dieses Bild ( aus Wikipedia ) illustriert dies gut:

Manhattan Entfernungen

Die grüne Linie gibt die tatsächliche Entfernung an.

Die blauen , roten und gelben Linien repräsentieren alle die gleiche Manhattan-Entfernung (12 Einheiten). Unabhängig davon, welche Kombination von Bewegungen nach oben und rechts Sie vom linken unteren Punkt zum rechten unteren Punkt zeichnen, erhalten Sie dieselbe Gesamtentfernung von Manhattan.

MichaelHouse
quelle
2
Tolle Antwort: kurz, süß, auf den Punkt und mit einem schönen Bild.
Tom 'Blue' Piddock
1
Diese Antwort ist nah, aber falsch. Dieses Bild zeigt nicht, dass die Entfernung in Manhattan konsistent ist (wenn Sie die grüne Linie als die Entfernung betrachten, ist sie tatsächlich nicht konsistent!) Und die Begründung, dass er Knoten nicht erneut überprüfen muss, weil "die Entfernung in Manhattan zwischen zwei punkte sind immer gleich " trifft nicht zu (die aussage trifft auch zu h(x) = 1000, was offensichtlich nicht konsistent ist) . Er kann das erneute Überprüfen von Knoten vermeiden, aber nur, weil die Entfernung von Manhattan konsistent ist, was in dieser Antwort nicht angezeigt wird.
BlueRaja - Danny Pflughoeft
2
Ich glaube, durch die Definition, die Sie verknüpft haben, ist die Entfernung nach Manhattan konsistent. Die Entfernung der grünen Linie würde eine andere Heuristik verwenden. Die roten, blauen und gelben Linien zeigen, dass der Abstand zwischen den beiden Knoten gleich bleibt (wenn dieselbe Heuristik verwendet wird). Wenn Sie näher heranrücken, wird die Heuristik verringert, und wenn Sie sich weiter wegbewegen, wird die Heuristik erhöht. Dies erfüllt die monotonen Anforderungen des OP. Während der Erstellung des Graphen mit einem Knoten an jeder "Kreuzung" ist der Manhattan-Abstand konsistent. Wenn es ein anderes Szenario wäre (wie das Ermöglichen einer diagonalen Bewegung), wäre die Heuristik schlecht.
MichaelHouse
2
Ich habe bereits gesagt, dass Manhatten Distance konsistent ist, aber nicht aus den von Ihnen genannten Gründen. Ihre Antwort zeigt weder Konsistenz noch Ihre Argumentation in den Kommentaren. "Konsistente / monotone Heuristik" hat eine genaue Definition (in meinem obigen Link angegeben) , die nicht mit einer monotonen Funktion identisch ist, für die Sie sie zu verwirren scheinen. Die Angabe "Annäherung verringert die Heuristik und Weiterentfernung erhöht die Heuristik" reicht nicht aus, um zu zeigen, dass sie konsistent ist, z. 2*manhattenbefriedigt das, ist aber nicht konsequent.
BlueRaja - Danny Pflughoeft
3
Ich weiß nicht, warum Sie sagen, dass es falsch ist. Sie scheinen darauf zu bestehen, dass diese Antwort unvollständig ist . Der Beweis in Ihrer Antwort scheint ebenso schwach zu sein: "Der Manhattenabstand ist konsistent ...". Anschließend wiederholen Sie die ursprünglichen Spezifikationen der Frage und stellen fest, wie unzulässig es wäre, wenn das Szenario anders wäre . Ich hatte nicht das Gefühl, dass die Antwort einen vollständigen mathematischen Beweis erforderte. Wenn Sie der Meinung sind, dass diese Frage dies erfordert, fügen Sie sie bitte Ihrer Antwort bei, und ich werde darüber abstimmen. Danke für die konstruktive Kritik.
MichaelHouse
6

In Erweiterung der Antwort von Byte56 möchte ich darauf hinweisen, dass in Ihrem spezifischen Datensatz die Verwendung der Manhattan-Distanz als heuristische Funktion tatsächlich immer eine perfekte Heuristik ist, in dem Sinne, dass sie immer die tatsächlichen Pfadkosten zurückgibt (sofern vorhanden) nichts "blockiert" die Wege).

Sie sollten auch beachten, dass alle Knoten in der richtigen Richtung (entweder horizontal oder vertikal) den gleichen erwarteten Abstand ergeben (da es viele gleich kurze Wege zum Ziel gibt). Sie sollten sich bewusst sein, dass Ihre Prioritätswarteschlange (offener Satz) bei verknüpften Prioritäten den zuletzt hinzugefügten Knoten zuerst aus der Warteschlange entfernen sollte (LIFO - Last In First Out). Auf diese Weise untersuchen Sie nur die Knoten, die sich auf dem optimalen Pfad befinden . Wenn Sie gleich geeignete Knoten auf eine FIFO-Weise (First In First Out) untersuchen, werden Sie effektiv alle Knoten untersuchen , die Teil eines besten Pfades sind. Dieses Problem tritt auf, weil es mehrere gleich gute Pfade zum Zielknoten gibt.

Thorkil Holm-Jacobsen
quelle
"(unter der Annahme, dass nichts den Weg blockiert)" - das ist eine ziemlich große Annahme. Wenn nichts den Pfad blockiert, ist zunächst kein Pfadfindungsalgorithmus erforderlich!
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft: Das stimmt, es war nur ein Gedanke, als ich das Bild von Byte56 betrachtete. Der Rest ist trotzdem wahr.
Thorkil Holm-Jacobsen
4

Ich bin mir nicht sicher, was Sie mit "immer" konsequent meinen. Ist die Manhattan-Entfernung in einem festen Raster unabhängig vom eingeschlagenen Weg? Ja, wie die Antwort von Byte56 sagte.

Beispielsweise ist die Manhattan-Entfernung bei Rotationen jedoch nicht invariant. ZB der Manhattan - Abstand ( L1-Norm ) zwischen dem Ursprung und einem Punkt (10,10)ist |10-0| + |10-0| = 20. Wenn Sie Ihre Koordinaten jedoch um 45 Grad drehen (Ihr fester Punkt liegt also in einer der Richtungen des Rasters), finden Sie jetzt den gleichen Punkt (10sqrt(2),0), also einen Manhattan-Abstand zum Ursprung von 10sqrt(2)~14.14.

Dr. Jimbob
quelle
+1 für diesen Hinweis; Die Entfernung von OTOH nach Manhattan ist bei 90-Grad-Rotationen unveränderlich. Dies sind wirklich die einzigen, die auf einem diskreten Raster „konsistent“ gemacht werden können.
Steven Stadnicki
1
Guter Fang, obwohl er erwähnt hat, dass nur horizontale und vertikale Bewegungen erlaubt sind.
Thorkil Holm-Jacobsen
1
Die ursprüngliche Frage war konsequent wie in monoton.
Emiliano