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)