Caminando por la Mona Lisa

¿Recuerdan el post donde les conté cómo Robert Alsing "pintó" a la Mona Lisa con 50 polígonos semitransparentes? Bueno, pues hoy les traigo otra curiosidad sobre La Gioconda.

Fíjense bien en la siguiente imagen:


...y fíjense mejor aún en los detalles:


Pues se trata nada más y nada menos que de una instancia del Problema del Viajante creada con 100 mil ciudades. En este famosísimo problema de la optimización combinatoria el objetico es encontrar una ruta que pase por cada una de las ciudades una sola vez, partiendo de una ciudad inicial a la que se debe regresar al final, e intentando encontrar el camino más corto (como si un viajero saliera de su casa a caminar por cada una de ellas sin visitar ninguna dos veces, regresando a su casa otra vez una vez concluido el tour en el menor tiempo).

Para problemas pequeños la tarea no es tan complicada pero cuando el número de ciudades crece, es prácticamente casi imposible encontrar la ruta óptima (si fuéramos en auto, querríamos usar la menor cantidad de combustible posible, por ejemplo). Tanto es así que, el que logre encontrar una mejor ruta caminando sobre La Gioconda que les muestro arriba, puede ganarse incluso algún dinerito y todo: hasta ahora el camino más corto lo encontró el japonés Yuichi Nagata el 17 de marzo de 2009 pero al que encuentre otro mejor, le darán un premio.

Ahora, si pensaban ir probando cada una de las posibles rutas (fuerza bruta se llama esta manera de proceder) para quedarse al final con la mejor de todas, no se los aconsejo: miren el ejemplo que pone Wikipedia:

Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades.

¡Imagínense entonces para 100 mil ciudades!

Share |