Mini Proyecto #1: Eight Puzzle

Mini Proyecto 1: Eight Puzzle Josué Malik Grimaldi Aguirre A00458126 Thania Cerecedo Zamarripa A01160864 Objetivo: Desarrollar el juego Puzzle 8 con ambiente gráfico en algun lenguaje con 3 diferentes métodos de algoritmo. Hill Climbing: Por medio de este algoritmo heurístico, el programa tiene que explorar los diferentes nodos encontrados que sean validos de acuerdo a la heurística encontrando el mejor resultado de acuerdo a los valores encontrados (este algoritmo no permite el retorno a un estado anterior) si no encuentra la solución optima regresará el mejor resultado obtenido. Heurísticas Propuestas para BFS y para HC: (Nodos mas cercanos entre si que se encuentran en su posición final) explora caminos en líneas rectas tratando de buscar siempre el camino mas corto a su posición final dando como resultado un valor y toma el mas bajo que representa el camino mas corto hacia la posicion final. Best First Search: Explora todo el árbol haciendo una búsqueda en anchura pero solo expandiendo el nodo que se ve más prometedor, si al ir buscando encuentra un mal camino donde no encuentra valores mejores a las que propone la heurística este se regresará al nodo adyacente o al nivel inmediato superior que tenga una mejor solución y lo expande, asi continua hasta llegar a la solución. Busqueda ciega en Anchura: Exte método expande todos los nodos del nivel, pregunta si esta la solución ahí a cada uno, si no la encuentra, continua bajando y expande todos los nodos de ese nuevo nivel, es una búsqueda ciega hasta encontrar la solución por lo tanto no requiere de heurísticas sin embargo este método es el que consume más cantidad de memoria. Este proyecto fue desarrollado en Java mediante la aplicación llamada NetBeans 7.1 Planteamiento del problema: Se tiene un Puzzle que tiene 9 casillas en cada una existe la probabilidad de que caiga cualquier numero con rango de valores del 1 al 8+ un espacio vacio con un valor de 0, intercambiando posiciones entre si. Estado inicial: Sea cualquier combinación aleatoria de números dentro del Puzzle la cual puede ser proporcionada por el usuario en una lista dentro del programa o generar la secuencia de números de manera aleatoria. Existen entre 0 y 8 nodos en su posición correcta. Estado final: El estado final es el Puzzle colocado en forma ordenada en orden ascendente, dejando al final el espacio vacio, es decir las posiciones 1,2,3,4,5,6,7,8,0. Para este estado se contampla 9 nodos en su posición correcta. Reglas del Juego: Los números solo se pueden mover en una dirección a la vez y solo se pueden mover hacia arriba, abajo, izquierda y derecha, siempre y cuando exista un espacio en blanco a su lado al cual moverse. Pruebas del Puzzle busqueda en Anchura 8,3,2,6,4,1,5,7,0 Tiempo: 0.258s Caminos Recorridos: 1,961,701 Nodos Explorados: 4,906,983 Movimientos Requeridos: 25 7,8,2,0,4,6,1,3,5 Tiempo: 0.433s Caminos Recorridos: 4,063,127 Nodos Explorados: 9,138,313 Movimientos Requeridos: 26 0,8,2,1,4,6,7,3,5 Este puzle no tiene Solución.