algorithm - tipos - propiedades de la heuristica
Encontrar una buena heurística para A*búsqueda (3)
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.
Es decir, si tiene este estado
6 3 9
8 7 5
1 2 4
y gira la esquina superior izquierda de 2x2 en el sentido de las agujas del reloj
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, 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 está completamente ordenado, entonces 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.
Entonces 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 le daré crédito a Stackoverflow por ayudarme; )
La simplicidad a menudo es 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.
Puede obtener una heurística admisible (es decir, no 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, puedes mirar 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.
Todos los elementos deben tenerse en cuenta al calcular la distancia, no solo elementos de esquina. Imagine que todos los elementos de esquina 1, 3, 7, 9 están en su casa, pero los demás no.
Podría argumentarse que aquellos elementos que son vecinos en el estado final deberían tender a acercarse durante cada paso, por lo que la distancia cercana 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.