Algoritmo A*

 El Algoritmo A*

Como todo en la vida, hay que empezar por el principio, y más cuando son temas tan complicados como la inteligencia artificial. ¿Qué es el algoritmo A* (A estrella)? Es un algoritmo que se utiliza en ciencias de la computación (en informática) para buscar la conexión posible y 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, si, este algoritmo lleva ayudandonos desde hace más de 50 años.

Foto de Alina Grubnyak. Fuente: Unsplash

Una vez sabemos qué es el algoritmo A*, la siguiente pregunta que nos hacemos es cómo funciona el Algoritmo A*. Esto es un poco más complicado de explicar pero lo primero que tenemos que tener en cuenta es que es un algoritmo 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. En palabras más claras: se basa en deducciones. Por ejemplo, hay nubes, va a llover. Pero no siempre es cierto. Por ello, un algorirmo heurístico nos puede llevar a una solución óptima (la lluvia) pero también errónea o no encontrar solución (no lluvia). Aquí os dejo un enlace donde se ve cómo funciona este algoritmo de forma simplificada con imágenes y un vídeo donde se ve cómo el algoritmo A* se ha utilizado en videojuegos:

Sin embargo, y a pesar de que es un algoritmo muy utilizado, presenta algunos problemas. El más principal de todo es que guarda información sobre todos los caminos generados. Si nos enfrentamos a un gran problema, puede que haya tal cantidad de información que no tendríamos memoria suficiente. Y por otro lado, es que este algoritmo funciona bien en terrenos fijos pero no tan bien cuando hay objetos móviles o el terreno puede cambiar. No tendríamos suficiente memoria o tiempo de procesamiento para ese tipo de problemas.