Rompecabezas Numerico

[pic 2]

[pic 3][pic 4][pic 5]

Contenido

Introducción        2

Estructura        2

Pruebas        4

Conclusiones        7

Introducción

El presente reporte tiene como objetivo mostrar cómo se implementaron algoritmos de búsqueda en rompecabezas numérico, la estructura que se utilizó para poder implementarlo, las heurísticas que se tomaron para encontrar la solución, y los algoritmos implementados.

Se mostrarán los resultados que se obtuvieron con la implementación de algoritmos de búsqueda en el juego del rompecabezas numérico, en total se aplicaron 3 algoritmos de búsqueda, estos son: el algoritmo de búsqueda primero en anchura (Breath First Search), el algoritmo de búsqueda primero en profundidad (Depth First Search) y el algoritmo A* (A estrella), para determinar cuál de estos es el mejor algoritmo que se puede aplicar, ayudándose con los nodos totales que expandieron cada uno, el número de movimientos necesarios para llegar a la solución, así como  el tiempo que les tomo resolver los rompecabezas.

Se tiene previsto realizar pruebas con rompecabezas de un tamaño de 3x3, 4x4 y 5x5.

Estructura

El proyecto cuenta con una clase Nodo, los 3 métodos para solucionar el rompecabezas requieren de la clase nodos, sus atributos son los siguientes:

• Una matriz para guardar el estado en el que se encuentra el rompecabezas.
• Una matriz que guarda el estado del nodo padre.
•  Int que guarda la profundidad a la que se encuentra.
• Int que guarda el costo que utiliza la heurística en el método A* para encontrar el camino más rápido a la solución.

Cada uno de estos atributos cuenta con sus respectivos métodos set y get para determinar y recuperar cada uno de estos atributos para utilizarlos en los métodos de solución.

La clase PuzzleSolucion sirve para determinar el tamaño de la matriz que se quiere resolver además de que cuenta con los estados iniciales y objetivos requeridos por los algoritmos para solucionar el problema.

Para solucionar los rompecabezas se implementaron 3 algoritmos:

• Algoritmo de búsqueda primero a lo ancho:

El algoritmo primero expande el nodo raíz que cuenta con el estado inicial, se utiliza una cola para añadir los nodos que se deben expandir, además de una lista de arreglos en la que se guardaran los nodos expandidos una vez que salgan de la cola, esto para evitar que entren en la cola nuevamente, lo que resultaría en un bucle infinito de nodos a expandir ya que no estarían delimitados.

Se verifican los elementos que se encuentran en la cola, si la cola está vacía pero el estado del nodo no es igual al estado objetivo, se determina que no se encontró la solución y termina el programa, en dado caso de que la cola no esté vacía tomara su elemento, verifica el estado y lo compara con el estado objetivo, terminando por añadir el nodo a la lista con los nodos expandidos, si los estados son iguales entonces encontró la solución, si no lo son, verificara el estado del nodo con los estados de los nodos que estén en la lista, si no han sido expandidos añade a la cola los nodos para expandirlos, a su vez añade los nodos hijo a otro arreglo para guardarlos a una pila que guarda el camino a la solución.

Cuando encuentre la solución el método retornara la pila con los pasos a la solución.

• Algoritmo de búsqueda en profundidad primero:

El algoritmo cuenta con la misma estructura que tiene el algoritmo de búsqueda a lo ancho, la única diferencia que tienen es que el algoritmo de búsqueda en profundidad utiliza una pila en vez de una cola, esto con el fin de que los nodos que se expanden sean los últimos que entran, expandiéndolos hacia su profundidad y no hacia lo ancho.

• Algoritmo A* (A estrella):

Este algoritmo utiliza una estructura similar a la de los algoritmos anteriores, la diferencia es que utiliza una lista de nodos a expandir, es muy parecido al de búsqueda en anchura, pero en este algoritmo se utilizan los atributos de profundidad, costo y valor de la clase nodos (es el único que los utiliza), utiliza los costos para verificar cuál es el mejor movimiento que puede hacer en su estado, determina el mejor movimiento mediante la fórmula  f(n))=g(n)+h(n)  en la que la función mínima o el valor de la función va a ser igual a la suma del costo de llegar al estado actual más el valor de la función heurística.

Se utiliza el mismo método para expandir nodos en los 3 algoritmos, primero toma el estado del nodo que se va a expandir, crea un nodo hijo y le asignara el mismo estado del padre, entonces verificara la posición en la que se encuentra el cero, y dependiendo de la posición del cero determinara la acción que se realizará, si no está en la última columna entonces puede hacer un movimiento a la derecha, toma el valor que está a la derecha del cero se lo asigna a la posición en la que se encuentra y a la siguiente le asigna cero, si la posición no está en la última fila entonces puede moverse para abajo, realiza la misma operación de búsqueda del cero y la sustitución entre los valores, si no está en la primera fila entonces puede moverse hacia arriba y si no se encuentra en la primera columna puede moverse hacia la izquierda, los nodos hijos que se vayan creando los guardara en una lista de arreglos de nodos.

El método para determinar el valor de la heurística para el algoritmo A* recibe un nodo del cual toma su estado, y cuenta los pasos para llegar al estado objetivo mediante un valor numérico que va sumando al comparar 2 matrices. Verificando el número de fichas que están mal colocadas y acumulando el número total de pasos que le tomaría acomodarlas para tomar la mejor opción.

Pruebas

Para verificar el funcionamiento de los algoritmos se realizaron distintas pruebas:

Para las matrices de 3x3 se tomó como ejemplo el siguiente estado inicial.

...