Miniproyecto #1: Eight Puzzle

Instituto Tecnológico y de Estudios Superiores de Monterrey.

Campus Estado de México

Mini Proyecto 1: Eight Puzzle

Sebastián Olivares García.

Marco Chávez Fuentes.

Luis Tituaña Criollo.

Enrique García Araico.

El proyecto consta de resolver un Eight Puzzle por medio de algoritmos 

de búsqueda no informados y los algoritmos heurísticos. El lenguaje de programación que utilizamos para el proyecto fue Java debido a nuestro conocimiento previo en el transcurso de la carrera y la fácil portabilidad a una interfaz gráfica en Android.

Los algoritmos heurísticos implementados son BFS (Best First Search) y Hill Climbing.

En la primera heurística, utilizamos distancia Manhattan del numero que queremos mover a la posición final de este. Primero creamos todos los posibles movimientos que se pueden hacer para después asignarle un peso a cada uno. Para asignar los pesos, generamos una matriz con todos los posibles costos Manhattan de acuerdo a su posición. Una vez asignado un coste a todos los nodos, escogemos el mejor nodo y repetimos el proceso.

En la segunda heurística implementada para Hill Climbing, debido a que conocemos el estado final, tenemos que tener en cuenta 3 variables; el número que queremos mover, el espacio vacío y el destino final de dicho número.

Observando detenidamente, nos dimos cuenta que necesitamos una relación entre estas variables, por lo que utilizamos 3 distancias Manhattan para medir el costo de cada nodo creado.

• Primer Manhattan: Relación (Número - Destino final)
• Segundo Manhattan: Relación  (Número - Espacio vacío)
• Tercer Manhattan: Relación (Espacio vacío - Destino final)

Una vez que obtuvimos esta relación nos encontramos con ciertos casos específicos donde el costo era el mismo pero la solución no. Para esto, decidimos asignarle una prioridad a cada Manhattan.

• Primer Manhattan x 100
• Segundo Manhattan x 10
• Tercer Manhattan x 1

El tercer problema que encontramos, era que al posicionar el primer número, todo se encontraba perfecto, pero al intentar acomodar el segundo el primero tenía que ser desplazado en algunos casos. Nuestra solución fue poner nuevos Constrains para que evitara mover los números ya posicionados en su lugar correcto.

Estas heurísticas resuelven el problema aproximadamente con 200 nodos generados de los cuales solo visita la mitad. Mientras que una búsqueda en Anchura genera 9! nodos.

Tabla comparativa

	Tiempo	Nodos Generados	Nodos Visitados
BFS	156ms	327	203
Hill Climbing	123ms	108	68