Búsqueda Informada

La búsqueda informada


La búsqueda informada utiliza el conocimiento específico del problema.
• Puede encontrar soluciones de una manera más eficiente.
• Una función heurística, h(n), mide el coste estimado más barato desde el nodo n a un nodo objetivo.
•h(n) se utiliza para guiar el proceso haciendo que en cada momento se seleccione el estado o las operaciones más prometedores.
Elpropósito de la búsqueda informada es utilizar conocimiento específico del problema para alcanzar el objetivo de manera más eficiente. La idea es ser capaces de medir la calidad de un estado, Eso nos permitirá dirigir la búsqueda por los mejores estados que estarán más cerca del objetico en cuenta a la calidad de los estados.



Estrategias

Las estrategias que usan la información dedefinición del problema y el coste del estado actual al objetivo (información específica del problema) son:

» El primero mejor (Best first Search)
» Búsqueda Avara
» A*
» IDA*
» Mejora iterativa
– Hill climbing
– Simulated Annealing

La función de evaluación
Mide la calidad de n
Un nodo tendrá calidad cuanto menor sea la distancia al objetivo
F(n) estima desde ese nodo n a un nodo objetivoLas búsquedas informadas expanden primero los nodos que están más cerca de los objetivos.

Búsqueda primero el mejor
La búsqueda primero el mejor es un caso particular del algoritmo general de Búsqueda -Árboles o Búsqueda- Grafos en el cual se selecciona un nodo para la expansión basada en una función de evaluación f(n).
Esta función evaluación devuelve un número que sirve para representar lodeseable (o indeseable) que sería la expansión de un nodo. Se expande primero aquel nodo que tiene mejor evaluación. Se escoge el que parece ser el mejor pero puede no serlo.
Hay una familia entera de algoritmos de Búsqueda-Primero-Mejor con funciones de evaluación diferentes. Una componente clave de estos algoritmos es una función heurística, denotada h(n):
H(n)= coste estimado del camino másbarato desde el nodo n a un nodo objetivo.
Las funciones heurísticas son la forma más común de transmitir el conocimiento adicional del problema al algoritmo de búsqueda.
Si en verdad fuese posible expandir desde un principio el mejor nodo, en realidad no se trataría de una búsqueda; sería encaminarse directamente a la meta. Lo que sucede es que se escoge el nodo que parece ser el mejor, según loaconsejado por la función de evaluación.
Puesto que su objetivo es encontrar soluciones de bajo costo, por lo general en estos algoritmos se utiliza alguna medida estimada del costo de la solución, y se hacen esfuerzos por reducir esta medida al mínimo.
Para enfocar la búsqueda, en tal medida debe figurar algún tipo de cálculo del costo de ruta que va de un estado al estado más cercano a la meta.Se puede decir que hay

Idea: Usar la función de evaluación f(n) para cada nodo, de modo que se pueda estimar su “deseabilidad” y sea el nodo más deseable que no ha sido expandido el que se elija para expandir.
Implementación: Los nodos en la frontera deben ordenarse de forma decreciente con respecto a su deseabilidad.
Casos especiales:
Búsqueda voraz primero el mejor
A*



Busquedavoraz primero el mejor

La búsqueda voraz primero el mejor trata de expandir el nodo más cercano al objetivo, alejando 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).
Este algoritmo consiste en reducir al mínimo el costo estimado para lograr una meta.
El nodo que se considere más cercano al estado de meta es elque se expande primero.
La búsqueda avara y la preferente por profundidad se asemejan por su indicación a utilizar una sola ruta hasta llegar a la meta, pero se atorarán cuando topen con un callejón sin salida.
Sus deficiencias son las mismas que las de la búsqueda preferente por profundidad: no es óptima y es incompleta, pues puede recorrer una ruta infinita y nunca regresar a probar otras...