Inteligencia artificial
busqueda informada

Michelle Diaz

Republica bolivariana de venezuela
universidad fermin toro
decanato de ingeneria

Bsqueda ciega o no informada (anchura, profundidad): no cuenta con ningn conocimiento sobre cmo llegar al objetivo.

Bsqueda informada: aplicar conocimiento al proceso de bsqueda para hacerlo ms eficiente.

El conocimiento vendr dado por una funcin que estima la bondad de los estados:

Dar preferencia a los estados mejores.

Ordenando la cola de ABIERTOS, comparando su bondad estimada.

Objetivo: reducir el rbol de bsqueda, ganando eficiencia en la prctica.

Busqueda informada

Del griego heuriskein, descubrir: Eureka!

Segn la RAE: tcnica de la indagacin y del descubrimiento.

Otro significado: mtodo para resolver problemas que no garantiza la solucin, pero que en general funciona bien.

En nuestro caso, una heurstica ser una funcin numrica sobre los estados.

Caractersticas:- Esta funcin de evaluacin se utiliza para guiar el proceso haciendo que en cada momento se seleccione el estado o las operaciones ms prometedoras.- No siempre se garantiza encontrar una solucin (si existe).-No siempre se garantiza encontrar la solucin ms prxima (la que tenga el nmero menor de operaciones).

Heuristica

La forma ms ampliamente conocida de la bsqueda primero el mejor se le llama bsqueda A* conocida como Bsqueda A-estrella; la cual evala los nodos combinando g(n) y h(n) de la siguiente manera:

f(n)=g(n)+h(n)

g(n) significa el coste para alcanzar el nodo; lo que quiere decir que nos da el coste de camino desde el nodo inicial al nodo n y h(n)=significa el coste de ir al nodo objetivo, es decir, el coste estimado del camino ms barato desde n hasta el objetivo.

f(n)=coste ms barato estimado de la solucin a travs de n.

De esta manera se trata de encontrar la solucin ms barata y es razonble intentar primero el nodo con el valor ms bajo de g(n).Cabe mencionar que esta estrategia resulta ser ms que razonable con tal que la funcion heurstica h(n) satisfaga cierta condiciones; la bsqueda A* compleja como optima, la optimalidad de A* es sencilla de analizar si se usa con la bsqueda de rboles.A* es ptima si h(n) es una heurstica admisible, es decir, con tal de que la h(n) nunca sobrestime el coste de alcanzar el objetivo. Como g(n) es el coste exacto para alcanzar n, tenemos como consecuencia inmediata que la f(n) nunca sobrestime el coste verdadero de una solucin a travs de n.

Bsqueda A*: minimizar el costo estima total de la solucin

Es de tipo de algoritmos de bsqueda heurstica con limitacin de memoria. Los ms utilizados son el IDA* (Iterative Deepening A*), y SMA* (Simplified memory A*).El IDA* (Iterative-Deepening A*) es al igual que el DFID un algoritmo basado en la profundizacin iterativa. La nica diferencia entre ambos algoritmos estriba en que mientras el DFID se basa en la profundidad para cada una de sus iteraciones, el IDA se basa en la informacin heurstica que posee para determinar el siguiente lmite de la iteracin. El tratamiento de esa informacin se realiza de igual forma que en el algoritmo del A*, o sea mediante la funcin de evaluacin f introducida anteriormente. El funcionamiento del algoritmo es el siguiente:

En cada iteracin el algoritmo realiza una bsqueda en profundidad hasta donde se lo permita su lmite de coste. Cada vez que se visita todo el grafo de bsqueda contenido dentro de ese lmite sin hallar la solucin entonces, el algoritmo incrementa el lmite de coste. Ese nuevo lmite viene dado por el menor de los lmites de corte, o sea, por el menor valor del coste de los nodos que tenan un valor superior en la anterior iteracin.

Este algoritmo se considera limitado en profundidad, aunque esta afirmacin no sea estrictamente cierta. La razn de ello viene dado por su eficacia en cuanto al uso de memoria pero en su funcionamiento no realiza un control estricto de la memoria.

Bsqueda IDA*