¿Qué relación guarda Papá Noel con un grupo de matemáticos daneses? La respuesta es el clásico problema matemático de la ruta más corta de fuente única, que ha supuesto un quebradero de cabeza para los matemáticos durante medio siglo. Pero, además, este es el tipo de cálculo en los que se basan las aplicaciones a las que diariamente confiamos nuestros desplazamientos. El descubrimiento de un algoritmo que ofrece la solución de manera inmediata lo agradecerá Santa, porque eso facilitará su tradicional y esforzado reparto navideño.
Los denominados problemas de la ruta más corta engloban aquellos problemas de grafos con varios puntos, o nodos interconectados entre sí por segmentos con un valor asignado, y donde el reto es encontrar la ruta más corta entre uno de los nodos y alguno o varios de los demás nodos.
Pasatiempo 1: El clásico problema matemático de la ruta más corta
Dentro de esta categoría de problemas matemáticos se engloba el conocido como problema de la ruta más corta de fuente única, que aborda el caso concreto de encontrar las trayectorias más favorables entre el nodo de partida y todos los demás nodos que configuran la red o grafo.
En nuestros pasatiempos, el camino más favorable es el que otorga la menor puntuación final (sumando la puntuación de cada tramo); ese camino no es necesariamente el que consta de menos tramos o pasos. Podemos verlo en este ejemplo:
Solución: La ruta más favorable del punto 1 al 9 es la que hace el recorrido 1-2-5-3-8-9
Siguiendo la referencia del ejemplo anterior, define la mejor ruta para ir desde uno de los puntos rojos hasta el otro:
Formulado —al menos formalmente— en la década de los 1950, desde entonces el problema de encontrar un algoritmo definitivo que permita resolverlo de forma inmediata ha desafiado a matemáticos de todo el mundo.
¿Cómo este problema, en principio no demasiado complejo, ha resistido el asalto de algunas de las mentes más brillantes durante todo este tiempo? La clave radica en esa premisa de la ruta más favorable, que no necesariamente es la más corta. Una diferencia que deriva del denominado peso negativo, una forma de ponderar y cuantificar factores que favorecen (o penalizan) un trayecto frente a otro. Algo fácil de entender si pensamos en que cuesta mucho menos recorrer 1 Km en llano, que ascender 500 metros por una empinada ladera.
La clave detrás de la ruta óptima
Este es, precisamente, el tipo de problemas y cálculos en los que se basan aplicaciones que usamos en nuestro día a día —como por ejemplo Google Maps— para guiarnos a través de la ruta óptima dependiendo de la distancia, el coste económico o el tiempo.
Al tener en consideración el peso negativo, se complica la resolución del problema. Hasta ahora, se empleaban algoritmos que requerían un gran volumen de cálculo, lo que demoraba la solución. Pero eso está a punto de cambiar, ya que un equipo de matemáticos e informáticos de la Universidad de Copenhage ha descubierto un algoritmo que resuelve el problema de forma inmediata. La clave ha sido introducir en el cálculo una dimensión adicional para reflejar el peso negativo, convirtiendo de este modo el grafo bidimensional en una red tridimensional.
Una solución que llega justo a tiempo para su aplicación, por ejemplo, en un sector tan en auge como el de los vehículos eléctricos. Para este tipo de coches, que se recargan cuando viajan cuesta abajo, la pendiente es el factor fundamental para determinar la mejor ruta. Pero también será muy útil en otros ámbitos como el mercado bursátil o la compraventa de divisas. Y no deja de ser una herramienta de lo más agradecida cuando conduces un trineo cargado de regalos y tienes que trepar con un saco a cuestas para colarte por un montón de chimeneas.
Pasatiempo 2: Papá Noel y el problema de la ruta más corta de fuente única
Ayuda a Papá Noel a resolver su problema de la ruta más corta de fuente única. Es decir, encuentra las rutas más cortas para que Santa llegue desde la chimenea por la que ya asoma su gorro a cada una de las demás chimeneas. Y como reto adicional, descubre también la ruta más corta desde la chimenea inicial hasta E, pasando antes por A.
Pasatiempo 3: Papa Noel no siempre ve el lado negativo de andar trepando por chimeneas
Parece lo mismo pero no es igual. Porque ahora de lo que se trata es de encontrar la mejor ruta de fuente única desde la chimenea de la que emerge Santa, a cada una de las otras chimeneas. Y no te olvides del reto extra: descubrir la ruta más favorable desde la chimenea inicial hasta E pasando por A.
Soluciones
Comentarios sobre esta publicación