Solución al problema del camino más corto

Los algoritmos de caminos mínimos permiten estudiar costes de trayecto diferentes, como la distancia, el tiempo de viaje, el coste generalizado, etc.

MADRID, 15 Nov. (EUROPA PRESS) – Investigadores de la Universidad de Copenhague han logrado resolver el problema del camino más corto para una fuente única, un acertijo que ha dejado perplejos a los expertos durante décadas.

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.

"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 resolverlo", explica el profesor asociado Christian Wulff-Nilsen.

El objetivo del problema de la ruta más corta de fuente única es encontrar las rutas más cortas desde un nodo inicial dado a todos los demás nodos en una red.

Los algoritmos de caminos mínimos permiten estudiar costes de trayecto diferentes, como la distancia, el tiempo de viaje, el coste generalizado, etc. Este tipo de cálculo ya se usa en una amplia gama de aplicaciones y tecnologías de las que dependemos para orientarnos, como Google Maps nos guía a través de paisajes y ciudades, por ejemplo.

El año pasado, Wulff-Nilsen hizo otro avance en la misma área, que produjo 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.

El investigador cree que resolver el problema de la ruta más corta de fuente única podría allanar el camino para algoritmos que no solo ayuden a los autos eléctricos a calcular la ruta más rápida de A a B en un instante, sino que lo hagan de la manera más eficiente desde el punto de vista 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

El nuevo resultado resuelve el problema en casi la misma cantidad de tiempo que el algoritmo de Dijkstra, pero también permite pesos de borde negativos.

"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", dice Christian Wulff-Nilsen.

El investigador destaca que ya existen sistemas de cálculo tanto de moneda como de recorridos para coches eléctricos. Pero resolver el problema de la ruta más corta de fuente única ha permitido a los investigadores crear un algoritmo excelente que se vuelve casi imposible de superar en lo que respecta a la velocidad. Al mismo tiempo, su simplicidad hace que sea fácil de adoptar para las diversas necesidades de la sociedad.

La investigación está actualmente disponible en arXiv.