algoritmos de busqueda

ALGORITMOS DE BÚSQUEDA
Ing. Ronald A. Rentería Ayquipa

Algoritmos de Búsqueda Tipos

Tipos de algoritmos de búsqueda



ALGORITMOS DE BÚSQUEDA NO INFORMADA
ALGORITMOS DE BÚSQUEDA HEURÍSTICA

Inteligencia Artificial Ing. Ronald A. Rentería Ayquipa

Búsqueda no informada Introducción

Búsqueda no informada








Conocidos como algoritmos de búsqueda ciega
Nodependen de la información del problema
Son generales (aplicables a cualquier problema)
Algoritmos exhaustivos (pueden llegar a recorrer todo el
árbol para llegar a una solución)
Aplicables a problemas pequeños
Políticas de recorrido:



En anchura  (Anchura prioritaria)
En profundidad  (Profundidad prioritaria, Profundidad iterativa)

Inteligencia Artificial Ing. Ronald A. RenteríaAyquipa

Búsqueda no informada Búsqueda en anchura prioritaria

Búsqueda en Anchura Prioritaria






Los nodos se visitan y generan por niveles
La estructura para los nodos abiertos es una cola (FIFO)
Un nodo es visitado cuando todos los nodos de los
niveles superiores y sus hermanos precedentes han sido
visitados
Características:





Completitud: El algoritmosiempre encuentra una solución
Complejidad temporal: Exponencial respecto al factor de
ramificación y la profundidad de la solución O(rp)
Complejidad espacial: Exponencial respecto al factor de
ramificación y la profundidad de la solución O(rp)
Optimalidad: La solución que se encuentra es óptima en
número de niveles desde la raíz
Inteligencia Artificial Ing. Ronald A. Rentería AyquipaBúsqueda no informada Búsqueda en profundidad prioritaria

Búsqueda en Profundidad Prioritaria







Los nodos se visitan y generan buscando los nodos a mayor
profundidad y retrocediendo cuando no se encuentran nodos
sucesores
La estructura para los nodos abiertos es una pila (LIFO)
Para garantizar que el algoritmo acaba (caminos infinitos) debe
imponerse un límite en la profundidadde exploración (profundidad
limitada)
Características






Completitud: El algoritmo encuentra una solución si se impone un límite
de profundidad y existe una solución dentro de ese límite
Complejidad temporal: Exponencial respecto al factor de ramificación y
la profundidad del límite de exploración O(rp)
Complejidad espacial: En el caso de no controlar los nodos repetidos elcoste es lineal respecto al factor de ramificación y el límite de
profundidad O(rp). Si tratamos repetidos el coste es igual que en anchura. Si
la implementación es recursiva el coste es O(p)
Optimalidad: No se garantiza que la solución sea óptima
Inteligencia Artificial Ing. Ronald A. Rentería Ayquipa

Búsqueda no informada Búsqueda en profundidad limitada

Búsqueda en ProfundidadLimitada






La estructura de abiertos es ahora una pila
Se dejan de generar sucesores cuando se llega al límite de profundidad
Esta modificación garantiza que el algoritmo acaba pero no una solución
Si tratamos repetidos el ahorro en espacio es nulo
Inteligencia Artificial Ing. Ronald A. Rentería Ayquipa

Búsqueda no informada Tratamiento repetidos

Tratamiento de nodos repetidos

En anchura




Si el repetido está en la estructura de nodos cerrados podemos
descartarlo. Tendrá una profundidad igual o mayor al repetido
cerrado (por tanto un costo igual o mayor)
Si el repetido está en la estructura de nodos abiertos podemos
descartarlo. Tendrá una profundidad igual o mayor al repetido abierto
(por tanto un costo igual o mayor)

Inteligencia Artificial Ing.Ronald A. Rentería Ayquipa

Búsqueda no informada Tratamiento repetidos

Tratamiento de nodos repetidos


En profundidad




Si el repetido está en la estructura de nodos cerrados lo dejaremos,
si tiene una profundidad menor
Si el repetido está en la estructura de nodos abiertos podemos
olvidarlo, seguro que tiene una profundidad mayor

Inteligencia Artificial Ing. Ronald...