BÚSQUEDA NO INFORMADA

Fecha de Clase: 4 - 8 de Mayo 2015

INTRODUCCIÓN

En esta clase se estudió los algoritmos de búsquedas no informadas o también conocidas como búsquedas a ciegas, el estudio de esta búsqueda es indispensable puesto que se han desarrollados diferentes tipos de estrategias que son aplicados según el problema.

Las estrategias de las  búsquedas no informadas han sido de gran ayuda para darle solución a diferentes tipos de problemas, estas son utilizadas de  acuerdo a  la búsqueda que se realice, siendo de mucha utilidad en este proceso.

OBJETIVO

Identificar las búsquedas no informada y conocer sus diferentes estrategias.

MARCO TEÓRICO

BÚSQUEDA NO INFORMADA

Las búsquedas no informadas son aquellas, son aquellas que no poseen información extra simplemente cuenta con la definición del problema, estas búsquedas solo pueden generar sucesores y distinguir entre un estado objetivo de uno que no lo es. La búsqueda no informada presenta seis estrategias de búsquedas:

                  

En este documento se hablara de la búsqueda primero en anchura y la búsqueda primero en profundidad ya que de estas dos estrategias de búsquedas son la base para el desarrollo de las demás estrategias búsquedas.

CRITERIOS DE EVALUACIÓN DE LAS ESTRATEGIAS: »Completitud: llegar al  objetivo o encontrar la solución.

»Optimización: encontrar la solución más óptima.

»Complejidad espacial: cuanto espacio de memoria necesita

»Complejidad temporal: el tiempo necesario para realizar la búsqueda.

LAS COMPLEJIDADES TEMPORAL Y ESPACIAL SE MIDEN EN TÉRMINOS DE:

b -> factor de ramificación ->  Es el máximo número de sucesores de cualquier nodo dentro del árbol de búsqueda

m ->longitud máxima del árbol de búsqueda -> es la longitud de cualquier camino en el espacio de estados

d -> profundidad de la mejor solución -> es la profundidad del nodo objetivo más superficial de menor coste.

BÚSQUEDA PRIMERO EN ANCHURA

Esta estrategia de búsqueda es completa y óptima. Según Russell y Norvig la búsqueda primero en anchura: “Es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc. En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel”.

Utiliza la estructura FIFO, puesto que esta estrategia siempre expande primero el nodo más antiguo, es decir el menos profundo.

ESTRATEGIA:

•     La búsqueda en el árbol  se realiza por niveles de profundidad
•    En la búsqueda primero en anchura expande todos los nodos de nivel n, antes de expandir nodos de nivel n+1. Figura 1

Figura1. Esquema de la búsqueda primero en anchura

CARACTERÍSTICAS

• Completitud: Esta estrategia siempre llaga al estado objetivo
• Optimización: esta búsqueda es óptima según el número de niveles que tenga desde la raíz hasta encontrar la solución.
• Complejidad espacial: involucra a la exponencial del factor ramificación y la profundidad en la que se halle la solución.
• Complejidad temporal: este depende de la profundidad en la que se encuentre la solución y al factor ramificación.

EJEMPLO DE  LA BUSQUEDA PRIMERO EN ANCHURA

Realizar una búsqueda primero en anchura donde el estado inicial es A y el estado objetivo es N

Recorrido de A:N = {A,B,C,D,E,F,G,H,I,J,K,L,M,N}

BÚSQUEDA PRIMERO EN PROFUNDIDAD

Esta estrategia de búsqueda siempre se comienza a expandir por el nodo más profundo y dando comienzo por el la do izquierdo en el árbol de búsqueda. Una vez que se hayan expandido todos los nodos, es decir cuando los nodos ya no posean ningún sucesor, se retrocede al nodo más superficial que tenga sucesores que no hayan sido expandidos.

La búsqueda en profundidad no es la más óptima,  ni el más completo, puesto que en muchas ocasiones no puede acabar la búsqueda o elije el peor camino. Utiliza una cola LIFO primero en entrar último en salir en la frontera de la búsqueda, este algoritmo maneja sencillos requisitos en la memoria, ya que almacena el camino del nodo raíz al nodo hoja, incluyendo a los nodos hermanos que no han sido expandidos.

Estrategia:

•  La búsqueda en el árbol  se realiza por el nodo más profundo (comenzando por el lado izquierdo del árbol)
•   Retrocede cuando no encuentra nodos sucesores. Figura 2

Figura 2. Esquema de la busqueda primero en profundidad

CARACTERÍSTICAS

• Completitud: esta estrategia encuentra la solución, pero muchas veces es necesario poner un límite.
• Optimización: la solución no siempre es la más óptima.
• Complejidad temporal: depende del factor ramificación y de la profundidad que tuvo que explorar para encontrar la solución.
• Complejidad espacial: hay que tener en cuenta los nodos repetidos, por el coste lineal respecto al factor de ramificación y el límite de profundidad. (Rentería, R. 2011)

EJEMPLO DE  LA BUSQUEDA PRIMERO EN PROFUNDIDAD

Realizar una búsqueda primero en profundidad donde el estado inicial es A y el estado objetivo es K

Recorrido de A:K = {A,B,D,F,H,J,K }

CONCLUSIÓN

Las búsquedas no informadas son importante porque permiten resolver problemas que no cuenta con suficiente información a través de sucesores e identificando los estados hasta llegar a su estado objetivo. Las búsquedas a ciegas han desarrollado estrategias que son utilizadas de acuerdo a la búsqueda que se vaya a realizar.

Las búsquedas no informadas tiene estrategias,  sin embargo las más importante son la búsqueda primero en anchura y primero en profundidad son la base para la creación de otras estrategias. Siendo importante su estudio para conocer y  diferenciar  su funcionalidad y su aplicación. Estas estrategias tienen características que hacen identificar cuáles son los puntos débiles de cada búsqueda y resaltar cuáles son sus fuertes, para según esto escoger la estrategia más  adecuada de acuerdo al problema que nos plantemos.

BIBLIOGRAFÍA

Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.

Rentería, R. 2011. ALGORITMOS DE BÚSQUEDA. Consultado 8 de mayo. 2015. Formato PDF.

Hermoso, R y Vasirani, M. 2011. BÚSQUEDA NO-INFORMADA. Consultado 8 de mayo. 2015. Formato PDF.

____. 2008. RESOLUCIÓN DE PROBLEMAS MEDIANTE BÚSQUEDA. Consultado 8 de mayo. 2015. Formato PDF.