Entradas
El Algoritmo A* es un algoritmo de
búsqueda que se desarrolló en 1968, el
cual encuentra la ruta más corta entre
dos puntos. Su diseño inicial le permitía resolver problemas transversales
de grafos; posteriormente, se usó para aplicaciones de búsqueda de caminos en videojuegos,
inteligencia artificial y robótica.
Este algoritmo presenta un diseño que le
permite identificar una ruta óptima desde una posición inicial dada hasta una
posición de destino dada y combina la búsqueda de costo uniforme (del Algoritmo
Dijkstra) y los algoritmos de búsqueda codiciosos; si lo comparamos con otros
algoritmos, presenta un tiempo de ejecución más breve, de fácil implementación
y una alta eficiencia.
Puedes ahondar en su funcionamiento
visitando la página: https://www.lanshor.com/pathfinding-a-estrella/
Es un algoritmo informado, utiliza una
heurística (información acerca de la posibilidad de que un nodo específico sea
mejor para intentar la próxima elección que cualquier otro nodo) lo que marca
una tendencia hacia la meta reduciendo de manera significativa el espacio
de búsqueda; esta heurística es admisible,
es decir, no sobreestima la distancia sobrante entre el nodo presente y el nodo
de la meta.
Función heurística de A*
f(n) = g(n) + h(n)
La función se encuentra compuesta por:
g(n) : es el costo de las movidas realizadas.
h(n) : es la función heurística. Representa el costo
estimado del mejor camino.
Ya que la g(n) nos da el coste del camino desde el
nodo inicio al nodo n, y la h(n) el coste estimado del camino más barato desde
n al objetivo, tenemos: f(n)= coste más barato estimado de la solución a través
de n.
Créditos de imagen: https://www.lanshor.com/pathfinding-a-estrella/
¿Qué
tipos de problemas no podrían ser resueltos por medio del algoritmo A*?
v - El algoritmo A* es útil en ambientes estáticos, pero no en un sistema
cambiante, donde las condiciones
externas sean alteradas por factores que
no controlamos.
v - La calidad de A* depende de la calidad en la heurística estimadora h (n),
si se acerca bastante al verdadero costo del camino restante, su eficiencia
será alta, pero si es muy bajo, su eficiencia disminuye.
v - No puede resolver problemas en los que la dimensión del espacio de búsqueda
sea muy grande.
v - En Pathfinding, (planificación de una ruta), el algoritmo tendría dificultades
cuando el problema contenga múltiples agentes, en los que el número de nodos a
expandir sean exponenciales en longitud de la solución; lo que hace que se
quede sin espacio antes de que se quede sin tiempo.
v - Problemas con más de una solución correcta.
v - Problemas de consecuencia incierta: no es posible planificar con
certeza pues no se sabe que ocurrirá luego del siguiente movimiento, según García
(2009).
v - Los algoritmos de búsqueda heurística de agente único no pueden ser utilizados en aplicaciones en tiempo real, debido a su costo computacional y el hecho de que no pueden comprometerse a una acción antes de que se conozca su resultado final. Korf (1990)
Por ultimo, elucubrando, problemas en donde el algoritmo debe crear rutas y no encontrarlas.
Fuentes:
Lasso-Cardona, Franco-Ocampo, Agudelo-Acevedo.
(2020). Algoritmos voraces y
heurísticos: un enfoque en el problema de la ruta mínima. INGE CUC, 16(2),
67–85.
Daniel García López (2009). Curso Inteligencia
Artificial. Unidad III: Solución de problemas por búsqueda
Tomás, V., Núñez, F., Andrade, E. Análisis de
algoritmos de búsqueda en espacio de estados. Ciencias Huasteca Boletín científico
de la escuela superior de Hueutla.
DOI: https://10.29057/ESH.V3I5.1089
Korf, R. (1990). Real-Time Heuristic Search. Artificial Intelligence, 42(2-3), 189-211
DOI: https://10.1016/0004-3702(90)90054-4
Algoritmo A*. Instituto Tecnológico de Nuevo
Laredo
http://www.itnuevolaredo.edu.mx/takeyas/libroisc/03.-ConceptosAlgoritmos.pdf
https://revistascientificas.cuc.edu.co/ingecuc/article/download/2752/3531?inline=1
