Aplicaciones de algoritmos de búsqueda

CURSO : Programación No Procedural

TEMA : Aplicaciones de Algoritmos de Búsqueda

INDICE

Implementación de Algoritmos en Lisp
Búsqueda en profundidad 3
Búsqueda en achura 5Ramificación y acotación 7

Aplicaciones
De Objetivos 9
De Anchura 11
De Ramificación y Acotación 12

Bibliografía 14


Aplicaciones de Algoritmos deBúsqueda

I. Algoritmos

1. Búsqueda en profundidad

;---- Esta función es la central de la búsqueda por profundidad. Se ----
;---- le entrega dos puntos y el grafo. La función verifica si hay----
:---- una ruta entre los dos puntos y entrega esta ruta ----

(defun profundidad (ptoini ptofin grafo)
(let (cola nil visitados nil inver nil auxil nil)
(setf auxilgrafo)
(setf cola (list ptoini))
(loop
(when (equal (first cola) ptofin) (return 'Si hay ruta))
(when (null grafo) (return 'No hay ruta))
;------Para poder buscar en grafo los puntos ------
;------ que siguen al primer elemento de Cola ------
;------ primero se eliminan todos los primeros ------;------ elementos de Grafo para poder como ------
;------ primero el primer elemento de Cola y ------
;------ asi pueda luego tomar todos los puntos ------;------ que siguen a ese elemento ------
(loop
(setf sies (first (first grafo)))
(when (equal sies (first cola)) (return nil))(when (null grafo) (return nil))
(pop grafo)
)
;------ Se toma el primer elemento de Cola y se ------
;------ buscan todos los puntos quesiguen a ese------
;------ elemento para incluirlos en la lista ------
;------ cola. Antes de incluirlo en cola primero------
;------ se añade en Visitados...