• Author / Uploaded
• Nilas Arcanister

Citation preview

; 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 (cond ((= nodo 1) ((= nodo 2) ((= nodo 3) ((= nodo 4) ((= nodo 5) ((= nodo 6) ((= nodo 7) ((= nodo 8) ((= nodo 9) (t nil) ) )

(nodo) (list (list (list (list (list (list (list (list (list

5 6 6 8 9 9 8 9 8

4 5 5 7 8 8 5 7 6

2)) 4 3 2)) 5 2 7 6 5 3 4)) 6 5 5))

1))

1)) 4 3 2 1)) 2)) 4))

(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) )

(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)