Puzzle

Heurísticas 8-Puzzle
Introducción:
En el siguiente documento se busca comparar tres tipos diferentes de heurísticas para dar solución al juego del 8-puzzle, todos las heurísticas acá propuestas serán analizadas por el algoritmo de A estrella, ya que este algoritmo asegura optimalizad siempre y cuando la heurística siempre subestime el valor total de pasos para dar solución al camino más cortoal objetivo, no se tratara la optimalizad como medio para juzgar la heurística sino que se buscara la que sea más rápida o que encuentre el camino más corto en menos pasos.
Heurísticas:
Manhattan: Esta heurística califica a cada nodo tomando en cuenta la distancia que tiene hasta su posición objetivo, es decir a una casilla se le asigna el valor de cuantos pasos le tomaría llegar a la casilla finaldonde quedaría ordenado, la suma de todos los valores de las casillas del tablero forman el dato de la heurística del tablero.
Numero de cuadros desordenados: Esta heurística únicamente cuenta cuantas casillas se encuentran en una posición desordenada, es decir que no están ubicadas en su posición final, esta heurística no es tan eficiente como la manhattan pero garantiza subestimación.
Blanco:Esta heurística calcula la distancia de la casilla en blanco entre su posición inicial y su estado en el tablero final.

Prueba:
Realizaremos el análisis de el algoritmo A estrella con cada una de las heurísticas anteriormente propuestas, para esto usaremos como ejemplo el siguiente puzzle y representamos también su respectiva solución.

Tablero inicial Tablero soluciónManhattan:
Usando esta heurística sobre el estado inicial del tablero podemos calcular el árbol de expansión pertinente, la casilla blanca puede moverse en 3 direcciones diferentes, así que esos serán los primeros nodos de nuestro árbol, cada uno de esos nodos tienen su propio valor de A estrella que se insertan en nuestra cola de prioridad.
1
2
3
4
 
6
7
5
8
f(1) f(2)f(3)
Los valores para cada una de las funciones A estrella de los anteriores nodos son las siguientes.















La cola de prioridad es la siguiente.
n
1
2
3
C
3
5
5

De esta forma agregamos estos tres valores a nuestra cola de prioridad y expandimos el nodo que denominamos como 1, en adelante no realizaremos el procedimiento completo de todos los nodos sino que expresaremos elresultado de su función y como interviene en el desarrollo del algoritmo.
Al expandir el nodo 1 tendremos otros 3 nodos, no revisamos el nodo del que vinimos, ahora h(4,), h(5) y h(6) tendrán valor de 2 ya que el valor de h de su nodo padre fue 1, realizando los cálculos de los nodos hijos del nodo 1 tendremos la siguiente cola de prioridad.

n
4
2
3
5
6
C
3
5
5
5
5

Si repetimos el procedimiento unavez más llegamos al objetivo, demostrando que la correspondiente heurística aplicando el algoritmo A estrella encuentra el camino más corto en 3 pasos.


Cuadros desordenados:
Esta heurística trata en la manera de lo posible de no mover cuadros que ya se encuentren ordenados, de no tener esa opción moverá cualquiera, gracias a la cola de prioridad del A estrella nos aseguramos de no entrar en ciclosy de encontrar la solución optima
Para la primera iteración tendremos los mismos 3 nodos iniciales que en la de manhattan ya que son los únicos movimientos posibles, veremos que para este puzzle la heurística de cuadros desordenados es igual de eficiente que la heurística de manhattan en la relación de pasos a ejecutar para encontrar la solución.
1
2
3
4
 
6
7
5
8
f(1)f(2) f(3)
Los valores para cada una de las funciones A estrella de los anteriores nodos son las siguientes.














Podemos apreciar que las funciones de A estrella son idénticas que en el caso de manhattan, pero debemos tener en cuenta que la heurística de manhattan es mejor que la de cuadros desordenados ya que al acercar un cuadro a su respectivo lugar la heurística...