8/17/2019 Busqueda Por Anchura y Profundidad en Lisp
1/2
; Algoritmos de busqueda por anchura y profundidad
; Copyrigth 2010 Luis Espino; Todos los derechos reservados.
; Problema: Matriz de posiciones
; Regla de sucesores: todo nodo alrededor; 1 2 3
; 4 5 6; 7 8 9
; la siguiente expresión sirve para leer el archivo desde consola; (load 'busqueda.lisp)
(defun sucesores (nodo)
(cond ((= nodo 1) (list 5 4 2))
((= nodo 2) (list 6 5 4 3 1)) ((= nodo 3) (list 6 5 2))
((= nodo 4) (list 8 7 5 2 1)) ((= nodo 5) (list 9 8 7 6 4 3 2 1))
((= nodo 6) (list 9 8 5 3 2)) ((= nodo 7) (list 8 5 4)) ((= nodo 8) (list 9 7 6 5 4))
((= nodo 9) (list 8 6 5)) (t nil)
))
(defun busqueda-anchura (nodo-inicio nodo-fin)
(print 'BUSQUEDA-ANCHURA) (setq lista (list nodo-inicio))
(loop until (null lista) do (setq nodo-actual (car lista))
(print nodo-actual) (setq lista (cdr lista))
(if (= nodo-actual nodo-fin)(return-from busqueda-anchura (print 'SOLUCION)))
(setq temp (sucesores nodo-actual))
;(setq temp (reverse temp)) ; intercambiar orden (print temp)
(if (not (null temp)) (setq lista (append lista temp))
) )
(print 'NO-SOLUCION))
8/17/2019 Busqueda Por Anchura y Profundidad en Lisp
2/2
(defun busqueda-profundidad (nodo-inicio nodo-fin) (print 'BUSQUEDA-PROFUNDIDAD)
(setq lista (list nodo-inicio)) (loop until (null lista) do
(setq nodo-actual (car lista))(print nodo-actual)
(setq lista (cdr lista)) (if (= nodo-actual nodo-fin)
(return-from busqueda-profundidad (print 'SOLUCION)))
(setq temp (sucesores nodo-actual)) ;(setq temp (reverse temp)) ; intercambiar orden
(print temp) (if (not (null temp))
(setq lista (append temp lista)) )
) (print 'NO-SOLUCION)
)
(busqueda-anchura 1 9)
(format t "~%")
(busqueda-profundidad 1 9)