Un equipo de investigación estadounidense ha incorporado una mejora sustanciosa en la resolución del algoritmo de flujo máximo, una de las operaciones más comunes de la informática que se usa, por ejemplo, para diseñar redes de comunicaciones, analizar circuitos o procesar imágenes digitales.
La aplicación de esta mejora a una red como Internet podría resolver un problema cientos de veces más deprisa que todos los algoritmos utilizados hasta el momento.
El algoritmo de flujo maximal o flujo máximo es uno de los problemas más básicos de la informática. Se utiliza normalmente para planificar rutas aéreas, solucionar problemas de logística o crear redes de comunicaciones, además de ser un capítulo fundamental en todos los cursos de introducción a los algoritmos. Durante décadas constituyó un tema de investigación recurrente que ofrecía resultados importantes una o dos veces al año. Sin embargo, a medida que el problema empezó a ser ampliamente comprendido, el ritmo de las innovaciones comenzó a ralentizarse. Ahora, una nueva investigación del Instituto Tecnológico de Massachusetts (MIT), en colaboración con la Universidad de Yale y la Universidad del Sur de California, ha concluido con la primera gran mejora del algoritmo de flujo máximo en los diez últimos años, según un comunicado del MIT.
En términos generales puede decirse que este algoritmo se utiliza para calcular la cantidad máxima de “elementos” que pueden pasarse de un extremo a otro de una red, teniendo en cuenta las limitaciones de la capacidad de los enlaces de esa red. Esos “elementos” podrían ser, por ejemplo, los paquetes de datos que viajan a través de Internet o las cajas de mercancías que se trasladan por las carreteras. En estos casos las limitaciones en los enlaces harían referencia al ancho de banda de las conexiones a Internet o a la velocidad media del tráfico en las carreteras congestionadas.
De manera más técnica, el problema tiene que ver con lo que los matemáticos llaman grafos. Un grafo es un conjunto de puntos o vértices en el espacio, que están conectados por un conjunto de líneas o aristas. El esquema estándar de una red de comunicaciones es un grafo. En el problema de flujo máximo, uno de los vértices en el grafo es conocido como “fuente” (un nodo que no tiene arista entrante) y otro es designado “sumidero” (un nodo que no tiene aristas salientes) Cada una de las aristas tiene una capacidad asociada, es decir, una cantidad de “elementos” que pueden pasar por ellas.
La pregunta que trata de contestar el algoritmo es “¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?”. Es decir, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.
Más información en Tendencias 21
