TOPICO: Inteligencia Artificial: Laboratorio 2

Busqueda No Informada

Implementar un programa que resuelva el 8 puzzle utilizando la estrategia de búsqueda primero en amplitud, utilizar una tabla hash para mapear los nodos ya visitados
Implementar un programa que resuelva el 8 puzzle utilizando la estrategia de búsqueda primero en profundidad (limitada), utilizar una tabla hash para mapear los nodos ya visitados
Implementar un programa que resuelva el problema de 8 puzzle utilizando la estrategia de búsqueda de profundidad iterativa, utilizar una tabla hash para mapear los nodos ya visitados
Realizar pruebas y comparaciones entre los 3 algoritmos, el documento lo pueden descargar de aquí.

Para la resolución de los problemas planteados, utilizamos DrScheme. A continuación un breve resumen de ideas de como fue programado y también algunas pantallas del programa:

Vista General de la interfaz hecha en Scheme

La realización de interfaces en DrScheme es muy sencillo, una guía puedes encontrar en: http://download.plt-scheme.org/doc/mred/ donde por ejemplo para la creación del frame usamos:

(define frame (instantiate frame%
("Algoritmos de Busqueda en 8-Puzzle")
[width 600]
[height 555]));Titulo

Para mostrarlo ponemos: (send frame show #t)

Podemos distribuir el frame creado en paneles, por ejemplo para nuestro caso tenemos varios paneles, veamos el panel de las figuras, donde tenemos un panel horizontal (Panel Figura) que contiene a dos paneles verticales, uno con la imagen completa y a otro con pequeñas imagenes:

(define panelfigura (instantiate horizontal-panel% (frame)
[style '(border)]
[min-width 10]
[stretchable-width #f]
[min-height 10]
[stretchable-height #f]
[spacing 20]))

(define panelfigCompleto (instantiate vertical-panel% (panelfigura)
[style '(border)]
[min-width 10]
[stretchable-width #f]
[min-height 10]
[stretchable-height #f]))

Ahora para instanciar la imagen en el panel:
(instantiate message% ((make-object bitmap% "imago.jpg") panelfigCompleto ))

Para cajas de texto, tenemos por ejemplo:

(define text0 (instantiate text-field%("Estado Meta: " panel1 )
(callback (lambda (text-field event) ()))
[min-width 10]
[stretchable-width #f]))

Ahora para accesar a la caja de texto, tanto para escribir (que debe estar en String) o para obtener el valor de la caja de texto hacemos respectivamente:
(send text0 set-value "0 1 2 3 4 5 6 7 8")
(send text0 get-value)

En la imagen anterior se visualiza la interfaz, y tambien las sub-imagenes en sus respectivas posiciones del estado inicial generado aleatoriamente.

Definición del 8-puzzle en DrScheme:

Bueno el espacio de estados de un 8-puzzle se encuentra representado así como se muestra en el siguiente gráfico, donde podrá observar que cada estado tiene 4 posibles movimientos a realizar para pasar a otro estado, sin embargo si considera el criterio de no repetir puede obtener menos estados.

Para trabajar en el Problema del 8-puzzle, representamos a cada estado como una lista, por ejemplo usualmente se suele ver como una matriz de 3x3 al 8-puzzle donde tenemos numeros del 0 al 8, nosotros en DrScheme lo hemos trabajado como una lista asi: '(0 1 2 3 4 5 6 7 8), donde este estado viene a ser nuestro estado meta u objetivo.
Ahora sabemos que el numero "0" viene a representar el espacio en blanco el cual es el que se mueve a traves del 8-puzzle hasta hallar la solución, entonces para ello definimos a las posiciones de sus vecinos y movimientos (o acciones) que se pueden tener, dado que el "0" esté en una determinada posición:

(define vecinos '((1 3) (0 2 4) (1 5)
(0 4 6) (1 3 5 7) (2 4 8)
(3 7) (4 6 8) (5 7)))

(define movimientos
list (list 'der 'ab) (list 'izq 'der 'ab) (list 'izq 'ab)
(list 'ar 'der 'ab) (list 'ar 'izq 'der 'ab) (list 'ar 'izq 'ab)
(list 'ar 'der) (list 'ar 'izq 'der) (list 'ar 'izq)))

Es decir, supongamos las posiciones en una matriz de 3x3:
0 1 2
3 4 5
6 7 8

Entonces si el numero "0" se encuentra en la posicion 4 (en el centro), tiene 4 opciones de ir hacia arriba y quedar en la posicion 1, de ir a la izquierda y quedar en la posición 3, de ir a la derecha y quedar en la posición 5 o de ir hacia abajo y quedar en la posición 7.

Para el desarrollo de las búsquedas, tenemos implementado algunas estructura en clases en DrScheme, como una lista: pila, cola; una tabla Hash, que está formada por un vector de listas de nodos; una estructura nodo, donde se encuentra el idNodo, estadoNodo, idPadre, accion, costo, profundidad. Ejemplo veamos la definición de la estructura Nodo en DrScheme:

(define-struct sNodo (idNodo estado idPadre accion costoC profund))
(define crearNodo(lambda(iN est iP acc costC prof)
(make-sNodo iN est iP acc costC prof)))

La de una clase, ejemplo Pila
;Clase Pila
(define pila (class object%
(init lista) ; initialization argument
(define current-lista lista) ; field
(super-new) ; superclass initialization
(define/public (get-lista) current-lista)
(define/public (insertar e)
(cond
((empty? e) current-lista)
((list? e)
(and (insertar (car e)) (insertar (cdr e))))
(else (set! current-lista(cons e current-lista)))
))
(define/public (eliminar)
(set! current-lista (cdr current-lista)))
))

Resolucion mediante Búsqueda en Amplitud:

Escogemos un estado inicial aleatorio, luego seleccionamos busqueda por Amplitud, y se procederá a desarrollar la misma dado el estado inicial, la solución será visualizada en la interfaz asi mismo los movimientos realizados desde las posiciones aleatoria hasta obtener la solución ... :D

Resolución mediante Búsqueda en Profundidad Limitada (donde vemos que no llego a la meta) :

Para este caso es necesario ingresar como un parámetro un límite de busqueda en profundidad, por ende, dado este limite puede ser que llegue a la solución o no, como puede ser visto en la siguiente figura: