lunes, 6 de febrero de 2017
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:
- Porque se ha
llegado al final y no hay solución a buscar
- 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.
Suscribirse a:
Entradas (Atom)