La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

La vuelta al mundo en 10 minutos (o en 156 días)

Posted by Carlos en octubre 24, 2007

El Degree Confluence Project es una curiosa iniciativa colaborativa consistente en visitar y tomar fotografías de todos los puntos del globo terráqueo con latitud y longitud enteras, esto es, de los puntos en los que se cruzan paralelos y meridianos correspondientes a un número entero (i.e., sin decimales) de grados de latitud o longitud respectivamente. Dado que la longitud puede tomar 360 valores enteros, y que la latitud puede tomar 181 (de 1º a 90º N o S, más el Ecuador), pero hay que descontar los polos en los que no hay variación de longitud, tenemos 360 x 179 + 2 = 64,442 confluencias. De éstas, una gran parte (más de 39,000) estarán en mitad de los mares u océanos, o se apiñarán cerca de los polos. Las restantes se hallan en tierra firme, o cerca de la costa, y definen una cuadrícula uniformemente distribuida por todos los continentes. Pueden considerarse en cierta medida como una muestra sistemática de lo que hay sobre la faz de la Tierra (de la tierra firme, claro).

Una vez identificados estos puntos, cabría considerar la tarea de dar una auténtica vuelta al mundo. No sólo circumnavegar el planeta, sino visitar cada pedacito de tierra firme del mismo, asumiendo estas confluencias como representativas de un área de ±0.5º de latitud/longitud (0.5º representa menos de 60 km en cualquiera de las cuatro direcciones principales en el Ecuador; en otros puntos la distancia E/W es todavía menor debido a la convergencia de los meridianos), lo que no parece descabellado. Tenemos entonces una instancia de nuestro bien conocido problema del viajante de comercio (TSP) con 16,189 “ciudades”. El vídeo inferior muestra un camino óptimo para recorrer todos estos puntos y volver al punto de partida. La longitud total del camino es de 1,628,716 km, lo que supone unos 156 días sin parar en una avioneta como la Mooney Acclaim.

La resolución del problema se ha realizado mediante Concorde, un paquete de optimización para el TSP que incorpora técnicas exactas tales como ramificación y corte, y heurísticas como el algoritmo de Lin-Kernighan. Es fácil ver que la solución óptima a una instancia del TSP sobre un plano no tendrá aristas que se crucen. La eliminación de estos cruces es precisamente una de las heurísticas más simples y efectivas para mejorar una solución obtenida mediante algún otro método. De hecho, es muy común incorporar una heurística de este tipo dentro de alguna otra metaheurística, e.g, un algoritmo genético. Estamos entonces hablando de algoritmos meméticos, a los que les dedicaremos algo más de tiempo más adelante.

Anuncios

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: