Ich habe vor kurzem einen Einführungskurs in Künstliche Intelligenz begonnen und mir wurde eine Aufgabe zugewiesen, eine zulässige heuristische Funktion in Python zu implementieren, die das 15-Puzzle mit A * -Suche löst.Zulässige Heuristische Manhattan Entfernung
Ich implementierte die Manhattan Entfernung zusammen mit einigen anderen Heuristiken. Der Python-Code funktionierte gut und der Algorithmus löst das Problem tatsächlich, aber ich habe Zweifel, ob die Manhattan-Distanzheuristik für dieses spezielle Problem zulässig ist.
Nach der Theorie eine Heuristik ist zulässig, wenn es nieüberschätzt die Kosten um das Ziel zu erreichen. Das bedeutet, dass die Heuristik optimistisch ist und die Kosten nie höher sind als die tatsächliche.
Wenn der Anfangszustand ist die folgende (0 bedeutet den leeren Slot):
1 2 3 4
0 6 7 8
5 9 10 12
13 14 11 15
mein Programm, das Problem mit 5 bewegt sich löst, aber die Summe der Manhattan Entfernungen jeder fehl am Platz Fliese ist gleich 10 Das ist der doppelte Wert der tatsächlichen Kosten. Die tatsächlichen Kosten sind also viel geringer als die geschätzten Kosten. Bedeutet das, dass die Heuristik nicht zulässig ist oder stimmt etwas nicht mit meiner Logik?
Ich dachte daran, nur die Manhattan-Distanz des leeren Blocks zu zählen, aber das würde zu Zuständen mit null geschätzten Kosten führen, wenn der leere Block an der richtigen Stelle ist, aber andere Kacheln verlegt sind.
Sie haben uns nicht Ihre Logik gezeigt, so wie sollen wir sie bewerten? –
Ich habe keine Probleme mit dem Code. Meine Frage ist eine theoretische Frage. Das Problem kann mit fünf Zügen gelöst werden. Jedes Mal, wenn die leere Kachel nach oben, unten, rechts oder links bewegt wird. Die fünf Bewegungen, die das Problem lösen, sind: Unten, Rechts, Rechts, Unten, Rechts. Aber wenn Sie die Heuristik auf den Ausgangszustand anwenden, gibt es 10 zurück, was das Doppelte der tatsächlichen Kosten ist. Es sollte weniger als die tatsächlichen Kosten nach Theorie sein. Sie benötigen den Code nicht, um die Manhattan-Entfernung zu berechnen. [Manhattan Entfernung] (http://en.wiktionary.org/wiki/Manhattan_distance) Danke für die schnelle Antwort;) – dimlucas
Es sieht für mich aus wie die Gesamtsumme von Manhattan Distanzen ist in der Tat 5 in Ihrem Beispiel. Wie bekommst du 10? –