Algoritmo A* y limitaciones

 Algoritmo A* y limitaciones

El algoritmo A* es un potente algoritmo con la capacidad de resolver problemas de grafos que se den en un ambiente estático. La capacidad de este algoritmo es que nos facilita el camino de menor coste entre un nodo origen y un nodo destino, en base a los condiciones que le pongamos al algoritmo. Un posible ejemplo de muestra en la siguiente imagen donde podemos observar la ruta más cercana entre el nodo origen y el nodo destino. En base a un criterio establecido por nosotros le hemos informado al algoritmo que los movimientos verticales y horizontales tienen un coste de 1 y los diagonales un coste de 2. Con esa información el algoritmo ha determinado la mejor ruta.

Aunque el ejemplo anterior sea un problema relativamente simple que podríamos resolver sin la necesidad de un ordenador en un par de minutos, la potencialidad de este algoritmo se basa en que es capaz de gestionar un gran volumen de datos en muy poco tiempo con una gran variabilidad de condicionantes. Esto sucede, por ejemplo, cuando buscamos la ruta más rápida desde un punto A a un punto B en una ciudad.

A pesar de que su principal potencial la de elegir la ruta de menor coste, también puede utilizarse en otros sistema de optimización. Otro posible aplicación sería la optimización en la resolución de problemas de estado. Un posible ejemplo sería determinar el número mínimo de movimientos para resolver un cubo de Rubik partiendo desde cualquier punto. También puede ser utilizado en partidas de ajedrez, donde el algoritmo establecería las diferentes posibilidades para ganar una partida.

Su potencial es ingente, pero tiene ciertas limitaciones. El algoritmo es principalmente útil cuando hablamos de ambientes estáticos, es decir, ambientes donde las condiciones del recorrido no avanzan a medida que avanzamos. Si nos encontráramos con un sistema donde las condiciones externas se ven alteradas por factores que no controlamos, el algoritmo podría perder el control de la situación y no ser capaz de elegir la ruta más correcta.

La segunda limitación es la cantidad de datos que tiene que manejar el algoritmo. Tenemos que considerar que en una red de 10x10 cuadros, el número de movimientos es de 100, mientras que en una red de 20x20 es de 400. Es decir, duplicando la red obtenemos una cantidad de movimientos 4 veces mayor y así exponencialmente.

La potencialidad del Algoritmo A* es enorme, aunque sus limitaciones impiden la resolución de ciertos problemas de manera efectiva. En cualquier caso, el aumento de la capacidad de almacenamiento y la optimización del propio algoritmo hace que esta herramienta que fue diseñada en los años 60 siga vigente hoy en día.