BÚSQUEDA INFORMADA Y EXPLORACIÓN

TEMA: BÚSQUEDA INFORMADA Y EXPLORACIÓN

Semana 12 al 16 de Octubre 2015

INTRODUCCIÓN

La búsqueda no informada a diferencia de la informada posee gran desventaja ya que esta se caracteriza por no brindar información previa al agente acerca del problema a solucionar, es decir el agente se encontrara en un espacio que es totalmente desconocido para él. Por tanto la búsqueda informada tiene un conocimiento puntualizado del problema, resultando más eficiente para el agente.

En el transcurso de este documento iremos conociendo porque la búsqueda  informada sobresale ante la búsqueda no informada y así mismo la aplicación de heurísticas que ayudan a disminuir  los costos de las búsquedas.

MARCO TEÓRICO

 ESTRATEGIA DE BÚSQUEDA INFORMADA (HEURÍSTICAS)

Una búsqueda informada es aquella en la que se tiene un conocimiento previo acerca del problema a solucionar, en si es muy optima porque le da al agente una visión más clara a cerca de la problemática y por ende los resultados esperados serán más satisfactorios que una estrategia no informada.

A la aproximación general que se considerara se la denominara búsqueda primero el mejor. Esta búsqueda es venerable pero su desventaja es que es inexacta,  ya que si se diera el caso de expandir el primer  nodo se muestra que es una búsqueda en absoluto. Lo más óptimo sería elegir el nodo que refleje ser el mejor según la función de evaluación. Cuando la función es exacta entonces se asume que esta es la mejor.

Existe una infinidad de familia de Búsqueda primero el mejor, diferenciándose cada una por sus funciones de evaluación. Una componente clave de estos algoritmos es una función heurística la misma que es denotada h(n) siendo este el coste estimado del camino más barato desde el nodo n a un nodo objetivo.

BÚSQUEDA VORAZ PRIMERO EL MEJOR

Esta búsqueda comprende en expandir el nodo más cercano al objetivo, invocando que se conducido lo más posible a la solución .De esta forma es capaz de evaluar los nodos usando únicamente la función heurística: f(n)=h(n).

La búsqueda voraz primero el mejor es similar a la búsqueda primero en profundidad debido a que esta opta seguir un camino hacia el objetivo, sin embargo retorna a su punto de partida si se encuentra en camino sin salida. Al igual que la búsqueda primero en profundidad soporta los mismos defectos, no resulta optima y solo es parcial porque puede ir hacia abajo en un camino infinito y nunca volver para intentar otras posibilidades).

En el peor de los casos en cuanto al tiempo y espacio es O(bm), en el que m viene siendo la profundidad máxima del espacio de búsqueda. Se puede dar el caso que si se usa una buena función, se puede reducir la complejidad   formidablemente.

BÚSQUEDA A*: MINIMIZAR EL COSTO ESTIMADO TOTAL DE LA SOLUCIÓN

A la búsqueda primero el mejor también se la llama búsqueda A*, dicha búsqueda evalúa los nodos combinando g(n) que es el coste para alcanzar el nodo, h(n) coste de ir al nodo objetivo: obteniendo la siguiente función.

F(n)=g(n)+h(n)

F(n), Es igual al costo más barato estimado de la solución a través de n. La forma más sencilla de poder analizar la optimalidad  es si se emplea mediante con la Búsqueda –Arboles.

CONCLUSIONES

Los costos de la búsqueda se pueden disminuir anticipadamente empleando heurísticas. Pero sin embargo en algunos algoritmos en los que se  emplean heurísticas se ha hallado que sus costos en cuanto se refiere a las búsquedas son muy  elevados aunque estos sean considerados los más óptimos.

La búsqueda primero el mejor le da acogida a los nodos no expandidos que tienen menor costo y su función fundamental es heurística h(n).

A diferencia de la búsqueda primero el mejor, la búsqueda primero el mejor  avara no sobresale porque no es muy optimo, pero no obstante a menudo tiene mucha eficacia.

La utilidad de aquellos algoritmos que se  desempeñan en la búsqueda heurística estos están  ligados de la disposición de la función heurística.

BIBLIOGRAFÍA

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España

Ruiz, J; Matín, M. 2011. Búsqueda Informada mediante Técnicas Heurísticas. (En línea). Consultado 9 de Oct del 2015. Formato PDF. Disponible en: https://www.cs.us.es/cursos/ia1/temas/tema-04.pdf