Lo bueno es enemigo de lo mejor

¿Creéis que cualquier problema se puede resolver con Inteligencia Artificial?

En general existe un problema con los algoritmos iterativos o pathfinding, no solo con el algoritmo A*. 

Existe una familia de problemas que no son resolubles de forma exacta por un algoritmo polinominal (como pueda ser las visitas de un viajante a X ciudades diferentes) que tiene X factorial posibilidades. 

Con un X pequeño ya tienes tantas posibilidades que evaluarlas todas se hace muy costoso. Es por ello que se aplican los heurísticos como el A*, los algoritmos genéticos, los algoritmos de hormigas, etc. que exploran un número razonable de soluciones del espacio siguiendo una heurítica que no asegura una solución óptima, pero devuelve buenas soluciones en un tiempo asumible de cálculo. La mayoría de problemas reales se resuelven así (ejemplo, recogida de basuras). 

Sin embargo, si necesitamos una solución óptima y exacta, este tipo de aproximaciones no nos valen. 

Los algoritmos de exactos tienen un problema y es que con un problema pequeño funcionan bien, pero con problema ligeramente más complejos, el tiempo de cálculo no es asumible. 

Un ejemplo. 70 trabajadores para 70 puestos de trabajo tiene… exacto, 70 soluciones. Hace unos años se estimaba que necesitarías más de 3000 planetas tierra llenos de ordenadores conectados en red para resolver este problema en un año y evaluar todas las soluciones. 

La velocidad de computación avanza a gran velocidad y conforme llegue la supercomputación y la computación cuántica, se podrá dar un salto de calidad y calcular con algoritmos exactos problemas ligeramente complejos que así lo requieren.. pero por el momento lo mejor es aplicar estos algoritmos que no dan la solución exacta y asumir que, por ahora, la inteligencia artificial no se puede aplicar cuando lo que se requiere es una solución óptima. 

Gracias al profesor Óscar Cordon, de la Universidad de Granada que en varias ocasiones me ha explicado en conferencias este tipo de conceptos.

Gracias a la Dra. Juani Bermejo, gracias a la cual estoy entendiendo al fin lo que es la computación cuántica.