BÚSQUEDA A*

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

La forma más ampliamente conocida de la búsqueda  primero el mejor se le llama búsqueda A* conocida como “Búsqueda A-estrella”; la cual evalúa 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 más barato desde n hasta el objetivo.

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

De esta manera se trata de encontrar la solución más barata y es razonble intentar primero el nodo con el valor más bajo de g(n).

Cabe mencionar que esta estrategia resulta ser más que razonable con tal que la funcion heurística h(n) satisfaga cierta condiciones; la búsqueda A* compleja como optima, la optimalidad de A* es sencilla de analizar si se usa con la búsqueda de árboles.

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. 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 solución a través de n.

Como por ejemplo:

En el ejemplo de la figura, se ha superpuesto una rejilla para estimar distancias. Supóngase que se quiere determinar el camino óptimo entre A y F. Inicialmente, se toma el origen y se coloca en la lista Abierta.

El nodo A pasa a lista cerrada y se pasan a la lista Abierta los conectados con el (B y C), asignándoles valores R, E y punteros al antecesor (A).

Se selecciona el de menor valor T de la lista Abierta (C) y se pasa a lista cerrada. Los conectados con el (D y E) se pasan a Abierta, asignándoles valores R, E y punteros al antecesor (C).

Se selecciona el de menor valor T de la lista Abierta (B) y se pasa a lista cerrada. Los conectados con el (D y E) no se pasan a Abierta, pues el valor T es mayor que los ya existentes.

Se selecciona el de menor valor T de la lista Abierta (D) y se pasa a lista cerrada. Sólo se pasa el nodo F a Abierta, pues B está ya en cerrada.

Se selecciona el de menor valor T de la lista Abierta (F) y se pasa a lista cerrada. Como es el nodo destino, se acaba el proceso.

Ahora, se puede recuperar el camino óptimo retrocediendo desde el nodo F mediante los punteros.

CONCLUSIÓN

la búsqueda a* utiliza dos parámetros para evaluar la ruta que tomar para llegar al nodo objetivo  ademas de utilizar la heuristica utiliza la función del coste del camino permitiendo así evaluando el camino utilizando dos parámetros ya mencionados y dependientes uno del otro para la realización de esta búsqueda.