Búscalo aquí:

Problema del 8 puzzle y Búsqueda No Informada [código]

El tradicional juego del 8-puzzle consiste, en dado un tablero con 9 casillas, las cuales van enumeradas del 1 al 8 más una casilla vacía. Dicha casilla vacia, es la que, con movimientos horizontales, verticales, hacia la izquierda o derecha, debe ser desplazada e intercambiada con alguno de sus vecinos, de manera que, dada una configuración inicial se llegue a una configuración final (meta). Este problema, al tratar de ser resuelto computacionalmente representa un problema al que debemos de tratar con sumo cuidado.


Aunque las reglas del juego sean sencillas de realizar (y evidentemente de programar) conlleva una complejidad mayor al momento de obtener la solución, es por esta razón que resulta un ejemplo clásico y muy didáctico para poner en práctica algoritmos de búsqueda que encuentren la solución eficiente a una configuración de 8-puzzle.


Búsqueda No Informada
Para la solución del problema del 8-puzzle presentamos 3 soluciones haciendo uso de algoritmos de busqueda no informada:

  1. Búsqueda primero en amplitud: expande el nodo más interno sin visitar, colocando sus nodos borde en una estructura FIFO.
  2. Búsqueda primero en profundidad limitada: expande el nodo más profundo que aún no había sido expandido, colocando sus nodos borde en una estructura LIFO, expandiendose como máximo hasta una profundidad límite.
  3. Búsqueda en profundidad iterativa: combina la búqueda primero en profundidad con la búsqueda primero en amplitud.
Desde aquí pueden descargar un documento de referencia. Es importante aclarar que este tipo de búsqueda no aseguran que siempre, dada una configuración inicial se encontrará la solución, esto debido a lo que se conoce como error de paridad.

Para entender que es error de paridad, primero debemos saber que es una inversión. Una inversión se presenta cuando un número mayor está "delante" de un número menor al colocar los números en una sola fila.

Es decir, si tuviesemos un estado: "123485760", donde 0 representa a la casilla vacía, tendríamos que 8 se encuentra delante de 5, 7 y 6, lo que da un numero de 3 inversiones; y también el 7 esta delante de 6, lo que suma un total de 4 inversiones. El número total de inversiones para este estado fue 4, es decir un número par, lo que significa que el juego tiene solución. Si el número total de inversiones hubiese resultado impar, el juego con dicho estado inicial, no tendría solución.


Implementación
Se ha implementado los 3 algoritmos de búsqueda no informada. La implementación de los algoritmos de búsqueda primero en amplitud, primero en profundidad limitada y en profundidad iterativa se ha realizado usando C++ sobre el compilador MingW 5.1.4.

Para la implementación de estos algoritmos se hace uso de Tablas Hash. El código fuente en C++ de las tablas Hash usadas se encuentran en los post tablas hash [código] y tablas hash 2 [código].

El codigo fuente y ejecutable para la solución del problema del 8 puzzle se puede descargar desde aqui.


Experimentos
Se realizaron experimentos acerca de la complejidad de los algoritmos implementados, las características del computador sobre el que se realizaron los experimentos son: procesador Pentium IV con memoria RAM 512 MB sobre el sistema operativo Windows XP usando el lenguaje de programación C++ con el compilador MinGW 5.1.4.

Los criterios tomados en cuenta para los experimentos fueron:

Generación automática de estados

El estado inicial para un determinado juego de puzzle es generado de manera aleatoria.


Tamaño de la Tabla Hash
El tamaño de la tabla hash quedo determinada en base a la propiedad del juego. El juego tiene 9 casillas, por lo tanto se podran realizar 9! = 362 880 permutaciones diferentes. De la misma manera se medira la efectividad de la funcion hash la cual se determina mediante la fórmula

efectividad de función hash = # de accesos directos/ # de accesos totales * 100

Número de Nodos generados
Es la cantidad total de nodos que se han ido generando durante el proceso de busqueda. El número de nodos generados es un indicador que nos permite medir la complejidad de tiempo para un determinado tipo de búsqueda.


Número de Nodos en memoria
Es la cantidad total de nodos que despúes de ser generados han sido guardados en algun TAD (Tipo Abstracto de Datos), la cual, según sea el caso, puede tratarse de una pila o cola. El número de nodos en memoria es un indicador que nos permite medir la complejidad de espacio para un determinado tipo de búsqueda.


Profundidad del árbol de búsqueda
Existen dos medidas de la profundidad: la profundidad máxima del espacio de estados, la cual nos indica el nivel máximo hasta el cual se expande el árbol; y la profundidad de solución de menor costo, la cual nos indica la profundidad en la cual se encontró la solución.


Los resultados de los experimentos realizados se presentan en este documento.



Espero les sea de utilidad, saludos.


Quieres leer más post como éste???...suscribete aquí!!!

12 comentarios:

  1. MUY BUENAS NOCHES JORGE, ME PARECIO MUY INTERESANTE
    LA INFORMACION QUE APORTA, PERO EN ESTOS MOMENTOS ME ENCUENTRO CON UN PROBLEMA DE PROGRMACION EXHAUSTIVA, ME GUSTARIA CONOCER LA IMPLEMENTACION DEL PUZZLE EN C UTILIZANDO ESTE METODO DE PROGRMACION, NO ES NECESARIO TODO EL CODIGO, TAN SOLO LA FUNCION QUE LO RESUELVA, LE ESTARE MUY AGRADECIDO SI ME RESPONDE AL SIGUIENTE CORREO rafajl0007@hotmail.com, muchisimas gracias.

    edgar rafael jimenez lopez

    ResponderEliminar
  2. Hola Edgard, cuando emncionas programación exhaustiva asumo que, para este caso del puzzle, te refieres al tipo de búsqueda exhaustiva, la cual consiste en probar para todas las posibles combinaciones de valores de cada nodo hasta dar con la solución. El tipo de algoritmo comunmente usado para estos casos es el backtracking (vuelta atras). Deberías revisar el código que adjunto en el post, tal vez te pueda alguna idea.

    ResponderEliminar
  3. Buen dia Jorge Carlos me dejaron exactamente este juego en la licenciatura y no tengo idea de como hacerlo podrias enviarme el codigo iker07@gmail.com

    ResponderEliminar
  4. Buenos dias Jorge Carlos, mira estuve revisando el blog sobre como resolver el problema del puzzle 8 utilizando los algoritmos de busquedas en profundidad, me parecio muy bueno y esta muy bien explicado todo. Sin embargo me gustaria poder descargar los fuentes de como vos desarrollaste el problema, pero el link que aparece http://joshi.ueuo.com/archivos/BNI-8puzzle.rar no sirve, sera que puedes colaborarme con esto, mandandome un link donde descargar los fuentes, o los fuentes a mi correo: john.blanco@gmail.com

    Muchas gracias...

    ResponderEliminar
  5. no sean ratas y programen su solucion.

    ResponderEliminar
  6. sos un groso!!!.si no fuera por vos no hubieramos encontrado la solucion por suerte ya hicimos el codigo.

    ResponderEliminar
  7. Alguien me puede pasar el codigo de este tema x favor? lo necesito urgente. Gracias

    ResponderEliminar
  8. Hola, podrian poner igual un codigo de ejemplo en c++ de busqueda informada y no informada aplicada en arboles binarios

    ResponderEliminar
  9. hola, tengo el problema del 8 puzzle con busquedas por amplitud, profundidad e iterativa, noce si me pudieras ayudar utilizando java. mi correo es: alrive190@hotmail.com

    ResponderEliminar
  10. Alguien tiene el código en java por favor, lo necesito urgente mi correo es lincol_jrg@hotmail.com
    Quisiera una mano en esto por favor

    ResponderEliminar
  11. Buen día, se que este post ya tiene algo de tiempo pero necesito ayuda con el código, me encargaron que lo modificara para que mostrara los cambios que se verían en el puzzle para llegar a la solución, en el código vi una función llamada mostrarPuzzle, pero nunca se usa, donde y/o como podré ponerla para que haga lo que me piden?...de antemano gracias, mi correo es javierg.ramos@hotmail.com

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...