martes, 29 de septiembre de 2009

Caminando por la Mona Lisa

votar
¿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 |

5 comentarios:

Margarita Garcia Alonso dijo...

Aguayaaaaa, que me lanzas retos que me van a poner el cerebro echando humo. Interesantisimo, estoy completamente en el viaje. Miles de gracias.

Morgana dijo...

Ay mi madre, recuerdo cuando me lo dieron en la carrera...en Diseño y Análisis de Algoritmos...entre ese y el de pintar un mapa...la de tardes que pasé en la biblioteca:-)

Besitos!

Eufrates del Valle dijo...

Estimada Aguaya, esto es muy complicado para mi! LOL!

Angel Collado Ruíz dijo...

Aguaya necesito saber cuanto van a pagar por esto, ahora que casi estoy desempleado, me sobrará tiempo. un saludo angel

Gladys Castillo dijo...

muy bueno todo esto... voy a divulgarlo por mis colegas...saludos