Encontrar una buena heurística para A * búsqueda

Question

Estoy tratando de encontrar la solución óptima para un pequeño juego de rompecabezas llamado Twiddle (se puede encontrar un applet con el juego here). El juego tiene una matriz de 3x3 con el número del 1 al 9. El objetivo es traer los números en el orden correcto usando la cantidad mínima de movimientos. En cada movimiento puede rotar un cuadrado de 2x2 en sentido horario o antihorario.

I.e. si usted tiene este estado

6 3 9 
8 7 5 
1 2 4 

y girar el cuadrado de 2x2 parte superior izquierda hacia la derecha se obtiene

8 6 9 
7 3 5 
1 2 4 

Estoy usando una búsqueda A * para encontrar la solución óptima. Mi f() es simplemente el número de rotaciones necesarias. Mi función heurística ya me lleva a la solución óptima (si la modifico, vea el aviso al final) pero no creo que sea la mejor que pueda encontrar. Mi heurística actual toma cada esquina, mira el número en la esquina y calcula la distancia de manhatten a la posición que este número tendrá en el estado resuelto (que me da el número de rotación necesario para llevar el número a esta posición) y suma todos estos valores Es decir. Se toma el ejemplo anterior:

6 3 9 
8 7 5 
1 2 4 

y este estado final

1 2 3 
4 5 6 
7 8 9 

entonces la heurística hace lo siguiente

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 

Además, si h es 0, pero el estado no es completamente ordenó, que h = 1.

Pero existe el problema de rotar 4 elementos a la vez. Entonces hay casos raros en los que puede hacer dos (o más) de estas rotaciones estimadas en un solo movimiento. Esto significa que la heurística de tesis sobrestima la distancia a la solución.

Mi solución actual es, simplemente, excluir una de las esquinas del cálculo que resuelve este problema al menos para mis casos de prueba. No he investigado si realmente resuelve el problema o si esta heurística todavía sobreestima en algunos casos extremos.

Así que mi pregunta es: ¿Cuál es la mejor heurística que se te puede ocurrir?

(Descargo de responsabilidad: Esto es para un proyecto universitario, así que esto es un poco de tarea. Pero soy libre de usar cualquier recurso si se me ocurre, así que está bien preguntarles chicos. También les daré crédito Stackoverflow por ayudarme;))

Answer 1

La simplicidad suele ser más efectiva. Considere los nueve dígitos (en el orden de filas primero) como formando un solo entero. La solución está representada por el entero más pequeño posible i (g) = 123456789. Por lo tanto, sugiero la siguiente heurística h (s) = i (s) - i (g). Para su ejemplo, h (s) = 639875124 - 123456789.

Answer 2

Todos los elementos deben tenerse en cuenta al calcular la distancia, no solo los elementos de la esquina. Imagine que todos los elementos de esquina 1, 3, 7, 9 están en su casa, pero los demás no.

Se podría argumentar que aquellos elementos que son vecinos en el estado final debe tienden a aproximarse durante cada paso, por lo que el vecino distancia también puede ser parte de la heurística, pero probablemente con una influencia más débil que la distancia de los elementos a su estado final .

Answer 3

Puede obtener una heurística admisible (es decir, sin sobreestimar) de su enfoque tomando todos los números en cuenta, y dividiendo por 4 y redondeando al siguiente entero.

Para mejorar la heurística, podría observar pares de números. Si, por ejemplo, en la parte superior izquierda, los números 1 y 2 se intercambian, necesita al menos 3 rotaciones para arreglarlos, lo que es un valor mejor que 1 + 1 al considerarlos por separado. Al final, todavía necesita dividir entre 4. Puede emparejar números arbitrariamente, o incluso probar todos los pares y buscar la mejor división en pares.