• Author / Uploaded
• Walt Leandro Coz

Citation preview

Algoritmo A* Autor

Uziel Octavio González Escorcia

El algoritmo de búsqueda A* o también denominado “A Estrella” se encuentra dentro de los tipos de algoritmos de búsqueda en grafos, representado por Peter E. Hart, Nils J. Nilsson y Bertram Rápale, en 1968. El algoritmo A* es el único que garantiza, sea cual sea la función heurística, que se tiene en cuenta el camino recorrido y por ende es mejor que la versión más extendida de "primero el mejor", aquélla que sólo considera la distancia a la meta. En definitiva, sí tiene razón en el caso concreto que usted plantea, pero no la tiene en general.

Búsqueda A* El algoritmo A estrella es un algoritmo de búsqueda para grafos que encuentra el camino de menor coste entre un nodo inicial y un nodo meta. Usa una función heurística (denotada f'(x), es una aproximación a f(x), función que proporciona la verdadera evaluación de un nodo) para determinar el orden en que la búsqueda visita nodos en el árbol. La mencionada función es la suma de otras dos funciones: una función que indica el coste del camino seguido hasta un cierto nodo (denotada g(x)) y una estimación admisible de la distancia hasta la meta (h'(x)). La función de evaluación resulta entonces f (x) = g(x) + h (x). Empezando en un nodo inicial dado, el algoritmo expande el nodo con el menor valor de f'(x). A estrella mantiene un conjunto de soluciones parciales almacenadas en una cola de prioridad, cómo en el algoritmo del apartado anterior. La prioridad asignada a un camino x viene determinada por la función f'(x). El proceso continua hasta que una meta tiene un valor f'(x) menor que cualquier otro nodo en la cola (o hasta que el árbol ha sido completamente recorrido).

Representación A continuación se muestra la clásica representación del algoritmo A *. Donde:

-

-

Introducción. Búsqueda A* Representación Complejidad Características Aplicaciones Referencias

g (n) es la distancia total que ha tomado para llegar desde la posición inicial a la ubicación actual. h '(n) es la estimación de la distancia desde la posición actual con el destino, es una función heurística se utiliza para crear esta estimación sobre cuán lejos se está para alcanzar la meta. f '(n) es la suma de g (n) y h' (n). Este es el camino actual estimado más corto. f (n) es el verdadero camino más corto que no se descubrieron hasta que el algoritmo A * ha terminado.

Complejidad La complejidad computacional del algoritmo está íntimamente relacionada con la calidad de la heurí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. Para que esto último suceda, se debe cumplir que

donde h* es una heurística óptima para el problema, como por ejemplo, el coste real de alcanzar el objetivo.

Características Realiza la búsqueda informada teniendo en cuenta dos factores fundamentales, el valor heurístico de los nodos y el coste real del recorrido.

Se utiliza en la búsqueda de un camino más corto. El Algoritmo no desarrolla un camino por interacción, sino que desarrolla varios caminos y elige los más prometedores. Es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad: mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores. Si para todo nodo n del grafo se cumple que g(n) = 0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n) = 0, el algoritmo 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, quiere decir que no sobrestime el coste real de alcanzar el nodo objetivo, si fuese así el algoritmo pasa a denominarse simplemente A, debido a que no se asegura que el resultado obtenido sea el camino de coste mínimo. Debido a que se 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.

Aplicaciones Minería de datos, búsqueda de comportamiento en los datos. Procesamiento de imágenes. Medicina humana, software médicos, control de tumores, problemas cancerígenos. En la aeronavegación y transporte, el pilotaje automático, búsquedas de rutas más próximas. Video juegos de estrategia, camino más corto, ejemplo:  Pacman: Los fantasmas que persiguen a Pacman buscan el camino más corto, en lugar de aparecer en forma aleatoria en el Mapa del Juego.



Age of Empires: un juego de conquista de civilizaciones, los enemigos salvan obstáculos para llegar a la ciudad del adversario.

Referencias [1] http://74.125.113.132/search?q=cache:XOfZN2Jdq8wJ:tspuib.googlecode.com/files/doc.pdf+algo ritmo+a+estrella&cd=3&hl=es&ct=clnk&gl=mx [2] http://www.scribd.com/doc/19950923/Busqueda-Heuristica