la versión original de esta historia apareció en la revista Quanta.
Si desea resolver un problema complicado, a menudo resulta útil organizarse. Podrías, por ejemplo, dividir el problema en partes y abordar primero las partes más fáciles. Pero este tipo de clasificación tiene un costo. Es posible que acabes dedicando demasiado tiempo a poner las piezas en orden.
Este dilema es especialmente relevante para uno de los problemas más emblemáticos de la informática: encontrar el camino más corto desde un punto de partida específico en una red hasta todos los demás puntos. Es como una versión mejorada de un problema que debes resolver cada vez que te mudas: aprender cuál es la mejor ruta desde tu nuevo hogar al trabajo, al gimnasio y al supermercado.
“Los caminos más cortos son un hermoso problema con el que cualquier persona en el mundo puede identificarse”, afirmó Mikkel Thorup, científico informático de la Universidad de Copenhague.
Intuitivamente, debería ser más fácil encontrar el camino más corto a destinos cercanos. Entonces, si desea diseñar el algoritmo más rápido posible para el problema de los caminos más cortos, parece razonable comenzar encontrando el punto más cercano, luego el siguiente más cercano, y así sucesivamente. Pero para hacer eso, necesitas determinar repetidamente cuál es el punto más cercano. Ordenarás los puntos por distancia a medida que avanzas. Existe un límite de velocidad fundamental para cualquier algoritmo que siga este enfoque: no se puede ir más rápido que el tiempo que lleva ordenar.
Hace cuarenta años, los investigadores que diseñaban algoritmos de rutas más cortas se toparon con esta “barrera de clasificación”. Ahora, un equipo de investigadores ha ideado un nuevo algoritmo que lo rompe. No ordena y se ejecuta más rápido que cualquier algoritmo que lo haga.
“Los autores fueron audaces al pensar que podían romper esta barrera”, dijo Robert Tarjan, científico informático de la Universidad de Princeton. “Es un resultado sorprendente”.
La frontera del conocimiento
Para analizar matemáticamente el problema de los caminos más cortos, los investigadores utilizan el lenguaje de los gráficos: redes de puntos o nodos conectados por líneas. Cada enlace entre nodos está etiquetado con un número llamado peso, que puede representar la longitud de ese segmento o el tiempo necesario para atravesarlo. Generalmente hay muchas rutas entre dos nodos cualesquiera, y la más corta es aquella cuyos pesos suman el número más pequeño. Dado un gráfico y un nodo “fuente” específico, el objetivo de un algoritmo es encontrar el camino más corto hacia todos los demás nodos.
El algoritmo de caminos más cortos más famoso, ideado por el científico informático pionero Edsger Dijkstra en 1956, comienza en la fuente y avanza paso a paso. Es un enfoque eficaz, porque conocer el camino más corto hacia los nodos cercanos puede ayudarle a encontrar los caminos más cortos hacia los más distantes. Pero como el resultado final es una lista ordenada de caminos más cortos, la barrera de clasificación establece un límite fundamental sobre la velocidad a la que puede ejecutarse el algoritmo.