Trouver une bonne heuristique A * Recherche

Question

Je suis en train de trouver la solution optimale pour un petit jeu de puzzle appelé Twiddle (une applet avec le jeu peut être trouvé ici ). Le jeu a une matrice 3x3 avec le nombre de 1 à 9. Le but est d'amener les chiffres dans le bon ordre en utilisant la quantité minimum de mouvements. Dans chaque mouvement que vous pouvez faire pivoter un 2x2 soit carré dans le sens horaire ou antihoraire.

i.e.. si vous avez cet état

6 3 9
8 7 5
1 2 4

et vous faites pivoter le 2x2 supérieur gauche vers la droite place, vous obtenez

8 6 9
7 3 5
1 2 4

J'utilise un A * chercher pour trouver la solution optimale. Mon f () est simplement le nombre de rotations nécessaires. Ma fonction heuristique déjà conduit à la solution optimale (si je le modifier, voir l'avis a t la fin) mais je ne pense pas que c'est le meilleur que vous pouvez trouver. Mon heuristique actuelle prend chaque coin, regarde le numéro dans le coin et calcule la distance manhattan à la position ce nombre aura dans l'état résolu (ce qui me donne le nombre de rotation nécessaire pour porter le nombre à cette postion) et sommes tous ces valeurs. C'est à dire. Vous prenez l'exemple ci-dessus:

6 3 9
8 7 5
1 2 4

et cet état de fin

1 2 3
4 5 6
7 8 9 

puis l'heuristique effectue les opérations suivantes

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

En outre, si h est égal à 0, mais l'état ne soit pas complètement ordonné, que h = 1.

Mais il y a le problème, que vous faites pivoter 4 éléments à la fois. Il y a donc un cas rares où vous pouvez faire deux (ou plus) les thèses des rotations estimées en un seul mouvement. Ce moyen heuristique thèses surestime la distance par rapport à la solution.

Ma solution actuelle est simplement exclu l'un des coins du calcul qui permet de résoudre ce problème au moins pour mon test-cas. Je l'ai fait aucune recherche si vraiment permet de résoudre le problème ou si ce surestime fixes heuristiques dans certains cas bord.

Alors ma question est: Quelle est la meilleure heuristique vous pouvez venir avec

(Avertissement: Ceci est un projet universitaire, c'est donc un peu de devoirs Mais je suis libre d'utiliser toute ressource si peut venir avec, il est donc normal de vous demander les gars aussi je créditera Stackoverflow pour.. me aider;))

Answer 1

La simplicité est souvent le plus efficace. Considérons les neuf chiffres (dans les lignes-premier ordre) comme formant un seul entier. La solution est représentée par le plus petit entier possible i (g) = 123456789. Par conséquent nous proposons l'heuristique h suivant (s) = i (s) - i (g). Pour exemple, h (s) = 639875124 - 123456789.

Answer 2

Tous les éléments doivent être pris en compte lors de calculer la distance, non seulement des éléments de coin. Imaginez que tous les éléments d'angle 1, 3, 7, 9 sont à leur domicile, mais tous les autres ne sont pas.

On pourrait faire valoir que ces éléments qui sont voisins dans l'état final devrait tendre à se rapprocher au cours de chaque étape, si la distance voisine peut également faire partie d'heuristique, mais probablement une influence plus faible que la distance des éléments à leur état final.

Answer 3

Vous pouvez obtenir une heuristique admissible (à savoir, non surestimant) de votre approche en prenant tous les numéros en compte, et en divisant par 4 et arrondi à l'entier.

Pour améliorer l'heuristique, vous pouvez regarder des paires de nombres. Si par exemple en haut à gauche les numéros 1 et 2 sont permutés, vous avez besoin d'au moins 3 rotations pour les fixer à la fois haut, ce qui est une meilleure valeur que 1 + 1 de les considérer séparément. En fin de compte, vous avez encore besoin de diviser par 4. Vous pouvez jumeler des nombres arbitrairement, ou même essayer toutes les paires et trouver la meilleure division en paires.