Encuentran solución al problema del camino más corto
Investigadores de la Universidad de Copenhague encuentran un algoritmo “que resuelve el problema en un tiempo prácticamente lineal” y permite pesos negativos.
Un grupo de investigadores de la Universidad de Copenhague (Dinamarca) ha encontrado la solución a un acertijo que ha dejado perplejos a los expertos durante décadas. El objetivo del problema de la ruta más corta de fuente única es encontrar las rutas más cortas entre dos vértices o nodos para que la suma de los pesos de las aristas que constituyen el recorrido sea la mínima.
En el caso planteado, los vértices son poblaciones (los nodos son, por ejemplo, ciudades) y los pesos de las aristas es el tiempo que empleamos en desplazarnos de un punto a otro. “Descubrimos un algoritmo que resuelve el problema en un tiempo prácticamente lineal, de la manera más rápida posible. Es un problema algorítmico fundamental que se estudia desde la década de 1950 y se enseña en todo el mundo. Esta fue una de las razones que nos impulsó a resolver”, explica el profesor asociado Christian Wulff-Nilsen.
La nueva fórmula hallada resuelve el problema en casi la misma cantidad de tiempo que el algoritmo de Dijkstra, pero también permite pesos de borde negativos. Ya existen algoritmos de caminos mínimos que permiten estudiar costes de trayecto diferentes, como la distancia, el tiempo de viaje, el coste generalizado, etc. Estos se usan en una amplia gama de aplicaciones y tecnologías como Google Maps, que nos guía y orienta a través de paisajes y ciudades.
El año pasado, Wulff-Nilsen hizo otro avance con un resultado que abordaba cómo encontrar el camino más corto en una red que cambia con el tiempo. Su solución al acertijo reciente se basa en ese trabajo. Resolver el acertijo “puede reducir el consumo de batería de los coches eléctricos y hacer la vida más difícil para los especuladores de divisas en el futuro”, informa la universidad en un comunicado.
Pesos negativos y ahorro energético
“Estamos agregando una dimensión que los algoritmos anteriores no tienen. Esta dimensión nos permite ver lo que llamamos pesos negativos. Un ejemplo práctico de esto puede ser con referencia a las colinas en una red de carreteras, lo cual es bueno saber si tienes un auto eléctrico que se carga mientras viajas cuesta abajo”, explica Wulff-Nilsen.
En el problema de la ruta más corta de fuente única, la red se representa como un grafo formado por nodos y conexiones entre ellos, llamados aristas. Cada borde tiene una dirección (por ejemplo, esto se puede usar para representar carreteras de un solo sentido), así como un peso, que expresa lo caro que es viajar a lo largo de ese borde. Si todos los pesos de los bordes son no negativos, el problema se puede resolver en un tiempo prácticamente lineal con un algoritmo clásico de Dijkstra, que pretende encontrar el camino de la longitud mínima de un vértice origen al resto de los vértices del grafo.
“En principio, el algoritmo podría usarse para advertir a los actores, como los bancos centrales, si los especuladores están especulando sobre la compra y venta de varias monedas. Mucho de esto sucede usando computadoras hoy en día. Pero debido a que nuestro algoritmo es tan rápido, podría ser capaz de para ser utilizado para detectar lagunas antes de que sean explotadas”, indica Christian Wulff-Nilsen.