Gute Heuristik für eine* Suche finden

Question

Ich versuche, die optimale Lösung für ein kleines Puzzlespiel namens Twiddle zu finden (ein Applet mit dem Spiel ist gefunden hier). Das Spiel verfügt über eine 3x3 -Matrix mit der Zahl von 1 bis 9. Ziel ist es, die Zahlen mit der minimalen Anzahl von Bewegungen in der richtigen Reihenfolge zu bringen. In jeder Bewegung können Sie ein 2x2 Quadrat entweder im Uhrzeigersinn oder gegen den Uhrzeigersinn drehen.

Dh wenn Sie diesen Zustand haben

6 3 9
8 7 5
1 2 4

und Sie drehen den oberen linken 2x2 quadratisch im Uhrzeigersinn Sie erhalten

8 6 9
7 3 5
1 2 4

Ich verwende eine A* -Suche, um die optimale Lösung zu finden. Mein f () ist einfach die Anzahl der benötigten Rotationen. Meine heuristische Funktion führt bereits zu der optimalen Lösung (wenn ich sie modifiziere, sehen Sie die Mitteilung am Ende), aber ich denke nicht, dass es das Beste ist, was Sie finden können. Meine aktuelle Heuristik nimmt jede Ecke, betrachtet die Nummer an der Ecke und berechnet die Manhatten -Entfernung zur Position, die diese Zahl im gelösten Zustand hat (was mir die Anzahl der Drehungen gibt diese Werte. Dh du nimmst das obige Beispiel:

6 3 9
8 7 5
1 2 4

und dieser Endzustand

1 2 3
4 5 6
7 8 9 

Dann macht die Heuristik Folgendes

6 is currently at index 0 and should by at index 5: 3 rotations needed
9 is currently at index 2 and should by at index 8: 2 rotations needed
1 is currently at index 6 and should by at index 0: 2 rotations needed
4 is currently at index 8 and should by at index 3: 3 rotations needed

h = 3 + 2 + 2 + 3 = 10

Außerdem, wenn H 0 ist, aber der Zustand nicht vollständig geordnet ist, als H = 1.

Aber es gibt das Problem, dass Sie 4 Elemente gleichzeitig drehen. Es gibt also seltene Fälle, in denen Sie zwei (mehr) von diesen geschätzten Rotationen in einer Bewegung durchführen können. Dies bedeutet, dass diese Heuristik die Entfernung zur Lösung überschätzt.

Meine derzeitige Problemumgehung besteht darin, einfach eine der Ecken aus der Berechnung auszuschließen, die dieses Problem zumindest für meine Testbeschlüsse löst. Ich habe keine Nachforschungen angestellt, wenn Ja wirklich Löst das Problem oder wenn diese Heuristik in einigen Kantenwagen immer noch überschätzt.

Meine Frage ist also: Was ist die beste Heuristik, die Sie sich einfallen lassen können?

(Haftungsausschluss: Dies gilt für ein Universitätsprojekt. Dies ist also ein bisschen Hausaufgaben. Aber ich kann eine Ressource verwenden, wenn es sich einfallen kann. Es ist also in Ordnung, Sie zu fragen. Außerdem werde ich Stackoverflow für die Hilfe für mir helfen. ))

Answer 1

Einfachheit ist oft am effektivsten. Betrachten Sie die neun Ziffern (in der Reihenfolge der Reihen erster Reihenfolge) als eine einzelne Ganzzahl. Die Lösung wird durch die kleinstmögliche Ganzzahl i (g) = 123456789 dargestellt. Daher schlage ich die folgende heuristische H (s) = i (s) - i (g) vor. Für Ihr Beispiel h (s) = 639875124 - 123456789.

Answer 2

Alle Elemente sollten bei der Berechnung der Entfernung berücksichtigt werden, nicht nur Eckelemente. Stellen Sie sich vor, alle Eckelemente 1, 3, 7, 9 sind zu Hause, aber alle anderen nicht.

Es könnte argumentiert werden, dass jene Elemente, die im letzten Zustand Nachbarn sind, in jedem Schritt neigen sollten, so

Answer 3

Sie können eine zulässige (dh nicht überschätzende) Heuristik von Ihrem Ansatz erhalten, indem Sie alle Zahlen berücksichtigen und sich um 4 dividieren und sich auf die nächste Ganzzahl rundeten.

Um die Heuristik zu verbessern, können Sie sich Paare von Zahlen ansehen. Wenn zB oben links die Nummern 1 und 2 ausgetauscht werden, benötigen Sie mindestens 3 Rotationen, um sie beide zu beheben, was ein besserer Wert als 1+1 ist, wenn Sie sie getrennt betrachten. Am Ende müssen Sie sich immer noch um 4 teilen. Sie können Zahlen willkürlich zusammenstellen oder sogar alle Paare ausprobieren und die beste Teilung in Paare finden.