Manoj Gupta supera un límite de 1996 en caminos más cortos

Manoj Gupta, del Indian Institute of Technology Gandhinagar, ha desarrollado un algoritmo que supera una limitación presente en la informática desde 1996. El método ofrece aproximaciones más precisas de los caminos más cortos entre puntos cercanos y no aumenta el tiempo de cálculo.

Calcular caminos más cortos es una tarea diaria para los ordenadores. Dependen de ella las aplicaciones de navegación, los sistemas de transporte y la infraestructura de internet. El problema se complica mucho cuando hay que hallar las distancias entre todos los pares posibles de puntos de una red enorme, conocido como APSP (All-Pairs Shortest Paths). Una red es aquí un conjunto de puntos conectados entre sí, que pueden representar ciudades, ordenadores, estaciones de tren o incluso neuronas.

El punto débil del método de 1996

Determinar con exactitud todas las rutas en una red grande y densa requiere enormes recursos de cómputo. Por eso los investigadores buscan desde hace tiempo métodos fiables que no obliguen a analizar cada camino. En 1996, Dor, Halperin y Zwick presentaron un algoritmo que garantiza una estimación no superior al doble de la distancia real más corta, una aproximación de factor 2.

Sin embargo, la garantía funcionaba sobre todo para puntos muy alejados. En conexiones cortas el error podía ser mayor: una ruta real de dos enlaces podía estimarse en cinco, superando el margen del doble.

La aportación de Gupta

Gupta mejora la forma de elegir los puntos usados en la estimación. El enfoque anterior se basaba en un conjunto relativamente pequeño de vértices representativos. El nuevo algoritmo emplea un muestreo multiescala, es decir, analiza la estructura de la red en varios niveles en lugar de depender de un único grupo de puntos.

Así puede tener en cuenta conexiones más cortas que antes pasaban inadvertidas. Lo más importante es que la mejora de precisión no incrementa la complejidad computacional global: se obtienen resultados más fiables sin alargar el tiempo de ejecución.

El avance podría ser relevante en telecomunicaciones, transporte, redes sociales y sistemas de inteligencia artificial, donde estimar distancias de forma rápida y fiable ayuda a analizar dependencias y optimizar sistemas completos.