Tendencias 21
Coddii




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

Optimiza el modo de resolver el problema del flujo máximo, fundamental en el análisis de redes y programación


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.




Fuente: Christine Daniloff (MIT)
Fuente: Christine Daniloff (MIT)
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”.


Elena Higueras
Martes, 28 de Septiembre 2010
Artículo leído 9869 veces



Nota

Comente este artículo

1.Publicado por ikki el 29/09/2010 08:31
bien por los informatico de estados unidos, que mejoran lo impensable

2.Publicado por Diego Fanega el 03/10/2010 20:33
Hay un pequeño error que verifiqué en las fuentes citadas: donde dice (N + L)^(2/3) es en realidad (N + L)^(3/2).

3.Publicado por Daiatron el 07/10/2010 11:20
Como dice Diego la complejidad computacional del antiguo algoritmo en realidad es (N + L)^(3/2). Pero no me parece un pequeño error, si no un error grave, porque de ser así el nuevo algoritmo sería peor que el antiguo.
http://www.pensamientoscomputables.com

4.Publicado por Utopico el 15/10/2010 12:07
"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." ... esto es más antiguo que...

Nuevo comentario:
Twitter

Los comentarios tienen la finalidad de difundir las opiniones que le merecen a nuestros lectores los contenidos que publicamos. Sin embargo, no está permitido verter comentarios contrarios a las leyes españolas o internacionales, así como tampoco insultos y descalificaciones de otras opiniones. Tendencias21 se reserva el derecho a eliminar los comentarios que considere no se ajustan al tema de cada artículo o que no respeten las normas de uso. Los comentarios a los artículos publicados son responsabilidad exclusiva de sus autores. Tendencias21 no asume ninguna responsabilidad sobre ellos. Los comentarios no se publican inmediatamente, sino que son editados por nuestra Redacción. Tendencias21 podrá hacer uso de los comentarios vertidos por sus lectores para ampliar debates en otros foros de discusión y otras publicaciones.

Otros artículos de esta misma sección
< >

Lunes, 7 de Noviembre 2016 - 15:00 Bolotweet, la red social del aula