Las limitaciones del algoritmo A*

El algoritmo A* es un algoritmo de búsqueda inteligente o informada que busca el camino más corto desde un estado inicial al estado final a través de un espacio de problemas usando para ello una heurística óptima.

Se usa el algoritmo A* para encontrar el camino mínimo entre dos nodos, por lo que es un algoritmo de búsqueda en grafos. Debido a esto, sus usos principales son la búsqueda de rutas óptimas en cualquier contexto que podamos llegar a imaginar.

Sus limitaciones, por tanto, es que no se puede usar para resolver problemas donde no pueda adaptarse la situación a un sistema en donde los distintos estados del problema se representan como nodos. El paso de un nodo del problema a otro tiene un coste asociado en la arista que los conecta de forma que, para cada nodo, se pueda definir una heurística según el camino que se ha seguido para la resolución del problema. Cuanto más cerca se esté de la solución, menos será el valor de la heurística. Por lo tanto, esta heurística permite ordenar los mejores estados (nodos) para seguir buscando la solución a partir de ellos.

Los problemas que soluciona el algoritmo A* de forma general son de optimización, pero puede modificarse el problema de forma que el algoritmo A* pueda servir para obtener una solución aproximada a multitud de problemas diversos.

Por ejemplo, para los problemas de regresión se pueden adaptar los estados para que representen los enteros o decimales de las variables que entran en juego y la solución será más cercana cuánto menos error se produzca con los coeficientes de las variables elegidos. Este mismo proceso se puede usar en algoritmos de clasificación en donde la heurística tendrá un valor más bajo cuánto mejor clasifica el conjunto de coeficientes relacionados con las variables del problema.

Los problemas de clustering también pueden resolverse si se fija al inicio el número de clústers deseado. En este caso, el espacio de estados pasa a estar dividido en tantos conjuntos como elemento se meta en cada clúster y se va acercando a la solución óptima por medio de una heurística que maximice la distancia entre los conjuntos escogidos.

Con estos ejemplos se puede llegar a la idea de que cualquier problema de aprendizaje supervisado al que se le pueda fijar una distancia a la solución o se busque optimizar el error mínimo en la respuesta puede adaptarse al algoritmo A*, aunque es obvio que en algunos casos no es la mejor forma para resolver el problema y que en otros solo se puede llegar a una solución aproximada hasta cierto decimal (puesto que el espacio de estados es finito, así que las soluciones de los estados posibles prefijados estarán necesariamente en el conjunto de los números racionales en vez de en el de los reales).

Problemas que no se pueden resolver con este algoritmo son los de aprendizaje no supervisado, así como problemas en los que no se puede definir una distancia o error que minimizar o aquellos en los que no se puede delimitar el espacio de estados que generan los nodos.

Otros problemas que tampoco pueden resolverse con el algoritmo A* son lo que no tienen una solución óptima porque se pueden seguir generando soluciones continuamente, como la búsqueda de los números primos (porque no hay un final propiamente dicho) o la toma de decisiones en tiempo real porque la entrada va aumentando en cada caso y no es finita, cualidad necesaria para el algoritmo A* pues su espacio de estados debe estar definido antes de iniciar la resolución del problema.