El problema del viajante de comercio

El problema consiste en averiguar el ciclo hamiltoniano mínimo de un grafo ponderado no dirigido y completo, o dicho de otra manera más mundana, el camino más corto que tiene que recorrer un comercial para visitar sólo una vez cada uno de los lugares a los que tiene que ir y volver al punto de partida. Para resolverlo se proporcionan las distancias que hay entre todas las ciudades conectadas.

La solución se expresa dando el orden en el que el comercial tiene que visitar todas las ciudades, por lo que la cantidad de soluciones posibles será el factorial del número de ciudades. Por tanto el tiempo que tarda el ordenador en descubrir cual de todas es la mejor solución, crece factorialmente dependiendo del número de ciudades que tenga que visitar, de forma que si el ordenador fuera capaz de evaluar una solución por cada microsegundo, para 10 ciudades tardaría 3 segundos y para 20 ciudades 77.146 años.

En Junio de este año se concedió a Sanjeev Arora y Joseph S. B. Mitchell, uno de los premios más importantes en informática, el premio Gödel, por haber encontrado, por separado, la misma solución de tiempo polinómico a una variante del problema del viajante de comercio, en la que la distancia entre las ciudades es la distancia euclidea, es decir, suponiendo que las carreteras entre las ciudades vayan en línea recta.

Respecto al problema original, actualmente hay algoritmos voraces que son capaces de calcular, en un tiempo razonable (complejidad polinómica), una de las mejores soluciones, pero no la mejor, por lo que el problema no está todavía completamente resuelto.

Por si acaso alguien está pensando que eso ya lo hacen los GPS o aplicaciones como Google Maps, que sepa que se está equivocando, porque el GPS resuelve un problema distinto que consiste en encontrar el camino más corto entre dos ciudades. Para hacerlo, usa el algoritmo de Dijkstra, que es un algoritmo de complejidad cuadrática.

Así que si queréis ser famosos y ganar un premio Gödel o mejor un premio Turing (el equivalente al Nobel en informática), ya sabéis, sólo tenéis que encontrar un algoritmo de tiempo polinómico que resuelva este problema.