TEMA 4: Estrategias de búsqueda informada.

Estrategias de búsqueda informada.

 24 de junio del 2014

Introducción

En esta clase el objetivo es mostrar cómo una estrategia de búsqueda  informada la cual  utiliza el Conocimiento específico del problema y no la definición del problema puede en contra soluciones de una manera más eficiente que una estrategia no informada, para cual tomaremos dos ejemplos de búsqueda informada para dar una visión más clara de cómo funciona esta clase de algoritmos.

Desarrollo

Estrategias de búsqueda informada.

Búsqueda voraz primero el mejor

La búsqueda primero el mejor es un caso particular del algoritmo general de BÚSQUEDA-ÁRBOL o de  BÚSQUEDA-GRAFO en el cual selecciona un nodo para la expansión basada en una función de evaluación. f(n).

La búsqueda primero el mejor puede implementarse  dentro de nuestro marco general de búsqueda con una cola con prioridad, una estructura de datos que mantendrá la frontera en orden ascendente de f-valores.

Hay una familia entera de algoritmos de BÚSQUEDA-PRIMERO con funciones de evaluación diferentes. Un componente clave de estos algoritmos es una función heurística', denotada h(n):

h(n) = coste estimado del camino más barato desde el nodo n a un nodo objetivo.

Búsqueda A*: minimizar el costo estimado total de la solución

A la forma más ampliamente conocida  de la búsqueda primero  el mejor se la llama búsqueda

A*: (pronunciada búsqueda A -estrella,).evalúa los nodos combinados 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 g(n) nos da el coste del camino desde el nodo inicial al nodo n, 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

La optimización de A* es sencilla de analizar si se usa con la BÚSQUEDA EN ARBOL. 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(n) es el coste exacto para alcanzar n, tenemos como consecuencia inmediata que la, f(n) nunca sobrestima el coste verdadero de una solución través de n.

Conclusiones

Búsqueda primero el mejor es una BÚSQUEDA-GRAFO donde los nodos no expandidos de costo mínimo se escogen para la expansión  Los algoritmos primero el mejor utiliza típicamente una función heurística h(n) que estima el coste de una solución desde n.

 Búsqueda A* expande nodos mínimos f(n)=g(n)+h(n). A* es completa y óptima. Con tal que garanticemos que h(n) sea admisible o consistente. La complejidad en espacio de A* es todavía Prohibitiva.

BIBLIOGRAFIA

˜Russell, S. Norvig, P. 2004. INTELIGENCIA A HTXFKCIAI, UN ENFOQIJE MUDERNO.2 ed. PEARSON EDUCACIONS,.S A. Formato PDF. Pag. 120-140.