BÚSQUEDA INFORMADA

Fecha de clase: 6 de noviembre

INTRODUCCIÓN

En esta clase se aprendió sobre las diferentes búsquedas informadas, ya que para realizar una búsqueda óptima hay que tener conocimiento de los tipos de búsqueda existente, cabe recalcar que esta búsqueda ya tiene conocimiento acerca del estado en que se encuentra aparte de lo que indica el problema.

MARCO TEÓRICO

BUSQUEDA INFORMADA

Esta sección muestra cómo una estrategia de búsqueda informada puede encontrar soluciones de una manera más eficiente que una estrategia no informada. Algunas estrategias son:

BUSQUEDA VORAZ PRIMERO EL MEJOR

Trata de expandir el nodo más cercano al objetivo, alegando que probablemente conduzca rápidamente a una solución. Así, evalúa los nodos utilizando solamente la función heurística: f(n)=h(n). 

No tiene en cuenta el coste de llegar hasta n, Se pretende llegar rápidamente a la solución,  sin importar tanto el coste. La bondad que tenga la función heurística h determinará la rapidez con que llegamos a un estado objetivo.

La minimización de h(n) puede llevarnos a ventajas falsas, puede hacernos expandir nodos innecesarios. Si no se tiene cuidado con los estados repetidos,  podemos llegar a callejones sin salida; se parece a la búsqueda primero en profundidad y tiene las mismas desventajas:

° No es óptima y es incompleta

° La complejidad es O(bm). (Diez, J)

BUSQUEDA A*

A la forma más ampliamente conocida de la búsqueda primero el mejor se le llama búsqueda A* (pronunciada «búsqueda A-estrella»). Evalúa los nodos combinando g{n), el coste para alcanzar el nodo, y h(n), el coste de ir al nodo objetivo:

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

Ya que la g(n) nos da el coste del camino desde el nodo inicio al nodo n, y la h(n) el coste estimado del camino más barato desde n al objetivo, tenemos:

F(n) = coste más barato estimado de la solución a través de n.

Así, si tratamos de encontrar la solución más barata, es razonable intentar primero el nodo con el valor más bajo de g(n) + h(n). Resulta que esta estrategia es más que razonable: con tal de que la función heurística h(n) satisfaga ciertas condiciones, la búsqueda A* es tanto completa como óptima.

La optimalidad de A* es sencilla de analizar si se usa con la Búsqueda-Árboles.

En este caso, A* es óptima si h(n) es una heurística admisible es decir, con tal de que la h(n) nunca sobrestime el coste de alcanzar el objetivo. Las heurísticas admisibles son por naturaleza optimistas, porque piensan que el coste de resolver el problema es menor que el que es en realidad. Ya que g(rí) es el coste exacto para alcanzar n, tenemos como consecuencia inmediata que la f\ri) nunca sobrestima el coste verdadero de una solución a través de n. (Russell, S y Norvig, P)

CONCLUSIÓN

Como se habló en clases las búsquedas informadas son mucho más eficientes que las no informadas, ya que además de tener el conocimiento previo también da solución de una manera más rápida claro está dependiendo de la calidad y cantidad de heurística.

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Diez, J. 2009. Búsqueda Informada. Formato PDF. (En línea). Disponible en http://www.aic.uniovi.es/ssii/SSII-T3-BusquedaII.pdf