¿Qué es el Algoritmo A*? Ventajas y desventajas
El algoritmo A* (pronunciado como “A estrella” o “A asterisco”) es un algoritmo de búsqueda en grafos diseñado para buscar rutas de navegación autónomas. Fue propuesto por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael para encontrar el camino óptimo entre un origen y un destino. Para resolver el problema, el espacio se divide en una red teselada en la que el centro de cada celda constituye lo que en teoría de grafos se conoce como un nodo. El algoritmo trata entonces de encontrar la ruta que conlleva “menor coste” entre el nodo origen y el nodo destino. Para ello, utiliza una función de evaluación que determina la probabilidad de que los distintos nodos de la red pertenezcan al camino óptimo. Al tratarse de una búsqueda informada – el algoritmo informa de la probabilidad de que cada celda se encuentre en la ruta de menor coste-, se dice que la función es heurística. Pero para que el algoritmo sea potente no solo debe tener en cuenta el valor heurístico de lo...
Un formato impactante, especialmente la conclusión :-)
ResponderEliminar