El Algoritmo A* y sus limitaciones

     

     Dentro de los algoritmos que hemos tratado en la asignatura vemos que hay dos grupos bien diferenciados: los de búsqueda informada y los no informados. En los primeros la gran ventaja y diferencia reside en que dentro de la información que manejan se encuentra la información sobre características del medio, una información adicional que les sirve para llegar antes a la resolución del problema . En el caso del  Algoritmo A* además se introduce el manejo de información heurística, que es la basada en una regla o conjunto de reglas que permiten seleccionar aquellas rutas que presumiblemente llevan hacia una solución aceptable del problema,  manejando la información basada en la experiencia y las características particulares de cada caso.

El hecho de que los algoritmos A* manejen información heurística hacen que puedan fallar por la naturaleza propia de este tipo de información ya que está basada en la experiencia e intuición. Este tipo de información no es completa ya que en muchos casos está limitada a la información que proporciona el sistema en el momento en el que se está resolviendo el problema.

Debido a lo expuesto anteriormente podemos inferir que un algoritmo que maneje heurísticos puede llegar a una resolución no óptima del problema o incluso no llegar a solucionarlo. En este caso ¿qué problemas podrían nos ser resueltos por un algoritmo A*? . En primer lugar hemos de pensar en aquellos problemas en los que no es sencillo encontrar una función heurística.  En determinados problemas puede estar bien definida la función heurística pero en otros casos puede no ser tan clara implicando una mayor complejidad computacional. El hecho de que se incremente la complejidad computacional hace que sea necesario aumentar la cantidad de  memoria, siendo este uno de los problemas fundamentales: debido a que hay que almacenar la información sobre todos los posibles pasos en la resolución del problema,  la cantidad de memoria necesaria puede ser exponencial con respecto al tamaño del problema. Volvemos de este modo a incidir en lo anterior, problemas con una heurística bien definida permitirán que el problema se vaya resolviendo linealmente pero aquellos problemas con una heurística de “baja calidad” harán  que la complejidad vaya aumentando exponencialmente hasta que se pueda llegar al caso de no resolución o resolución no óptima del problema. 

Esto pondrá el límite respecto a cuándo podemos obtener una solución óptima para un problema. En los problemas  para los que no podemos encontrar una función heurística suficientemente buena, deberemos usar algoritmos que no busquen el óptimo, pero que nos garanticen que nos acercaremos lo suficiente a él para obtener una buena solución.