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

  • Una pequeña luna de Saturno parecida a la “Estrella de la Muerte” de Star Wars contiene un océano oculto 8 febrero, 2024
    Por debajo de la superficie repleta de cráteres de Mimas, una de las lunas más pequeñas de Saturno, se esconde un océano global de agua líquida de reciente formación. El satélite posee tan sólo unos 400 kilómetros de diámetro y presenta un notable parecido con la “Estrella de la Muerte”, una estación espacial imperial que […]
    Pablo Javier Piacente
  • Logran controlar un objeto virtual con la mente durante un sueño lúcido 8 febrero, 2024
    Un grupo de participantes en un nuevo estudio científico logró manejar un vehículo virtual a través de un avatar únicamente con su mente, mientras sus cerebros permanecían en la fase REM del sueño. Además de profundizar en los misterios de la consciencia humana, la innovación podría facilitar el acceso a nuevos desarrollos tecnológicos, como un […]
    Pablo Javier Piacente
  • Un proyecto global trabaja para crear de forma colaborativa un cerebro robótico general 8 febrero, 2024
    El auge de la inteligencia artificial generativa impulsa un proyecto global que trabaja para crear un cerebro robótico general, capaz de generar androides como los que hemos visto hasta ahora solo en la ciencia ficción. Pero es cuestión de tiempo que convivamos con ellos en perfecta armonía. Ya no es una utopía.
    Eduardo Martínez de la Fe
  • La IA está capacitada para resolver dilemas morales cuando conduce vehículos autónomos 8 febrero, 2024
    Los sistemas de IA muestran significativas similitudes éticas con las reacciones humanas ante dilemas morales, lo que los acreditan para conducir vehículos autónomos tal como lo harían las personas.
    Redacción T21
  • Los huracanes se están volviendo tan fuertes que ya no existen categorías para clasificarlos 7 febrero, 2024
    Cinco tormentas en la última década tuvieron velocidades de viento que pertenecen a una hipotética categoría 6 en la escala de huracanes Saffir-Simpson: el fenómeno obligaría a los científicos a crear una nueva clasificación, capaz de reflejar la virulencia de los huracanes en la actualidad. Las causas principales del fenómeno tienen su origen en el […]
    Pablo Javier Piacente
  • Un asteroide habría explotado sobre la Antártida hace unos 2,5 millones de años 7 febrero, 2024
    Un asteroide se desintegró sobre el continente antártico hace aproximadamente 2,5 millones de años: la evidencia proviene de un análisis químico de más de 100 pequeños trozos de roca extraterrestre, que se han preservado dentro de las enormes capas de hielo. Hasta el momento, solo se conocen otros dos eventos de explosiones aéreas antiguas en […]
    Pablo Javier Piacente
  • Crean la primera niña de inteligencia artificial del mundo 7 febrero, 2024
    La primera niña IA del mundo ha sido creada por científicos chinos, que la han dotado de emociones e intelecto y de la capacidad de aprender de forma autónoma. Se comporta como si tuviera tres o cuatro años y representa un avance significativo para el campo de la inteligencia artificial general.
    Redacción T21
  • Oponerse a la regulación de los pesticidas no es la solución al problema de los agricultores 7 febrero, 2024
    Los agricultores que se movilizan en España y Europa se oponen con firmeza a las nuevas regulaciones europeas en materia de pesticidas, lo que representa una amenaza mayor para la salud pública que tener una central nuclear al lado de casa: estos químicos han costado miles de vidas y enfermos crónicos, al tiempo que han […]
    Eduardo Costas | Catedrático de la UCM y Académico de Farmacia
  • El arte existió antes del surgimiento de los humanos modernos 6 febrero, 2024
    Nuevas investigaciones sugieren que nuestros parientes humanos arcaicos, como los neandertales, ya contaban con las capacidades cognitivas para desarrollar arte: el hallazgo de ejemplos cada vez más antiguos de expresión artística en el registro arqueológico confirmaría esta hipótesis. Sin embargo, aún se discute si estas manifestaciones creativas pueden catalogarse como arte.
    Pablo Javier Piacente
  • Descubren una nueva supertierra que podría ser un mundo habitable 6 febrero, 2024
    Un planeta extrasolar del tipo supertierra, denominado TOI-715 b y aproximadamente una vez y media más ancho que la Tierra, podría ser capaz de albergar vida: orbita dentro de la zona habitable de una enana roja, a escasa distancia de nuestro planeta. Además, podría estar acompañado de otro cuerpo planetario, con un tamaño casi idéntico al […]
    Pablo Javier Piacente