Tecnología y Social Media 


Problema del viajante

El problema del viajante es uno de los problemas más famosos de la matemática computacional. Pertenece a una serie de problemas que parecen tener una fácil solución pero en la práctica presentan una gran dificultad. Este problema en concreto ha sido muy estudiado por sus múltiples aplicaciones en la optimización de recursos, tanto en el campo empresarial (logística de transporte) como en el de la robótica (desplazamientos que se realizan al hacer un circuito impreso).

Problema del viajante

Representación mediante grafo del problema del viajante

Plantea cómo un viajante podría empezar y terminar en una ciudad concreta, pasando por todas las ciudades que están en su mapa una sola vez, y por la mínima ruta posible. A priori la solución puede parecer sencilla, solo habría que probar cuál de las posibles combinaciones de rutas sería la óptima, lo que llamamos por “fuerza bruta”. La dificultad aparece cuando el número de ciudades es elevado, las posibles combinaciones aumentan de manera exponencial.

Los problemas cuyo aumento de datos hacen que el tiempo de resolución (o computación) aumente exponencialmente, se les llama NP-completos. Por tanto, el problema del viajante es NP-completo, ya que un aumento de ciudades eleva exponencialmente el número de combinaciones posibles y, debido a esto, el número de pruebas que hay que realizar para ver cual es la combinación óptima, incrementando exponencialmente el tiempo de resolución. Aquí estriba su impedimento en la práctica, si el número de ciudades es elevado no existe computadora a nuestro alcance capaz de computar (o solucionar) el problema en un tiempo razonable.

Pongamos un ejemplo, imaginemos un problema del viajante con 20 ciudades, las posibles combinaciones de estas ciudades serían más de 2,4 trillones (20 factorial, o 20!). Supongamos que tenemos el mejor microprocesador que hay en el mercado, lo que nos posibilita un mayor número de instrucciones por segundo. En este caso vamos a imaginar que tenemos un Intel Quad Core (cuatro núcleos) con unas 49 millones de instrucciones por segundo (49.000 MIPS). En el mejor de los casos, y siendo conscientes que esto no es así en la realidad, consideremos que necesitamos una sola instrucción por cada combinación y nuestro procesador trabaja exclusivamente en el problema del viajante. Con una sencilla cuenta de división (combinaciones divididas entre MIPS) podemos darnos cuenta que se resolvería en más de 1.500 años.

Por suerte, a continuación tenemos una solución al problema de manera lineal (en notación matemática O(1)), es decir, que un incremento en los datos no aumente la complejidad del problema:

Solución problema del viajante

 

Imagen | Representación mediante grafo del problema del viajante, Solución al problema del viajante (broma)

RELACIONADOS