El problema de la red mínima

¿Cuál es la red lineal de longitud total mínima que interconecta un conjunto arbitrario de 100 puntos, pongamos por caso? La solución de este problema se ha resistido a los ordenadores más rápidos y a los matemáticos más sagaces.

Una compañía imaginaria, la Cía. Telefónica Steiner, estimó que podría ahorrar cientos de millones de pesetas si lograse determinar la red mínima de tendido telefónico capaz de interconectar a sus 100 clientes. Tratando de dar con una solución, la Cía. Steiner contrató los servicios de Informática Cavalieri, de nombradía mundial por la eficacia de sus programadores y la rapidez de sus equipos de cómputo. Una semana después, la Cavalieri presentaba a la Cía. Steiner un programa para resolver su problema, demostrando que el programa había hallado en sólo una hora la red mínima correspondiente a 15 de los abonados de ésta. La Cía. Steiner abonó a la Cavalieri 100.000 pesetas por el programa y se comprometió a pagar una peseta por cada segundo de ordenador invertido en la determinación de la solución completa. Pues bien, para cuando el ordenador hubiera concluido el cómputo correspondiente a los 100 abonados, la compañía telefónica adeudaría cientos de billones de pesetas en concepto de tiempo de cómputo y sus abonados se habrían dispersado, ¡fuera por voluntad propia o a causa de la deriva de los continentes!

¿Acaso era defectuoso el programa que Cavalieri preparó para la Cía. Steiner? El dilema anterior es uno de los ejemplos del problema de Steiner, que se plantea hallar la red de segmentos rectilíneos de mínima longitud total que permita conectar entre sí cierto conjunto de puntos. El problema de Steiner no puede ser resuelto trazando sin más segmentos entre los puntos dados, pero sí añadiendo puntos nuevos, llamados puntos de Steiner, que sirven de nudos de enlace en una red de longitud mínima. Los matemáticos y los especialistas en ciencias de cómputo han ideado algoritmos (esto es, procedimientos estrictamente formulados) con el fin de determinar el número y la ubicación de los puntos de Steiner. Empero, ni aun los mejores de tales algoritmos, instalados y funcionando en los ordenadores más rápidos, alcanzan a proporcionar una solución para conjuntos grandes de puntos arbitrarios, porque el tiempo que habrían de invertir para lograrlo es tan largo que es irrealizable. Además, el problema de Steiner pertenece a una categoría de problemas tales que son muchos los científicos informáticos convencidos de que jamás se podrá hallar para ellos un algoritmo eficiente. Por esta razón, la Informática Cavalieri debería quedar exonerada de culpa.

Puedes obtener el artículo en...

¿Tienes acceso a la revista?

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.

Responsable: Prensa Científica, S.A. Finalidad: enviarle por correo electrónico los boletines que haya solicitado recibir. Derechos: tiene derecho a acceder, rectificar y suprimir sus datos, así como a otros derechos, como se explica en la información adicional y detallada que puede consultar en nuestra Política de Privacidad.