Wie ist Manhattan eine zulässige Heuristik?

Question

Ist es nicht wahr, dass das Zählen der Züge für 1 Kachel dazu führen kann, dass andere Kacheln ihren Zielzustand erreichen? Und daher kann das Zählen für jedes Plättchen uns mehr zählen als die minimalen Bewegungen, die erforderlich sind, um den Zielzustand zu erreichen?

Diese Frage steht im Kontext von Manhattan Entfernung für 15-Puzzle. Hier

ist die Frage in anderen Worten:

Kann verwenden wir Manhattan-Distanz als eine zulässige Heuristik für N-Puzzle. Um die A * -Suche zu implementieren, benötigen wir eine zulässige Heuristik. Ist Manhattan Heuristik ein Kandidat? Wenn ja, wie kontern Sie das obige Argument (die ersten 3 Sätze in der Frage)?

Definitionen: A* ist eine Art Suchalgorithmus. Es verwendet eine heuristische Funktion, um die geschätzte Entfernung zum Ziel zu bestimmen. Solange diese heuristische Funktion den Abstand zum Ziel niemals überschätzt, wird der Algorithmus den kürzesten Pfad finden, wahrscheinlich schneller als die Breite der ersten Suche. Eine Heuristik, die diese Bedingung erfüllt, ist zulässig.

Answer 1

Zulässige Heuristiken dürfen die Anzahl der Schritte zur Lösung dieses Problems nicht überschätzen. Da Sie die Blöcke 1 nur zu einer Zeit und nur in einer von vier Richtungen bewegen können, ist das optimale Szenario für jeden Block, dass es einen klaren, unbehinderten Weg zu seinem Zielzustand hat. Dies ist ein M.D. von 1.

Der Rest der Zustände für ein Paar Blöcke ist suboptimal, was bedeutet, dass mehr Züge als der M.D. nimmt, um den Block an der richtigen Stelle zu bekommen. Somit wird die Heuristik niemals überschätzt und ist zulässig.

Ich werde löschen, wenn jemand eine korrekte, formale Version von diesem postet.

Answer 2

Formaler Beweis: Definition von h, h (s *) = 0, wenn s * der Zielzustand ist. Nehmen Sie für den Beweis durch Widerspruch , dass C * < h (s0) für einige Anfangszustand s0. Beachten Sie, dass, da jede Aktion nur eine Kachel verschieben kann, die Ausführung einer Aktion höchstens h um eins reduzieren kann. Da das Ziel in C * -Aktionen erreicht werden kann, haben wir h (s *) ≥ h (s0) - C *> 0, was uns zu einem Widerspruch führt, da h (s *) Null sein sollte. Deshalb müssen wir h (s0) ≤ C * für s0 haben, und h ist zulässig. (Quelle: Universität von Kalifornien, Irvine)