Cómo visitar dos millones de estrellas en el menor tiempo posible

El proyecto Gaia de la Agencia Espacial Europea tiene 2.079.471 estrellas catalogadas. ¿Podríamos encontrar una ruta para visitarlas todas, en el menor tiempo posible? Recientemente, un grupo de investigadores ha dado con un camino que se acerca mucho a la respuesta. Este tipo de cuestiones se estudian en un área de las matemáticas conocida como optimización matemática o programación matemática, de gran importancia no sólo teórica sino también por sus aplicaciones a la vida real y por sus ramificaciones en otras disciplinas.

Se trata de identificar, entre todas las posibilidades para resolver un problema, la mejor, respecto a un criterio establecido. Nos hacemos este tipo de preguntas cuando elegimos compañía telefónica –queremos elegir la que nos ofrezca un servicio más adecuado a un precio más bajo–, cuando vamos a hacer recados por nuestro barrio –queremos desplazarnos gastando la menor energía y tiempo posible– o al planificar un largo paseo por el universo. En todos los casos, escogemos entre todas las posibilidades existentes –el conjunto de compañías telefónicas, las diversas rutas por nuestro barrio o por el cosmos– para optimizar una cantidad –dinero o tiempo–.

El problema del paseo estelar es un ejemplo del problema del viajante de comercio (del inglés travelling salesmen problem), uno de los más importantes del campo. Se parte de una red de ciudades, interconectadas entre ellas por carreteras. A partir de ella definimos un grafo, es decir, una estructura matemática abstracta que contiene objetos –los vértices del grafo y relaciones entre los mismos –las aristas del grafo–. En nuestro caso, los vértices serían las ciudades y habría una arista entre dos ciudades si estas se encuentran conectadas por una carretera. Además, incluiremos la distancia existente entre las ciudades conectadas dando un peso a las aristas, es decir, un valor que se corresponde a los kilómetros de separación.

El problema del paseo estelar es un ejemplo del problema del viajante de comercio, uno de los más importantes del campo

Ahora, un viajante busca la manera de visitar todas las ciudades sin repetición, acabando el recorrido en la ciudad inicial y utilizando el menor número posible de kilómetros. En lenguaje matemático, la cuestión consiste en encontrar lo que se denomina un ciclo –un grafo que empieza y acaba en el mismo punto– hamiltoniano –que solo pasa una vez por cada vértice– en el grafo bajo estudio, de tal forma que la suma de pesos de sus aristas sea el más pequeño posible.

Para un número pequeño de ciudades la cuenta la podemos hacer a mano, pero la complejidad del problema aumenta rápidamente en función de las ciudades que estemos considerando. Tomando más de 20 ciudades y suponiendo que el número de conexiones es elevado –el número máximo de carreteras en este caso sería 190, en el supuesto que hubiera una carretera directa entre cualquier par de localidades–, el problema algorítmico de calcular todas las rutas se convierte en una cuestión intratable. De hecho, es bien conocido que se trata de un problema algorítmico difícil: encontrar la solución, incluso utilizando ordenadores potentes, necesita de tanto tiempo de cálculo que se considera impracticable.

Sin embargo, los métodos modernos permiten encontrar soluciones casi-óptimas en tiempos de cálculo razonables. Estas son soluciones del problema que no minimizan el número de kilómetros, pero que se acercan mucho a ello, es decir, su diferencia con respecto al óptimo es pequeña. En dicha búsqueda se utilizan una ámplia variedad de técnicas matemáticas, que incluyen el uso de heurísticas, la estadística, la probabilidad y el análisis.

El estudio de este problema motivó el desarrollo de muchas de las ideas centrales en esta disciplina. El trabajo fundamental, del año 1954, es Solution of a large-scale travelling-sales problem. En él, George Dantzig –padre del algoritmo–, Delbert R. Fulkerson y Selmer Johnson pusieron los cimientos al estudio formal del problema del viajante y, de paso, dieron forma a toda la disciplina de la programación matemática (que ya recibió un gran impulso durante la II Guerra Mundial). Como dato curioso, los autores estudiaron el problema para 48 ciudades de Estados Unidos, y obtuvieron una ruta para visitarlas a todas siguiendo un ciclo hamiltoniano.

Actualmente y gracias a la potencia algorítmica de los computadores, se pueden estudiar sistemas muchísimo más complejos que en los años cincuenta y, sorprendentemente, obtener resultados muy cercanos al valor óptimo. Es el caso del reciente trabajo de Bill Cook (Universidad de Waterloo, Canadá) y Keld Helsgaun (Universidad Roskilde, Dinamarca): han encontrado, mediante técnicas de optimización matemática, la ruta más corta para visitar 2.079.471 estrellas indexadas por el proyecto Gaia de la Agencia Espacial Europea. El estudio, que puede encontrarse aquí, encuentra una ruta para visitar todas estas estrellas en... ¡94.208.157,5 años luz! Y que además está muy cerca de ser la solución óptima. Esta aplicación reciente e impresionante muestra la potencia matemática de las ideas de esta disciplina.

Juanjo Rué es profesor agregat de la Universidad Politécnica de Cataluña y miembro de la Barcelona Graduate School of Mathematics

Café y Teoremas es una sección dedicada a las matemáticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en la que los investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: “Un matemático es una máquina que transforma café en teoremas”.

Edición y coordinación: Ágata A. Timón García-Longoria (ICMAT)

Puedes seguir a MATERIA en Facebook, Twitter, Instagram o suscribirte aquí a nuestra newsletter