IA. Métodos de resolución de puzzle 8

Para la resolución de puzle 8 podemos utilizar dentro de búsqueda sin información las siguientes búsquedas:

• Búsqueda en Amplitud
• Búsqueda en profundidad
• Búsqueda hacia atrás
• Otras búsquedas no contempladas en el temario

Lo primero que hay que explicar que puzle 8 consiste en la creación en un juego de un tablero de 3x3 posiciones, en total 9 y una de ellas siempre está vacía. Para la resolución de este problema las posiciones las numeramos del 0 al 8 siendo la posición 0 el espacio vacío.

En este problema tenemos cuatro operadores, arriba, abajo, derecha e izquierda, que se corresponde con los movimientos que puede hacer el cubo vacio.

Estado inicial:

Estado Final a buscar (meta):

Vamos a realizar la búsqueda con 2 búsquedas diferentes para que se pueda apreciar la diferencia entre ellos en la forma de ejecución.

Nota: El espacio vacío se corresponde con el cero en la programación de esta búsqueda.

Solución búsqueda Amplitud

Como se puede apreciar, se han tenido que analizar 15 nodos en el árbol. La búsqueda es de todas las posibilidades. Los nodos con la palabra “No”, quiere decir que es igual que el problema inicial y no se analizará.

Los nodos han sido numerados por orden de procesamiento. Como se puede ver este tipo de ramificación por nodo es finito y ha sido capaz de encontrar la solución.

En este caso ha sido eficiente dado que la meta de la búsqueda ha sido muy cercana, si fuera más lejana, no sería eficiente este método de búsqueda. Esto se debe a que consume la memoria de forma exponencial.

Solución búsqueda Profundidad

En esta búsqueda podemos apreciar cómo funciona la búsqueda en profundidad, explotando en profundidad un camino, en el caso de no encontrar la solución volvería atrás a seguir explotando los otros nodos no explotados.

En este caso la solución se ha podido encontrar en la explotación del primer nodo y como se puede apreciar para este estado inicial ha sido mejor que la búsqueda en amplitud.

Esta búsqueda es más compleja porque requiere realizar el retroceso o también llamado backtraking.

El retroceso hay que hacerlo en estos casos:

1. Porque se ha llegado al final y no hay solución a buscar
2. Porque hemos llegado a un límite de explotación en profundidad (corte)

Este método está recomendado cuando la meta a buscar está muy alejada y hay problemas de memoria en el ordenador.