Pensamientos computables - www.pensamientoscomputables.com
35

El problema del viajante de comercio

Publicado el: 05/10/2010
El viajante de comercio es un problema computacionalmente muy costoso de calcular. Su complejidad es exponencial y, por lo tanto, entra en la categoría de los problemas que no se pueden resolver en tiempo polinómico, lo que en otras palabras, quiere decir, que un ordenador actual puede tardar milenios en hallar la solución al problema. Si se pudiese obtener el resultado en menos tiempo sería útil para comerciales, agencias de transporte, carteros, repartidores, infinidad de procesos de fabricación, análisis del ADN y otras muchas situaciones.

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.

Pensamientos (1): Ver comentarios Comentar
Categorías:

Comparte:

Copia y pega en tu página:

Comparte
Escribe tus pensamientos computables

Respondiendo a los siguientes comentarios:

Para comprobar que eres un humano responde correctamente:

Esta pregunta no me gusta, ¡cambialá!

Ninguno de estos datos será almacenado.

(Escribe el correo electrónico)

Campo obligatorio.

(Escribe el correo eléctronico o los correos electrónicos separados por comas)

Campo obligatorio.

Para comprobar que eres un humano responde correctamente:

Esta pregunta no me gusta, ¡cambialá!

Pensamientos
Daiatron en Google+