En las últimas semanas se ha producido un gran debate en foros y agregadores como Reedit por determinar la distancia más larga de nuestro planeta tanto por tierra como por mar. ¿Por qué no se ha podido descubrir antes? Se trata de un problema de optimización causado por la presencia de islas, lagos y la naturaleza de las costas. Hoy te presentamos un método para calcular estas dos rutas usando el algoritmo de branch and bound.

Estos métodos de algoritmos conocidos como “ramificación” y “poda” constituyen una variante del Backtracking pero mejorado sustancialmente. Este se aplica mayoritariamente a problemas de optimización. Esta técnica se suele representar como un árbol de soluciones, donde cada una de las ramas nos lleva a una posible solución. La característica de esta técnica, respecto a otras, es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas para no seguir malgastando recursos y procesos en los casos en los que se alejen de una solución óptima.

Utilizando esta técnica, el Centro de Investigación United Technologies y el IBM Research en India han desarrollado un algoritmo para calcular el camino más largo en línea recta por tierra y por mar.

Rohan Chabukswar, físico del United Technologies Research Centre Ireland en Cork, junto a Kushal Mukherjee, ingeniero de IBM Research India en Nueva Delhi, comenzaron a investigar con datos del modelo ETOPO1 Global Relief de la NASA sobre la superficie de la Tierra, en el que se muestra todo el planeta con una resolución espacial de, aproximadamente, 1,8 kilómetros.

Hasta 15 países en 11.241,1 kilómetros

Para dar con la solución se redujo sustancialmente el volumen de trabajo de campo recurriendo únicamente a las matemáticas. A medida que el algoritmo se ejecutaba, los subconjuntos se analizaban y se reducían las posibilidades hasta encontrar una solución. Por mar la línea discurría entre la costa de Pakistán hasta las costas rusas, una distancia de, aproximadamente, 32,089.7 kilómetros. Mientras que el camino más largo por tierra se extendía cerca de Jinjiang en Fujian; a través de Mongolia, Kazajstán y Rusia; para, finalmente, llegar a Europa y terminar cerca de Sagres. Una ruta que recorre hasta 15 países en 11.241,1 kilómetros.

Fuente: CHABUKSWAR ET AL. Adapted by J. You / SCIENCE MAG.

La entrada Un algoritmo encuentra el camino más largo en línea recta para atravesar la Tierra aparece primero en Blogthinkbig.com.