Download lección 8. búsquedas con árbol

LECCIÓN 8.
BÚSQUEDAS CON ÁRBOL
En esta lección se presenta una implementación de algoritmos generales de búsqueda en
grafos que emplean árboles de búsqueda. También se analiza la resolución de dos problemas de
búsqueda en espacios de estados.
"Quién a buen árbol se arrima, buena sombra le cobija."
(Refrán castellano)
I.A.I.C. 2002/03
8.1
Dpto. Leng. C. Comp. (U. Málaga)
I.A.I.C. 2002/03
8.2
Dpto. Leng. C. Comp. (U. Málaga)
R.8.1. Búsqueda a ciegas en grafos.
a) Implementar una estructura de datos ARBOL que pueda utilizarse como árbol de búsqueda
para realizar la búsqueda general en grafos a ciegas.
b) Implementar las funciones necesarias para el manejo de la lista abiertos en un algoritmo
general de búsqueda en grafos.
c) Implementar el algoritmo de búsqueda en amplitud mediante una función AMPLITUD que
compruebe la aparición de estados repetidos. Esta función tiene como parámetro necesario el
ESTADO-INIcial de la búsqueda y como parámetros clave:
• FINALP: una función de un argumento (FINALP E) que devuelve T si E es un estado
final, o NIL en otro caso.
• HIJOS: una función de un argumento (HIJOS E) que dado un estado E devuelve una
lista con todos los estados directamente accesibles desde E en el espacio de
búsqueda.
• TRAZA: Una función de un argumento (TRAZA E) que se llama en cada iteración con
el estado expandido, y permite mostrar información de traza; o bien NIL, en cuyo caso
no se muestra información de traza.
• EQ-ESTADO: un predicado de dos argumentos (EQ-ESTADO E1 E2) que devuelve T
si E1 y E2 son el mismo estado, o NIL en otro caso.
AMPLITUD devuelve un camino solución, o bien NIL si no se encontró solución.
SOLUCIÓN:
a) Definimos un árbol como un conjunto de arcos (estado → padre) y un estado raíz cuyo padre es
la constante :maceta. Todo estado del árbol debe tener obligatoriamente un único padre (aunque
no comprobaremos si el padre pertenece ya al árbol).
Existen diversas formas de implementar la búsqueda dependiendo de los requisitos del problema
que se pretenda resolver (vd. Russell & Norvig, 1995). Utilizaremos aquí la más general, en la que
se comprueba la aparición de estados repetidos. Una manera eficiente de implementar este tipo de
búsqueda es utilizando una tabla hash para guardar los arcos. Para cada estado guardaremos en
la tabla su padre. De este modo, podemos comprobar si un estado aparece ya en el árbol en
tiempo casi constante independientemente del tamaño del árbol. Para poder ser utilizados como
claves de una tabla hash, los estados deben ser objetos que puedan compararse con EQ, EQL,
EQUAL ó EQUALP.
Definiremos a continuación los constructores de árboles. El primero recibirá el estado inicial, y la
función de comparación adecuada para los índices de la tabla hash (EQ, EQL, EQUAL, ó
EQUALP), y devolverá un nuevo árbol que contiene únicamente el estado raíz. El segundo será
una operación que recibirá un árbol y modificará destructivamente su contenido, añadiendo un
nuevo arco entre dos estados dados. Nótese que esta segunda operación no devuelve ningún
valor, ya que su interés reside únicamente en el efecto secundario que produce: modificar la
estructura árbol que recibe como primer argumento.
(defun hacer-arbol (e-ini eq-estado)
"devuelve un árbol (tabla hash) con e-ini como raíz(padre :maceta)"
(let ((arbol
(make-hash-table :test eq-estado)))
(setf (gethash e-ini arbol) :maceta)
arbol))
(defun arbol-nuevo-nodo-des (arbol &key estado padre)
"modifica destructivamente el árbol, añadiendo un arco (estado → padre)"
(setf (gethash estado arbol) padre)
(values))
A continuación definiremos aquellas funciones o selectores que nos permiten consultar el árbol.
Concretamente, dado un estado queremos saber: a) cuál es su padre; b) si aparece ya en el árbol.
En realidad ambas funciones son idénticas, ya que podemos deducir si un estado aparece ya en el
I.A.I.C. 2002/03
8.3
Dpto. Leng. C. Comp. (U. Málaga)
árbol simplemente comprobando si tiene padre. También utilizaremos una función para saber si un
estado es o no la raíz del árbol:
(defun arbol-padre-estado (arbol e)
(gethash e arbol))
“padre del estado e en el árbol"
(defun arbol-pertenece-estado-p (arbol e)
(gethash e arbol))
"¿pertenece e al árbol?"
(defun arbol-raiz-p (arbol e)
“¿es e la raíz de árbol?”
(eq :maceta (gethash e arbol)))
Por último definiremos una función que, dados un árbol y un estado e del árbol, nos devuelva el
camino desde e al estado raíz. Nótese que esta función no es dependiente de la implementación
del árbol.
(defun arbol-camino (arbol e &optional l) "camino hasta e en el arbol"
(cond ((arbol-raiz-p arbol e) (cons e l))
(t (arbol-camino arbol
(arbol-padre-estado arbol e)
(cons e l)))))
b) En realidad no es necesario definir funciones para el manejo de una lista ABIERTOS, ya que las
listas y sus operaciones básicas están predefinidas en Lisp. Sin embargo, y por cuestiones
estilísticas, redefiniremos algunas de esas funciones con los nombres comúnmente empleados en
la literatura sobre algoritmos de búsqueda.
(defun abre (abiertos e) (cons e abiertos))
(defun abierto-p (abiertos e) (member e abiertos :test #'equalp))
(defun ultimo (abiertos) (car (last abiertos)))
(defun cierra (abiertos e) (remove e abiertos :test #'equalp))
(defun vacia (abiertos) (null abiertos))
a) Con las definiciones anteriores la tarea es ya muy sencilla.
1. Crear un ARBOL de búsqueda y una lista ABIERTOS que contienen únicamente el estado
inicial.
2. Seleccionar el último elemento e de ABIERTOS (si hay).
3. Si ABIERTOS está vacía, terminar con fracaso.
4. Cerrar e.
5. Si e es un estado final, terminar con el camino desde e hasta la raíz del ARBOL.
6. Expandir el estado e, añadiendo sus sucesores nuevos a ABIERTOS y el ARBOL.
7. Volver a 2.
O lo que es lo mismo, dicho en LISP:
I.A.I.C. 2002/03
8.4
Dpto. Leng. C. Comp. (U. Málaga)
(defun amplitud (estado-ini &key (finalp #'finalp)
(hijos #'hijos)
(eq-estado nil)
(traza nil))
(do* ((arbol
(hacer-arbol estado-ini eq-estado))
(abiertos (abre nil estado-ini))
(e
(ultimo abiertos) (ultimo abiertos)))
((vacia abiertos) NIL)
(when traza (funcall traza e))
(setf abiertos (cierra abiertos e))
(when (funcall finalp e) (return (arbol-camino arbol e)))
(dolist (e2 (funcall hijos e)) ;se expande el estado
(when (not (arbol-pertenece-estado-p arbol e2))
(setf abiertos (abre abiertos e2))
(arbol-nuevo-nodo-des arbol :estado e2 :padre e)))))
Ahora podemos hacer por ejemplo la siguiente llamada:
(AMPLITUD 1 :finalp #'(lambda (n) (> n 10))
:hijos #'(lambda (n) (list (1+ n) (+ 2 n))) :eq-estado #'eql
:traza #'print)
I.A.I.C. 2002/03
8.5
Dpto. Leng. C. Comp. (U. Málaga)
R.8.2. Búsqueda heurística en grafos.
a) Implementar una estructura de datos ARBOL que pueda utilizarse como árbol de búsqueda
para realizar la búsqueda heurística en grafos de tipo A*.
b) Implementar las funciones necesarias para el manejo de la lista abiertos en un algoritmo
general de búsqueda en grafos.
c) Implementar el algoritmo A mediante una función A. Esta función tiene como parámetro
necesario el ESTADO-INIcial de la búsqueda y como parámetros clave:
• FINALP: una función de un argumento (FINALP E) que devuelve T si E es un estado
final, o NIL en otro caso.
• HIJOS: una función de un argumento (HIJOS E) que dado un estado E devuelve una
lista con todos los estados directamente accesibles desde E en el espacio de
búsqueda.
• TRAZA: Una función de un argumento (TRAZA E) que se llama en cada iteración con
el estado expandido, y permite mostrar información de traza; o bien NIL, en cuyo caso
no se muestra información de traza.
• EQ-ESTADO: un predicado de dos argumentos (EQ-ESTADO E1 E2) que devuelve T
si E1 y E2 son el mismo estado, o NIL en otro caso.
• COSTE: una función de dos argumentos (COSTE E1 E2) que devuelve el coste de la
transición E1 → E2.
• H: una función de un argumento (H E) que devuelve una estimación heurística del
coste de una solución que partiendo de E llegue a un estado final.
A devuelve un camino solución y su coste, o bien NIL si no se encontró solución.
**************************
SOLUCION:
a) La solución adoptada será similar a la empleada para implementar la búsqueda en amplitud
(vd. Ejercicio R.8.1). Definimos un árbol como un conjunto de arcos (estado → padre) y un estado
raíz cuyo padre es la constante :maceta. Todo estado del árbol debe tener obligatoriamente un
único padre (aunque no comprobaremos si el padre pertenece ya al árbol).
Utilizaremos nuevamente una tabla hash para guardar los arcos. Sin embargo ahora debemos
guardar para cada estado, además a su padre, la información de coste que permite la búsqueda
heurística. Concretamente guardaremos junto a cada estado: su padre; el coste del camino en el
árbol desde la raíz hasta el estado (g); la estimación del coste de un camino solución que pase por
el estado (f). Recogeremos toda esta información en una estructura de tipo NODO, y guardaremos
los nodos en la tabla hash indexados por su estado:
(defstruct nodo (padre
(g
(f
nil)
nil)
nil))
Definiremos a continuación los constructores de árboles.
• El primero recibirá el estado inicial, y la función de comparación adecuada para los
índices de la tabla hash (EQ, EQL, EQUAL, ó EQUALP), y devolverá un nuevo árbol que
contiene únicamente el estado raíz. Su coste (g) será cero. El valor de su estimación es
indiferente.
• El segundo será una operación que recibirá un árbol y modificará destructivamente su
contenido, añadiendo un nuevo arco entre dos estados dados. Dicha función también
recibirá los valores g y h.
• Por último, necesitamos una operación que permita cambiar el padre de un estado. En
efecto, en A* es importante guardar para cada estado el camino más corto de entre los
encontrados hasta el momento. Al cambiar el padre, lógicamente, cambiará también el
coste del camino y su estimación.
I.A.I.C. 2002/03
8.6
Dpto. Leng. C. Comp. (U. Málaga)
(defun hacer-arbol (e-ini eq-estado)
"devuelve un arbol (tabla hash ) con e-ini como raiz(padre :maceta)"
(let ((arbol
(make-hash-table :test eq-estado)))
(setf (gethash e-ini arbol) (make-nodo :padre :maceta
:g
0
:f
0))
arbol))
(defun arbol-nuevo-nodo-des (arbol &key estado padre g h)
"modifica destructivamente el arbol, añadiendo un arco estado → padre"
(setf (gethash estado arbol) (make-nodo :padre padre
:g
g
:f
(+ g h)))
(values))
(defun arbol-cambia-padre-des (arbol e nuevo-p nuevo-g h)
"modifica destructivamente el arbol, el nuevo padre de e será nuevo-p con
coste nuevo-g"
(let ((n (gethash e arbol)))
(setf (nodo-padre n) nuevo-p
(nodo-g
n) nuevo-g
(nodo-f
n) (+ nuevo-g h))
(values)))
A los selectores vistos en R.8.1.a debemos añadir aquellas funciones que permiten consultar los
valores de g y f de un estado. Nótese que ahora estos valores y el padre se encuentran guardados
en una estructura tipo NODO.:
(defun arbol-g-estado (arbol e)
(nodo-g (gethash e arbol)))
"coste hasta e en el arbol"
(defun arbol-f-estado (arbol e)
"estimación de coste de una solucion pasando por e"
(nodo-f (gethash e arbol)))
(defun arbol-padre-estado (arbol e)
(nodo-padre (gethash e arbol)))
"padre del estado e en el arbol"
(defun arbol-pertenece-estado-p (arbol e)
(gethash e arbol))
"¿pertenece e al arbol?"
(defun arbol-raiz-p (arbol e)
"¿es e la raíz de árbol?"
(eq :maceta (nodo-padre (gethash e arbol))))
Por último, necesitaremos una función que, dados un árbol y un estado, nos devuelva el camino
desde la raíz del árbol al estado. Nótese que la implementación del árbol para A* es distinta de la
vista en R.8.1.a. Sin embargo esta función es idéntica, ya que es independiente de la
implementación:
(defun arbol-camino (arbol e &optional l) "camino hasta e en el arbol"
(cond ((arbol-raiz-p arbol e) (cons e l))
(t (arbol-camino arbol
(arbol-padre-estado arbol e)
(cons e l)))))
b) Por cuestiones estilísticas, realizaremos las mismas definiciones que en R.8.1.b. Además,
necesitamos ahora una función que nos devuelva el mejor estado de ABIERTOS, es decir, aquél
I.A.I.C. 2002/03
8.7
Dpto. Leng. C. Comp. (U. Málaga)
que tenga menor valor de f(n). Puesto que los valores de f(n) están guardados en el árbol, la
función (mejor abiertos arbol) recibirá ambos argumentos. Optaremos aquí por una
definición sencilla, aunque poco eficiente, de mejor.
(defun abre (abiertos e) (cons e abiertos))
(defun abierto-p (abiertos e) (member e abiertos :test #'equalp))
(defun cierra (abiertos e) (remove e abiertos :test #'equalp))
(defun vacia (abiertos) (null abiertos))
(defun mejor (abiertos arbol)
(infimo abiertos
#'(lambda (e1 e2) (< (arbol-f-estado arbol e1)
(arbol-f-estado arbol e2)))))
;;Recuérdese la definición de INFIMO:
(defun infimo (l pred &optional ac)
(cond ((null l) ac)
((null ac) (infimo (cdr l) pred (car l)))
(t (infimo (cdr l) pred (mi-min ac (car l) pred)))))
(defun mi-min (x y pred)
(if (funcall pred x y) x y))
c) Con las definiciones anteriores la tarea es ya muy sencilla, aunque no tanto como en R.8.1.c,
principalmente debido a que ahora es necesario reconsiderar aquellos sucesores de un estado que
ya pertenezcan al árbol.
1. Crear un ARBOL de búsqueda y una lista ABIERTOS que contienen únicamente el estado
inicial.
2. Seleccionar el elemento e de ABIERTOS con menor valor de f(n) (si hay).
3. Si ABIERTOS está vacía, terminar con fracaso.
4. Cerrar e.
5. Si e es un estado final, terminar con el camino desde e hasta la raíz del ARBOL.
6. Para cada sucesor e2 de e en el grafo,
a. Si e2 ya pertenece al ARBOL, entonces,
i. Calcular el coste del nuevo camino hasta e2.
ii. Si el coste del nuevo camino es menor, redirigir el puntero de e2 a e.
iii. Si se cambió el puntero y e2 está cerrado, volver a abrirlo.
en otro caso,
i. Establecer e2 como sucesor de e en el ARBOL.
7. Volver a 2.
I.A.I.C. 2002/03
8.8
Dpto. Leng. C. Comp. (U. Málaga)
(defun a (estado-ini &key (finalp #'finalp)
(coste #'coste)
(eq-estado nil)
(do* ((arbol
(hacer-arbol estado-ini
(abiertos (abre nil estado-ini))
(e
(mejor abiertos arbol)
((vacia abiertos) NIL)
(hijos #'hijos)
(h
#'h)
(traza nil))
eq-estado))
(mejor abiertos arbol)))
(when traza (funcall traza e))
(setf abiertos (cierra abiertos e))
(when (funcall finalp e) (return (arbol-camino arbol e)))
(dolist (e2 (funcall hijos e))
;se expande el estado
(let ((coste-nuevo (+ (arbol-g-estado arbol e)
(funcall coste e e2)))
(h-e2
(funcall h e2)))
(cond ((arbol-pertenece-estado-p arbol e2)
(when (< coste-nuevo (arbol-g-estado arbol e2))
(arbol-cambia-padre-des arbol e2 e coste-nuevo h-e2)
(when (not (abierto-p abiertos e2))
(setf abiertos (abre abiertos e2)))))
(t
(setf abiertos (abre abiertos e2))
(arbol-nuevo-nodo-des arbol
:estado e2
:padre e
:g
coste-nuevo
:h
h-e2)))))))
La principal diferencia con AMPLITUD aparece en la expansión de estados, que ahora es más
complicada. En efecto, en el caso en que el estado ya exista (esté abierto o cerrado), hay que
considerar si es mejor conservar su antiguo padre o cambiarlo; además, si el nodo estaba ya
cerrado y hemos decidido cambiar su padre, será necesario reabrirlo.
Ahora podemos hacer por ejemplo la siguiente llamada:
(a 1 :FINALP #'(lambda (n) (> n 10))
:HIJOS #'(lambda (n) (list (1+ n) (+ 2 n)))
:COSTE #'(lambda (n m) (+ n m))
:h #'(lambda (n) 0)
:EQ-ESTADO #'eql
:TRAZA #'print)
I.A.I.C. 2002/03
8.9
Dpto. Leng. C. Comp. (U. Málaga)
R.8.3. Considérese el juego del “disco del loco”. Se trata de cuatro anillos concéntricos, en
cada uno de los cuales hay escritos ocho números. El disco central es fijo; los demás pueden
moverse alrededor de él mediante giros de 45º tanto en el sentido de las agujas del reloj como
en el contrario. El objetivo del juego es conseguir que, para todos los radios la suma de los
cuatro números alineados valga 12.
Se pide:
a) Diseñar un formalismo para representar en LISP los posibles estados del problema
utilizando listas.
b) Diseñar un formalismo para representar en LISP el espacio de estados correspondiente
(funciones FINALP, HIJOS, EQ-ESTADO).
c) Aplicar el algoritmo de búsqueda en amplitud para hallar una sucesión de movimientos que
lleve al estado final partiendo de la configuración indicada a continuación.
ε
**************************
SOLUCION:
a) Representaremos el estado mediante una lista de listas. Cada sublista contendrá los valores
correspondientes a los radios. El selector (num-anillos e) devuelve el número de anillos de
un disco e.
(defun hacer-estado (&rest
(defun num-anillos (d)
(defun estado-ini ()
disco) disco) ;servirá cualquier constructor
;de listas
(length d))
(hacer-estado '(2
'(2
'(1
'(3
2
1
3
2
5
3
2
3
1
4
1
4
5
5
3
3
3
3
4
3
4
3
2
4
3)
2)
5)
5)))
b) La función de comparación de estados será simplemente EQUAL. En cuanto a la función
FINALP debe comprobar que la suma de los radios sea siempre 12:
(defun finalp (d)
(dolist (n (apply #'mapcar (cons #'+ d)) t)
(unless (= n 12)
(return nil))))
I.A.I.C. 2002/03
8.10
Dpto. Leng. C. Comp. (U. Málaga)
Los hijos de un estado dado son los resultantes de rotar cada uno de los anillos a derecha e
izquierda:
(defun hijos (d)
(let ((lhijos nil))
(dotimes (a (num-anillos d) lhijos)
(push (disco-rotar-derecha
a d) lhijos)
(push (disco-rotar-izquierda a d) lhijos))))
Las funciones (disco-rotar-derecha a d) y (disco-rotar-izquierda a d) devuelven
un disco igual que d tras rotar a derecha e izquierda respectivamente el anillo a. El disco más
interior es el cero.
(defun disco-rotar-derecha (a d)
(cond ((zerop a)(cons (anillo-rotar-> (car d)) (cdr d)))
(t
(cons (car d) (disco-rotar-derecha (1- a) (cdr d))))))
(defun disco-rotar-izquierda (a d)
(cond ((zerop a)(cons (anillo-rotar<- (car d)) (cdr d)))
(t
(cons (car d) (disco-rotar-izquierda (1- a) (cdr d))))))
Las funciones (anillo-rotar-> a) y (anillo-rotar<- a) son las encargadas de rotar un
anillo a derecha e izquierda respectivamente:
(defun anillo-rotar-> (a) (append (last a) (butlast a)))
(defun anillo-rotar<- (a) (append (cdr a) (list (car a))))
c) La llamada a la función amplitud sería:
(amplitud (estado-ini) :eq-estado #’equal)
Con la ayuda de las siguientes funciones puede mostrarse el resultado por pantalla de forma más
cómoda:
(defun ver-disco (d)
"Muestra un anillo en cada linea, comenzando por el más profundo"
(format t "~%-------------------")
(dolist (a d)
(print a)))
(defun disco-loco ()
(dolist (e (amplitud (estado-ini) :eq-estado #'equal))
(ver-disco e)))
I.A.I.C. 2002/03
8.11
Dpto. Leng. C. Comp. (U. Málaga)
R.8.4. Considérese el problema del puzzle-8, consistente en un tablero 3 x 3 que contiene 8 fichas
y una casilla vacía.
2 8 3
1 6 4
7 5
Las fichas pueden desplazarse horizontal o verticalmente a la posición adyacente siempre que
esta sea la casilla vacía. El objetivo del puzzle es, dada una configuración inicial, llegar a
través de una secuencia de movimientos válidos hasta otra configuración dada. Por ejemplo:
1 2 3
8
4
7 6 5
Se pide:
a) Diseñar un formalismo para representar en LISP los posibles estados del problema
utilizando arrays.
b) Diseñar un formalismo para representar en LISP el espacio de estados correspondiente
(funciones FINALP, HIJOS, EQ-ESTADO).
c) Aplicar el algoritmo de búsqueda A* para hallar una sucesión de movimientos que lleve al
estado final partiendo de la configuración indicada más arriba.
**************************
SOLUCION:
a) Representaremos cada tablero mediante un array 3x3. El estado vendrá representado por una
estructura con las coordenadas de la posición vacía (fila y columna), y el tablero
correspondiente. El constructor básico y los selectores serán los siguientes:
(defvar *nfil*)
(setq *nfil* 3)
(defvar *ncol*)
(setq *ncol* 3)
;número de filas del tablero
;número de columnas del tablero
(defstruct estado
pv-fil
pv-col
tablero)
“Estado del puzzle-8”
;fila de la posición vacía
;columna de la posición vacía
;array con el contenido del tablero
De este modo podemos representar fácilmente los estados inicial y final:
(defvar *estado-ini*)
(setq *estado-ini* (make-estado :pv-fil 2 :pv-col 1
:tablero (make-array (list *nfil* *ncol*)
:initial-contents '((2 8 3)
(1 6 4)
(7 _ 5)))))
(defvar *efinal*)
(setq *efinal* (make-estado :pv-fil 1 :pv-col 1
:tablero (make-array (list *nfil* *ncol*)
:initial-contents '((1 2 3)
(8 _ 4)
(7 6 5)))))
b) La función de comparación de estados (EQ-ESTADO) será simplemente la función EQUALP.
Comencemos con la función FINALP, que devolverá T si un estado coincide con la configuración
final.
(defun finalp (e)
I.A.I.C. 2002/03
(equalp e *efinal*))
8.12
Dpto. Leng. C. Comp. (U. Málaga)
Consideremos ahora la función HIJOS. En principio hay cuatro movimientos posibles desde un
estado E dado. Sea (F, C) la posición de la casilla vacía:
• permutar (F, C) con (F+1, C) (si (F+1, C) pertenece al tablero),
• permutar (F, C) con (F-1, C) (si (F-1, C) pertenece al tablero),
• permutar (F, C) con (F, C+1) (si (F, C+1) pertenece al tablero),
• permutar (F, C) con (F, C-1) (si (F, C-1) pertenece al tablero),
(defun hijos (e)
(let ((fv
(estado-pv-fil e))
(cv
(estado-pv-col e))
(tab (estado-tablero e)))
(remove-if #'null
(list
(estado-permuta fv
(estado-permuta fv
(estado-permuta fv
(estado-permuta fv
cv
cv
cv
cv
fv (1+ cv)
fv (1- cv)
(1+ fv) cv
(1- fv) cv
tab)
tab)
tab)
tab)))))
Necesitaremos un nuevo constructor de estados (estado-permuta fv cv f2 c2 tab), que
reciba las coordenadas de la posición vacía (fv, cv), las nuevas coordenadas (f2, c2), y un
tablero tab, y devuelva un nuevo estado con el tablero resultante de permutar los contenidos de
las posiciones (fv, cv), y (f2,c2). Si la posición (f2,c2) no pertenece al tablero, el
resultado será NIL:
(defun estado-permuta (fv cv f2 c2 tab)
(when (posicion-valida? f2 c2)
(make-estado :pv-fil f2
:pv-col c2
:tablero (permuta-tablero fv cv f2 c2 tab))))
(defun posicion-valida? (f c)
(and (<= 0 f (1- *nfil*)) (<= 0 c (1- *ncol*))))
La función (permuta-tablero fv cv f2 c2 tab) devuelve una copia del tablero tab con
el contenido de las posiciones (fv,cv) y (f2,c2) intercambiado.
(defun permuta-tablero (fv cv f2 c2 tab)
(let* ((tab2 (copiar-tablero tab)))
(setf (aref tab2 fv cv) (aref tab f2 c2)
(aref tab2 f2 c2) (aref tab fv cv))
tab2))
(defun copiar-tablero (tab)
"Devuelve una copia del tablero tab"
(let ((tab2 (make-array (list *nfil* *ncol*))))
(dotimes (f *nfil* tab2)
(dotimes (c *ncol*)
(setf (aref tab2 f c) (aref tab f c))))))
c) La siguiente función muestra ordenadamente por pantalla un estado:
(defun ver-estado (e)
(let ((tab (estado-tablero e)))
(dotimes (f *nfil*)
(dotimes (c *ncol*)
(princ (aref tab f c)))
(terpri))
(terpri)))
I.A.I.C. 2002/03
8.13
Dpto. Leng. C. Comp. (U. Málaga)
De modo que puede verse el resultado con ayuda de la siguiente función:
(defun puzzle-8 ()
(dolist (e (a *estado-ini* :eq-estado #'equalp
:coste #’(lambda (n1 n2) 1)
:h
#’(lambda (n) 0)))
(ver-estado e)))
I.A.I.C. 2002/03
8.14
Dpto. Leng. C. Comp. (U. Málaga)
EJERCICIOS PROPUESTOS.
P.8.1. Implementar versiones de los algoritmo de búsqueda AMPLITUD y A (presentados en R.8.1
y R.8.2 respectivamente) que proporcionen información estadística acerca de la búsqueda.
Concretamente, el algoritmo debe calcular y escribir cuando finalice su ejecución:
a) el número total T de nodos generados
b) el número total de nodos expandidos
c) el número máximo de nodos presentes en ABIERTOS en un paso del algoritmo
d) el factor B de ramificación efectivo de la exploración, dado por la ecuación implícita
(BL – 1) B
----------- = T
B – 1
Donde L es la longitud del camino solución hallado.
P.8.2. Construir instancias del juego del disco del loco en las que la solución se encuentre a
distintas profundidades (número de movimientos). Resolverlas empleando el algoritmo de
búsqueda en amplitud desarrollado en P.8.1, y elaborar una gráfica para el número de iteraciones
realizadas, el número de nodos generados, y el tiempo empleado en función de la profundidad de
la solución.
P.8.3. Diseñar e implementar una función (FINALP E) para el juego del disco del loco y que sea
más eficiente que la presentada en R.8.3. Concretamente, el valor de las sumas de los radios
debe calcularse secuencialmente, y la función debe devolver NIL tan pronto como uno de ellos
sume un valor distinto de 12.
P.8.4. a) Diseñar e implementar una función heurística admisible e informada para el problema
del puzzle-8.
b) Construir instancias del puzzle-8 en las que la solución se encuentre a distintas profundidades
(número de movimientos). Resolverlas empleando el algoritmo de búsqueda heurística
desarrollado en P.8.1 y la función heurística del apartado (a), y elaborar una gráfica para el
número de iteraciones realizadas, el número de nodos generados, y el tiempo empleado en
función de la profundidad de la solución.
c) Ídem para el heurístico ∀n h(n) = 0.
P.8.5. Considérese el siguiente solitario. Se dispone de un tablero de ajedrez de N × N y de un
caballo situado en la posición (1, 1). Se trata de encontrar, si es que existe, una secuencia de
movimientos del caballo tal que éste pase por todas y cada una de las posiciones del tablero sin
pasar dos veces por la misma.
a) Definir mediante arrays un tipo de datos ‘tablero’, capaz de procesar los siguientes mensajes:
! MARCAR-POSICION x y que marca en cualquier caso como visitada la posición (x, y)
! MARCADOP x y que devuelve T en caso de que la posición (x, y) esté marcada en el
tablero, y NIL en otro caso.
b) Definir un tipo de datos adecuado para representar los estados del problema. Proporcionar las
funciones HIJOS, FINALP y una función de traza adecuadas para resolver el problema
mediante el algoritmo de búsqueda en amplitud presentado en R.8.1.
P.8.6. Un viajero lleva consigo un lobo, una cabra y una inmensa col. El viajero llega a un río que
debe atravesar. Dispone para ello de una barca, pero en la barca solamente cabe –además de él,
que debe tripularla- uno de sus animales u objetos. Por otra parte, si el lobo y la cabra están juntos
y el viajero no está con ellos, el lobo se comerá a la cabra; y análogamente ocurrirá con la cabra y
la col. El viajero desea planificar sus travesías en la barca de forma que pasen íntegras todas sus
pertenencias. Resolver este problema reduciéndolo a una búsqueda en espacio de estados. Para
ello se pide:
• Describir en lenguaje natural cómo se va a representar cada estado de este problema en
LISP.
• Implementar las funciones FINALP e HIJOS para esta representación, así como una función
de traza adecuada.
• Aplicar un algoritmo de búsqueda en amplitud para resolver el problema.
I.A.I.C. 2002/03
8.15
Dpto. Leng. C. Comp. (U. Málaga)
P.8.7. Implementar una función PROFUN con los mismos parámetros que AMPLITUD, pero que
realice la búsqueda en profundidad.
P.8.8. Implementar una función PROFUN-L que realice de forma eficiente la búsqueda en
profundidad con límite de profundidad. Para ello se guardará para cada estado su profundidad en
el árbol. Dicha función tendrá los mismos parámetros que PROFUN, y además uno nuevo LIMITEPROF. El comportamiento será el siguiente:
• Si LIMITE-PROF es NIL, se realizará la búsqueda sin límite de profundidad (como en
PROFUN).
• Si LIMITE-PROF es un entero no negativo, se realizará la búsqueda con límite de
profundidad, de modo que no se generarán los sucesores de aquellos estados cuya
profundidad coincida con el límite.
P.8.9. La implementación del algoritmo A* presentada en R.8.2 utiliza una lista ABIERTOS muy
ineficiente. Determinar el mejor elemento de ABIERTOS es una tarea cuya complejidad crece
proporcionalmente con el tamaño de la lista, que puede llegar a ser muy grande. Una alternativa
más eficiente es emplear una estructura del tipo “montón binario” para implementar ABIERTOS.
Un montón binario es un árbol binario cuyos nodos almacenan determinados valores de modo que
se cumpla siempre la siguiente condición:
"En cada nodo, el valor guardado es menor o igual que los valores guardados
en cada uno de sus hijos"
El árbol se construye balanceado en amplitud de la siguiente forma:
• Los nuevos elementos se insertan en la última posición libre del árbol, y se hacen subir
hasta su posición correcta intercambiándolos recursívamente con su padre hasta que este
sea menor, o bien se llegue a la raíz.
• El menor elemento del árbol se encuentra siempre en la raíz. Para borrarlo y mantener el
árbol balanceado, se borra también el último elemento, se coloca en la raíz, y se le hace
descender recursívamente intercambiándolo con el menor de sus hijos hasta que ambos
sean mayores, o llegue a ser una hoja del árbol.
De este modo, el tiempo empleado tanto para la inserción como el borrado de elementos es
logarítmico con el número de ellos en el peor caso.
Implementar la lista ABIERTOS y sus operaciones utilizando un montón binario.
NOTA: El árbol puede implementarse eficientemente mediante una tabla hash, indexada con
números naturales (1,2,...). La raíz se almacenará en la posición 1. Para cada elemento indexado
en k, sus dos hijos están indexados como 2k, 2k+1. En consecuencia, el elemento con índice k
tiene su padre en la posición (k div-entera 2).
P.8.10. Implementar una versión del algoritmo de búsqueda heurística A que incorpore una
estrategia de limitación de sucesores. La nueva función A-LIMITADO tendrá un nuevo
parámetro MAX-SUCESORES y la función EXPANDE se comportará de la siguiente forma:
! Si MAX-SUCESORES es NIL (por defecto), se comportará igual que el algoritmo A.
! Si MAX-SUCESORES es un entero positivo, entonces cuando se expande un nodo el
algoritmo nunca considera más de MAX-SUCESORES sucesores del mismo, quedándose
siempre con los de mejor valor de f(n). Por ejemplo, si MAX-SUCESORES es 4, el algoritmo
solo considerará para cada nodo los 4 sucesores más prometedores del mismo.
____________________________________________________________________________________
Las erratas y comentarios sobre estos apuntes son bienvenidos en: [email protected]
I.A.I.C. 2002/03
8.16
Dpto. Leng. C. Comp. (U. Málaga)