El problema del n-Puzzle

Qué es?

Este programa se ha implementado para resolver el juego del N-puzzle, mediante el empleo de distintos algoritmos de búsqueda.  Los algoritmos implementados son cuatro,  tres de ellos de búsqueda informada: y uno de ellos de búsqueda no informada: Para resolver el juego, estos algoritmos, parten de una configuración inicial del N-puzzle, y van recorriendo el árbol de búsqueda hacia una configuración final, intentando encontrar un camino cuya longitud sea lo más próxima a la mínima. Para realizar tal labor,  los algoritmos de búsqueda informada hacen uso de una función heurística que mide la bondad de dicho camino, razón por la cual se conoce también a este tipo de búsqueda como búsqueda heurística. En cambio, los algoritmos de búsqueda no informada no hacen uso de información adicional del problema por lo cual se les conoce con el nombre de búsqueda ciega.

Se ha partido del problema del 8-puzzle como base para todas las explicaciones posteriores, siendo fácilmente extrapolables a cualquier otro puzzle.

 

Explicación.

 En I.A. la descripción formal de un problema incluye:

(1) Estado Inicial
(2) Operadores
(3) Test del objetivo
(4) Coste del camino

La definición formal del problema del 8-puzzle es la que se presenta a continuación:
 

  1. El estado inicial viene dado por una de las posibles configuraciones de las 9 casillas, 8 de ellas numeradas del 1-8 y una de ellas en blanco.
  2. Los operadores son cuatro: mover la ficha blanca hacia el norte, el sur, el este y el oeste.
  3. El test del objetivo se cumple cuando se alcanza el estado meta, o sea, la configuración final del puzzle.
  4. El coste de cada una de las operaciones es uniforme e igual a uno. El coste del camino será la suma de los costes de las operaciones aplicadas hasta alcanzar la solución.
 El problema, entonces, puede resolverse usando las reglas en combinación con una estrategia de control adecuada, para movernos a través del espacio de estados, hasta encontrar un camino desde el estado inicial hasta el estado meta. Así pues, el proceso de búsqueda es fundamental para el proceso de resolución de problemas. Una representación gráfica de un estado, sería:

 

La documentación sigue con la caracterización del  proceso de búsqueda .

Vuelta al índice de la documentación.