Blog
Algoritmos de búsqueda
7 febrero, 2022
(Fuente imagen: Lambda)
El algoritmo A* es un algoritmo de búsqueda en grafos desarrollado en 1968. Este algoritmo es de tipo heurístico, es un método basado en la división de un problema complejo en problemas más sencillos. El algoritmo A*fue diseñado para buscar rutas de navegación autónomas y busca el camino de menor coste entre dos puntos. Una de sus aplicaciones más habituales es para detectar geo-localizaciones en las que se tiene conocimiento de coordenadas de ubicación por satélite.
Lo primero que hace el algoritmo es dividir el espacio en celdas. Se evalúa por un lado la longitud del camino más corto de la celda al punto de origen, y por otro el camino más corto de la celda al punto final. A cada celda se le da una probabilidad de pertenecer al camino óptimo y se busca que este camino óptimo sea el de menor coste.
El problema de este tipo de algoritmos es que se basan en la minimización de una función que puede no indicar el camino de coste real más bajo. Por esto, los algoritmos deben incluir tanto el valor heurístico de las celdas como el coste real del recorrido. Otro de los problemas de este algoritmo es el espacio de almacenaje que requiere, ya que debe almacenar todas las distancias de cada celda a origen y destino. La cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema. Para resolver este problema se han propuesto variaciones de este algoritmo.
Referencias