ESTRATEGIAS DE BÚSQUEDA INFORMADA

INTRODUCCIÓN

Las estrategias de búsqueda no informada resuelven problemas mediante generación sistemática de estados, pero son muy ineficientes

Vamos a ver cómo las estrategias de búsqueda informada o heurística, usando conocimiento específico del problema, pueden resolver problemas más eficientemente

OBJETIVO

La siguiente clase tiene como objetivo comprender las estrategias de Búsqueda informada.

Búsqueda voraz primero el mejor

La búsqueda voraz priman 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: ñn) = h(n). Veamos cómo trabaja para los problemas de encontrar una ruta en Rumania utilizando la heurística «Bstanriaoi linea recta que llamaremos hDUt Si el objetivo es Bucarest, tendremos que conocer las distancias en línea recta a Bucarest, que se muestran en la. Por ejemplo, h[xJyEn(Arad)) = 366. Notemos que los valores de hDLRno pueden calcularse de la descripción de problema en sí mismo. Además, debemos tener una cierta cantidad de experiencia para saber que hnK está correlacionada con las distancias reales del camino y es, por lo tanto, una heurística útil.

BÚSQUEDA A*

Características Principales

Como todo algoritmo de búsqueda en anchura, A* es un algoritmo completo: en caso de existir una solución, siempre dará con ella. Si para todo nodo n del grafo se cumple g(n) = 0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n) = 0, A* pasa a ser una búsqueda de coste uniforme no informada.

Para garantizar la optimalidad del algoritmo, la función h(n) debe ser admisible, o sea que no sobrestime el coste real de alcanzar el nodo objetivo.

De no cumplirse dicha condición, el algoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que h(n) es consistente (o monótona), es decir, que para cualquier nodo n y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar el objetivo desde el sucesor. La complejidad computacional está relacionada con la calidad de laheurística que se utilice en el problema. En el caso peor, con una heurística de pésima calidad, la complejidad será exponencial, mientras que en el caso mejor, con una buena h'(n), el algoritmo se ejecutará en tiempo lineal.

El espacio requerido por A* para ser ejecutado es su mayor problema. Dado que tiene que almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema. Para solucionar este problema, se han propuesto diversas variaciones de este algoritmo, como pueden ser RTA*, IDA* o SMA*.

El rendimiento de los algoritmos de búsqueda heurística depende de la calidad de la función heurística.

BÚSQUEDA CON MEMORIA ACOTADA

Problema del algoritmo A* => Altos requerimientos de memoria.
Algoritmo A*PI: Los requerimientos de memoria se pueden solucionar aplicando el algoritmo de PI
(Profundidad Iterativa) al A*:
– Función de corte: f-coste (g+h)
– En cada iteración el valor del corte es f-coste más pequeño de cualquier nodo que excedió el coste de la iteración anterior.
Algoritmos con memoria acotada:
– BRPM: Búsqueda recursiva primero el mejor.
– A*M: Algoritmo A* con memoria acotada.
– A*MS: Algoritmo A* con memoria simplificada.

CONCLUSIÓN

Búsqueda voraz primero el mejor.- Expande el nodo más cercano al objetivo, asumiendo que probablemente conduzca más rápidamente a la solución.  La función de evaluación f(n) es la función heurística  h(n)=f(n) = h(n) donde h(n) = costo estimado del camino más barato desde el nodo n hasta el objetivo

Búsqueda A*.- Minimizar el costo estimado total de la solución
Evalúa los nodos combinando g(n) y h(n)
 g(n): costo de haber alcanzado n
 h(n): costo para llegar desde n hasta el objetivo
 f(n) = g(n) + h(n) -> costo más barato estimado de la f(n) = g(n) + h(n) -> costo más barato estimado de la solución a través de n En cada paso se expande el nodo con el valor más bajo de f(n), ó sea, de g(n)+h(n)

La búsqueda A* es óptima siempre y cuando la función heurística h(n) sea una heurística admisible,
nunca sobreestime el costo de alcanzar el objetivo, son funciones optimistas.

BIBLIOGRAFÍA

Cesar S 2008. Búsqueda Informada.  (En línea). EC. Consultado, 13 de Noviembre. 2014. Formato HTML. Disponible en: http://www.ecured.cu/index.php/Algoritmo_de_B%C3%BAsqueda_Heur%C3%ADstica_A*
Ruiz, j. 2012. Búsqueda Informada. (En línea). Disponible en: http://www.cs.us.es/cursos/ia1/temas/tema-06.pdf

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.