Tendencias21
Importante mejora de uno de los algoritmos básicos de la informática

Importante mejora de uno de los algoritmos básicos de la informática

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. Por Elena Higueras.

Importante mejora de uno de los algoritmos básicos de la informática

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.

De grafos a matrices

Tradicionalmente, el procedimiento para obtener el flujo máximo de una red ha consistido en seleccionar cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria. Y hacer esto repetidas veces, ya que en cada una de ellas solo se considera un camino a través del grafo. Sin embargo, la mejora introducida por el equipo estadounidense permite seleccionar, de una manera más inteligente, el orden en que estos caminos son explorados para reducir el tiempo en que se resuelve el problema.

El grupo de investigación, compuesto por Jonathan Kelner, profesor de Matemáticas Aplicadas en el MIT, Alexander Mandry, estudiante de posgrado en el Laboratorio de Informática e Inteligencia Artificial del MIT, el matemático Paul Christiano y los profesores Daniel Spielman y Shanghua Teng, de la Universidad de Yale y la USC respectivamente, ha adoptado un enfoque totalmente nuevo para el problema del flujo máximo. Su innovación consiste en representar el grafo como una matriz, en la que a cada nodo del grafo se le asigna una fila y una columna de la matriz. El número donde una fila y una columna coinciden representa la cantidad de cosas que pueden ser transferidas entre dos nodos.

En la rama de las matemáticas conocida como álgebra lineal, una fila de una matriz también se puede interpretar como una ecuación matemática. Las herramientas del álgebra lineal permiten la solución simultánea de todas las ecuaciones incorporadas por todas las filas de una matriz. Si se modifican los números de la matriz en repetidas ocasiones, se modifican las ecuaciones y los investigadores pueden evaluar eficazmente todo el grafo a la vez. Este enfoque, que Kelner tiene previsto describir hoy en una charla en el MIT, resulta ser más eficiente que probar caminos uno por uno.

Para demostrarlo, los investigadores plantean en el comunicado los resultados obtenidos con la siguiente fórmula: Si N es el número de nodos en un gráfico y L es el número de enlaces entre ellos, la ejecución de los algoritmos de flujo más rápidos hasta ahora era proporcional a (N + L)^(2/3). Sin embargo, la ejecución del nuevo algoritmo es proporcional a (N + L)^(4/3). Para una red como Internet, que tiene cientos de miles de millones de nodos, el nuevo algoritmo podría resolver el problema de flujo máximo cientos de veces más rápido que su predecesor.

En el mundo real estos grafos modelan redes de transporte y comunicación. Pero para Kelner, las posibilidades de aplicaciones prácticas del nuevo algoritmo van mucho más allá, desde el análisis de circuitos hasta el alineamiento de secuencias de ADN, pasando por el procesamiento digital de imágenes, entre otras.

La viabilidad inmediata del algoritmo, sin embargo, no es lo que más impresiona a John Hopcroft, profesor de Ingeniería y Matemática Aplicada en el centro de investigación de IBM en la Universidad de Cornell y ganador del Premio Turing, el más importante en Informática: «Mi predicción es que este marco particular va a ser aplicable a una amplia gama de problemas diferentes. Cuando hay un gran avance de esta naturaleza, por lo general, se suele formar una especialidad y en cuatro o cinco años, comienzan a surgir resultados interesantes”.

RedacciónT21

Hacer un comentario

RSS Lo último de Tendencias21

  • Oleada cósmica: cinco asteroides rozan la Tierra en solo cuatro días 3 junio, 2025
    Cinco rocas espaciales pasarán a millones de kilómetros de nuestro planeta en apenas cuatro días, con el 4 de junio como jornada clave. No representan peligro, pero ofrecen una oportunidad única para la ciencia.
    Redacción T21
  • Estados Unidos crea una "máquina del tiempo científica", capaz de condensar en días décadas de investigación 3 junio, 2025
    El próximo superordenador Doudna, que Estados Unidos tendrá operativo en 2026, está diseñado para ser el catalizador de una nueva era de descubrimientos, transformando la forma en que abordamos desde los misterios del cosmos hasta las complejidades de la vida misma.
    EDUARDO MARTÍNEZ DE LA FE/T21
  • Se revela una estructura oculta al borde del Sol 3 junio, 2025
    La atmósfera exterior del Sol, conocida como corona solar, ha revelado recientemente detalles asombrosos gracias a avances en óptica adaptativa y técnicas de observación de alto contraste. Un equipo internacional de científicos ha logrado capturar las imágenes más nítidas hasta la fecha de la corona solar, mostrando fenómenos como las “gotas de lluvia” solares y […]
    Redacción T21
  • Dormir mal puede estar relacionado con problemas en la audición 2 junio, 2025
    Una investigación realizada en China y otros estudios recientes sugieren que las patologías del sueño, como el insomnio, el trastorno del movimiento periódico de las extremidades y la apnea del sueño podrían estar relacionados con la pérdida auditiva.
    Pablo Javier Piacente / T21
  • Un tatuaje electrónico puede leer los niveles de estrés 2 junio, 2025
    Un nuevo tatuaje electrónico portátil y ultradelgado que se coloca en la frente de forma no invasiva monitorea de manera inalámbrica la actividad cerebral, rastrea la carga cognitiva en tiempo real y potencialmente predice la fatiga mental y el estrés antes que se haga evidente.
    Pablo Javier Piacente / T21
  • ¿El próximo Einstein será un algoritmo? Nace la primera científica artificial que genera conocimiento 2 junio, 2025
    Una inteligencia artificial ha concebido, ejecutado y escrito una investigación original que ha sido aceptada en ACL 2025, uno de los foros científicos más prestigiosos del mundo. Zochi es la primera científica artificial reconocida por la élite.
    EDUARDO MARTÍNEZ DE LA FE/T21
  • Crean un "hormigón viviente" que se repara a sí mismo 2 junio, 2025
    Un equipo de investigadores ha desarrollado un tipo de concreto que puede curarse a sí mismo aprovechando el poder del liquen sintético. Mejora notablemente intentos anteriores de producir hormigón "vivo" hecho con bacterias, ya que el nuevo material logra ser completamente autosuficiente.
    Redacción T21
  • El eco cuántico del cerebro: ¿estamos entrelazados con nuestros pensamientos? 2 junio, 2025
    El entrelazamiento cuántico, la "acción fantasmal a distancia" que tanto intrigó a Einstein, podría no ser solo una rareza del microcosmos, sino que tendría un eco medible en los procesos cognitivos inconscientes mediante un aparente fenómeno “supercuántico”.
    EDUARDO MARTÍNEZ DE LA FE/T21
  • Un enorme desierto en Asia se está transformando en un vergel gracias al cambio climático 1 junio, 2025
    Los hallazgos de un nuevo estudio muestran que la ecologización del desierto de Thar ha sido impulsada principalmente por más lluvias durante las temporadas de monzones de verano, un aumento del 64% en las precipitaciones en general por el cambio climático y, en segundo lugar, por la infraestructura de riego que lleva el agua subterránea […]
    Pablo Javier Piacente / T21
  • La NASA está observando una enorme y creciente anomalía en el campo magnético de la Tierra 31 mayo, 2025
    La NASA está haciendo un seguimiento detallado de la "abolladura" o "bache" en el campo magnético terrestre descubierta en 1961, que crece rápidamente y podría ser el preludio de una inversión geomagnética: ocurre cuando los polos magnéticos norte y sur intercambian posiciones.
    EDUARDO MARTÍNEZ DE LA FE/T21