Stimmt es nicht, dass das Zählen der Züge für eine Kachel dazu führen kann, dass andere Kacheln ihren Zielzustand erreichen? Und daher kann das Zählen für jede Kachel uns mehr zählen als die minimalen Bewegungen, die erforderlich sind, um den Zielzustand zu erreichen?
Diese Frage steht im Zusammenhang mit Manhattan Entfernung für 15-Puzzle.
Hier ist die Frage in anderen Worten:
Können wir Manhattan-Entfernung als zulässige Heuristik für N-Puzzle verwenden? 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 .
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 von Blöcken ist suboptimal, was bedeutet, dass mehr Bewegungen als der M. D. braucht, um den Block an die richtige Stelle zu bringen. Somit wird die Heuristik niemals überschätzt und ist zulässig.
Ich werde löschen, wenn jemand eine korrekte, formelle Version von diesem postet.
Formaler Beweis: Definition von h, h (s *) = 0, wenn s * der Zielzustand ist. Nehmen Sie für den Beweis durch Widerspruch an dass C * & lt; h (s0) für einen Anfangszustand s0. Beachten Sie, dass sich jede Aktion verschieben kann Nur eine Kachel, die eine Aktion ausführt, kann höchstens h um eins reduzieren. Da kann das Ziel sein in C * -Aktionen erreicht werden, haben wir h (s *) ≥ h (s0) - C * & gt; 0, was uns zu einem bringt Widerspruch, da h (s *) Null sein sollte. Daher müssen wir für alle Zeiten h (s0) ≤ C * haben s0 und h ist zulässig. ( Quelle : Universität von Kalifornien, Irvine)
Tags und Links algorithm artificial-intelligence a-star heuristics