¿Qué es el algoritmo A* (A estrella)? Se trata un algoritmo que se utiliza en ciencias de la computación para buscar la conexión más eficiente entre dos puntos. Es decir, busca el camino que genere menos coste entre dos puntos, el origen y el destino. Este algoritmo se presentó por primera vez en 1968 y ha estado presente en casi todas las aplicaciones de búsqueda de caminos desde el principio de los tiempos hasta la última década.
El algoritmo de búsqueda A* se clasifica dentro de estos algoritmos de búsqueda informada. Este tipo de algoritmos, frente a los de búsqueda ciega, se caracterizan por poseer una información extra sobre la estructura del espacio en el que se realiza la búsqueda, lo que les permite alcanzar más rápidamente (o con menor coste) su objetivo final. Es un algoritmo de tipo heurístico, es decir, se basa en reglas que permiten escoger las ramas del espacio que nos llevan hacia una solución aceptable del problema. Lo que realiza el algoritmo es construir distintas rutas desde un punto inicial hasta encontrar alguna que llegue hasta el nodo final. De este modo solo construye aquellas rutas que son candidatas a formar una solución. Para poder determinar qué rutas son las que tienen mayor probabilidad de llegar al nodo meta.
Este algoritmo utiliza la función de evaluación:
f(n) = g(n) + h'(n)
- h'(n) representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final
- g(n) representa el costo real del camino recorrido para llegar a dicho nodo, n
Aplicaciones
El algoritmo A * al ser especialmente diseñado para detectar en las rutas menos costosas dentro de un grafo complejo, es normalmente utilizado para encontrar rutas cortas entre pares individuales de ubicaciones. Una de sus aplicaciones más usuales es para detectar geo-localizaciones en las que se tiene conocimiento de coordenadas de ubicación por satélite.
Diseño de pathfining para videojuegos o robótica. Aplicado a videojuegos, pathfinding es la capacidad de la inteligencia artificial de un personaje u otro objeto móvil de un juego de encontrar el camino más corto entre dos puntos y llegar a su destino. Es especialmente importante en juegos de estrategia, donde el jugador debe seleccionar una unidad y marcar el punto al que debe desplazarse. Si el pathfinding del juego no está bien diseñado, la unidad puede bloquearse y no alcanzar su destino. Es especialmente importante en juegos de estrategia, donde el jugador debe seleccionar una unidad y marcar el punto al que debe desplazarse. Si el pathfinding del juego no está bien diseñado, la unidad puede bloquearse y no alcanzar su destino.
Limitaciones
La complejidad computacional del desarrollo del algoritmo A* está ligado directamente a la calidad de la heurística que se proporciona, 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 heurística el algoritmo se ejecutará en tiempo lineal. La heurística es una aproximación cuantitativa de lo que falta para llegar a la solución.
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.
arrebol ciencia 
Deja un comentario