Qué tipos de problemas no podrían ser resueltos por medio del algoritmo A*

                PROBLEMAS QUE NO PODRÍAN SER RESUELTOS POR ALGORITMO A*

En la búsqueda de soluciones a un problema la Inteligencia Artificial usa diferentes algoritmos.

El algoritmo A* usa infomación heurística, basada en la experiencia y en el conocimiento lo mas amplio posible del problema.

Un heurístico lo definimos como un conjunto de reglas que permite escoger aquellas ramas del espacio de estados que, presumiblemente, y en base al conocimiento amplio del problema, lleva a una solución aceptable.

La heurística usualmente propone estrategias (heurísticas) que guían el descubrimiento. Se trata de procedimientos simples, a menudo basados en el sentido común o la intuición, que se supone ofrecerán una buena solución (aunque no necesariamente la óptima) a problemas difíciles, de un modo fácil y rápido.  

El procedimiento consiste sencillamente en proponer unos algoritmos que satisfagan la solución del problema, de suerte que  sea posible avanzar.

Es interesante la utilización de algoritmos heurísticos para resolver un problema:

Cuando no existe un método exacto o éste requiere mucho tiempo de cálculo o memoria

Cuando no se necesita la solución óptima

Cuando los datos son poco fiables

Cuando limitaciones de tiempo y espacio(para almacenamiento de datos) obliguen al empleo de métodos de rápida respuesta aún a costa de la precisión

Los heurísticos pueden fallar, pues están basados en la experiencia o en la intuición.
Con lo cual un heurístico puede llevar a un algoritmo de búsqueda hacia una solución óptima, subóptima, o fallar y no encontrar ninguna solución.

Para incorporar la información heurística al algoritmo se realiza una función de evaluación: un medio de clasificar los nodo candidatos y determinar cuál está con mayor probabilidad en el mejor camino que conduzca a la solución del problema.
Se valora no sólo la heurística, sino también el coste de un operador. Se busca el camino de menor costo siempre que se cumplan unas determinadas condiciones.

Ir escogiendo como siguiente estado a explorar aquel que minimiza la heurística y el coste ha dado lugar al algoritmo A*,

Propuesto en 1968 por Petr E. Hart, Nils J. Nilsson y Bertram Rafael, ha sido una de las grandes ideas de la Inteligencia Artificial. Este es el algoritmo que se utilizó Deep Blue, de IBM,  para vencer al ajedrez a Grary Kasparov en 1997, por primera vez.

El rendimiento de los algoritmos de búsqueda heurístia depende de la calidad de la función heurística. El mayor problema del Algoritmo A* es el espacio requerido en la máquina para su ejecución. Como tiene que almacenar todos los posibles nodos de cada estado, la cantidad de memoria que requerirá será exponencial al tamaño del problema.
Por ello se han propuesto diferentes variaciones de este algoritmo, como RTA*, IDA*o SMA*.

Hay problemas que no podrían ser resueltos por medio del algoritmo A*.
Son aquellos problemas que requieren una solución exacta. Problemas matemáticos, sobre todo, tanto en su aplicación dentro de la lógica y la matemática,  como en su utilización en la física, química, astronomía... Las que requieren soluciones robustas.

La búsqueda de repuestas y soluciones exactas, y las de medidas e indicadores exactos, que no se aplican en problemas reales en el mundo, por su carácter complejo, con rasgos de no-linealidad, sorpresa, emergencia, equilibrios inestables...

Los problemas de la sociedad humana ya no se tratan como problemas que requieran soluciones exactas, sino probabilísticas, más flexibles,

Los problemas matemáticos se pueden clasificar con respecto a su abordaje desde la Inteligencia Artificial en "problemas indecidibles", que no se pueden resolver mediante algoritmos, y "problemas decidibles", que cuentan al menos con un algoritmo para abordarlo.
Los problemas decidibles se subdividen en "problemas intratables", problemas que disponen de algoritmos para su solución, pero son inabordables para un computador por el elevado número de operaciones que realizar para resolverlos, con lo cual no es factible su resolución.
Y "problemas tratables", aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.