Encontrar una buena heurística para una 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 aquí). El juego tiene una matriz 3x3 con el número de 1 a 9. El objetivo es llevar los números en el orden correcto utilizando la cantidad mínima de movimientos. En cada movimiento puede girar un cuadrado 2x2, ya sea en sentido horario o antihorario.

Es decir, si tienes este estado

6 3 9
8 7 5
1 2 4

y gira la parte superior izquierda 2x2 cuadrado en el sentido de las agujas del reloj que obtienes

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 conduce a la solución óptima (si la modifico, vea el aviso al final) pero no creo que sea el 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 (lo que me da la cantidad de rotación necesaria para llevar el número a esta postura) y suma todo estos valores. Es decir, tomas 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 está completamente ordenado, que H = 1.

Pero existe el problema de que gira 4 elementos a la vez. Por lo tanto, hay casos raros en los que puede hacer dos (mineral más) de estas rotaciones estimadas en un movimiento. Esto significa que estas heurísticas sobreestima 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 De Verdad resuelve el problema o si esta heurística aún se sobreestima en algunos casos de borde.

Entonces mi pregunta es: ¿Cuál es la mejor heurística que se te ocurra?

(Descargo de responsabilidad: esto es para un proyecto universitario, por lo que esto es un poco de tarea. Pero soy libre de usar cualquier recurso si se le ocurre, por lo que está bien preguntarles. También le daré crédito a StackOverflow por ayudarme; ))

Answer 1

La simplicidad es a menudo más efectiva. Considere los nueve dígitos (en el orden de las 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 lo siguiente heurístico 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 todos los demás no lo están.

Se podría argumentar que aquellos elementos que son vecinos en el estado final deben tender a acercarse durante cada paso, por lo que la distancia vecina 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, no sobreestimarse) de su enfoque teniendo en cuenta todos los números, y dividiendo por 4 y redondeando al siguiente entero.

Para mejorar la heurística, podrías ver pares de números. Si se intercambia por ejemplo, por ejemplo, en la parte superior izquierda, los números 1 y 2, necesita al menos 3 rotaciones para arreglarlas ambas, lo cual es un mejor valor que 1+1 al considerarlos por separado. Al final, aún necesita dividir por 4. Puede emparejarse los números de manera arbitraria, o incluso probar todos los pares y encontrar la mejor división en pares.