Algoritmo de búsqueda A*
Fuente: https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*
En 1964 nace el Algoritmo A*, cuando Nils Nilsson propuso una heurística, una estrategia de búsqueda de caminos con información, basada en aproximaciones para incrementar la velocidad del algoritmo de búsqueda Dijkstra.
A* es un algoritmo de búsqueda en grafos que tiene como principales características encontrar siempre una solución y esta será el camino de menor costo entre el punto origen y el punto de destino, siempre y cuando este segundo punto exista.
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 no construye todas las rutas posibles en una situación determinada sino sólo aquellas rutas que son candidatas a llegar al destino final, ahorrando así una cantidad importante de cálculo.
Para determinar qué rutas con mayor probabilidad de llegar a la meta utiliza valores de costo total del trayecto hasta el destino, valores del camino desde el nodo actual a otro y el valor de la heurística entre todos los nodos posibles.
Fuente: https://www.lanshor.com/pathfinding-a-estrella/
Claro, las técnicas heurísticas, están pensadas para mejorar la eficiencia del proceso de búsqueda, pero pueden no ser completas porque sólo manejan información limitada. En todo caso, con respecto al algoritmo A* es un algoritmo completo porque siempre encuentra la solución, se considera el mejor algoritmo para resolver problemas de búsqueda de caminos.
Situaciones problemáticas para el A*
A* puede convertirse en un algoritmo inservible en algunas situaciones concretas:
- Cuando no tenemos toda la información sobre el recorrido que tenemos que transitar hasta el nodo final.
- Cuando solo vemos una porción de mapa cercano.
- Cuando los obstáculos cambian en el tiempo, esto es situaciones en las que los nodos van cambiando.
Por otro lado, el trabajo con A* es continuo y existen propuestas de mejora para optimizar sus resultados en el desarrollo de juegos de búsqueda cada vez más complejos. Algunas de las que es posible encontrar en diferentes foros de la red plantean por ejemplo usar una heurística pesimista que sobreestime la distancia restante, aunque es probable que de esta manera encontremos la ruta de menor coste, nos permite reducir búsquedas redundantes, o realizar búsquedas del camino de origen a meta y de meta a origen al mismo tiempo, lo que implica mantener el cálculo de 2 conjuntos de datos.
Algunas fuentes consultadas:
https://www.lanshor.com/pathfinding-a-estrella/
https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*
https://stackoverflow.com/questions/9511118/is-a-the-best-pathfinding-algorithm
https://gamedev.stackexchange.com/questions/130114/reconciling-flocking-and-a-theory
https://www.math.unipd.it/~motta/slides%20conv.%20PD%2017/cacace.pdf
iruzkinik ez:
Argitaratu iruzkina