Un algoritmo encuentra la línea recta más larga navegable sin tocar tierra

Arxiv.org

En 2012, surgió un curioso debate en Reddit, donde el usuario Kepleronlyknows publicó un mapa del mundo que mostraba el camino navegable más largo en línea recta sobre el agua sin tocar tierra. La ruta comenzaba en Pakistán y daba un largo rodeo por debajo de África y América del Sur hasta llegar al este de Rusia. La publicación generó un gran debate, con muchos usuarios preguntándose si la premisa era correcta: ¿podría haber una ruta diferente en línea recta sobre el agua que fuera más larga pero ininterrumpida por tierra de cualquier tipo? Al mismo tiempo, surgió la misma pregunta sobre la Tierra: ¿cuál es la ruta más larga en línea recta ininterrumpida por lagos o mares?

Para los cartógrafos las respuestas tendrían que seguir un gran círculo: un arco a lo largo de uno de los muchos círculos imaginarios más grandes que se pueden dibujar alrededor de una esfera. Una forma de resolver este problema es midiendo la longitud de cada posible camino en línea recta sobre tierra y agua. Esto llevaría mucho tiempo y no seróa útil: un mapa del mundo con una resolución de 1.85 kilómetros y más de 230 mil millones de círculos válidos, cada uno consistente en 21.600 puntos individuales, lo que hace un total de más de cinco billones de puntos a considerar.

Una respuesta más sencilla ha llegado de la mano de Rohan Chabukswar, del Centro de Investigación Tecnológica de Irlanda, y Kushal Mukherjee, de IBM Research (India), que han desarrollado un algoritmo para calcular el camino más largo en línea recta en tierra o mar, que explota una técnica conocida como branch y bound. Funciona considerando soluciones potenciales como ramas en un árbol. En lugar de evaluar todas las soluciones, el algoritmo, publicado en Arxiv.org, comprueba una rama tras otra, una técnica conocida como ramificación, mientras que otra, llamada delimitación, reduce significativamente la tarea. Cada rama contiene un subconjunto de soluciones potenciales, una de las cuales es la solución óptima. El truco es encontrar una propiedad de los subconjuntos que dependa de lo cerca que estén las soluciones de la óptima.

Chabukswar y Mukherjee han perfeccionado un truco que consiste en encontrar una propiedad matemática de las rutas de gran círculo que limite la solución óptima para las trayectorias en línea recta. Luego crean un algoritmo que usa esto para encontrar la ruta más larga. El algoritmo devolvió la ruta más larga en aproximadamente 10 minutos de cálculo para la trayectoria del agua, y 45 minutos de cálculo para la ruta terrestre en una computadora portátil estándar. Resulta que Kepleronlyknows estaba en lo cierto: el camino más largo en línea recta sobre el agua comienza en Sonmiani, Balochistán, Pakistán, pasa entre África y Madagascar y luego entre la Antártida y Tierra del Fuego en América del Sur, y termina en el distrito de Karaginsky, Krai de Kamchatka, en Rusia. Tiene 32,089.7 kilómetros de largo.

Por su parte, el camino más largo sobre tierra se extiende desde cerca de Jinjiang, Fujian, en China, se entreteje a través de Mongolia, Kazajstán y Rusia, y finalmente llega a Europa para terminar cerca de Sagres en Portugal. En total, la ruta pasa por 15 países en 11.241.1 kilómetros.

Beatriz de Vera
Esta noticia ha sido publicada originalmente en N+1, ciencia que suma

Sobre N+1: Es la primera revista online de divulgación científica y tecnológica que permite la reproducción total o parcial de sus contenidos por medios de comunicación, bloggers e influencers, realizando la mención del texto y el enlace a la web: “Esta noticia ha sido publicada originalmente en la revista N+1, ciencia que sumawww.nmas1.org”.​​​​​​

Suscríbete

Déjanos tu mail para recibir nuestro boletín de noticias

La confirmación ha sido enviada a tu correo.