El problema del viajante de comercio ayuda a que Internet funcione mejor

El problema del viajante de comercio ayuda a que Internet funcione mejor
Facebook Twitter Flipboard E-mail

Existe un rompecabezas clásico que ha intrigado durante años a los matemáticos de todo el mundo. Es el llamado “problema del viajante de comercio”. A grandes rasgos, trata de lo siguiente:

Imaginad que sois viajantes de comercio y que debéis visitar 15 ciudades durante un viaje de negocios. Ciudades que están diseminadas por el mapa de forma aleatoria. Vuestra pregunta, en aras de economizar recursos y tiempo, sería: ¿cuál es el camino que conduce a cada ciudad una sola vez recorriendo la menor distancia posible?

Un vistazo a…
Internet (1997 - 2021): su crecimiento en conexiones

La pregunta parece sencilla. Sin embargo, la respuesta es casi imposible de determinar.

A pesar de que sólo hablamos de 15 ciudades, existen miles de millones de rutas posibles que podemos tomar. Por esa razón, históricamente, los matemáticos no han conseguido una ruta perfecta.

Esta clase de problemas son más importantes de lo que parecen para nuestra vida diaria, aunque nuestro trabajo nada tenga que ver con los viajantes de comercio. Por ejemplo, el funcionamiento de Internet, tal y como lo explica Steven Johnson en Sistemas emergentes:

Pensemos en esos viajantes de comercio como en bits de datos, y en las ciudades como en servidores de Red distribuidos por todo el planeta. Ser capaces de calcular la ruta más corta en la Red sería una bendición para un sistema de distribución masiva como Internet, donde puede haber miles de “ciudades” en cada ruta, en lugar de quince.

Afortunadamente, el problema fue resuelto hace poco. A finales de 1999, Marco Dorigo de la Universidad Libre de Bruselas, anunció que sus colegas y él habían dado con la clave. Y la clave era nada menos que observar a las hormigas.

¿Las hormigas? ¿Qué tienen que ver las hormigas con los viajantes de comercio o con el funcionamiento de Internet?

Al parecer, las colonias de hormigas tienen una habilidad extraordinaria a la hora de calcular el camino más corto hasta diferentes fuentes de alimento, usando su lenguaje simple de rastros de feromonas.

De modo que Dorigo hizo lo mismo que hacen las hormigas. Envió a un ejército de viajantes de comercio virtuales a explorar las posibles rutas en el mapa.

Cuando un viajante completa con éxito el trayecto a las quince ciudades, vuelve sobre sus pasos hasta la primera ciudad y deposita pequeñas cantidades de “feromonas” virtuales en el camino. Dado que la cantidad total de feromonas es finita, se distribuye en dosis más pequeñas en los caminos más largos y en dosis mayores en los más cortos. Con miles de hormigas recorriendo el mapa, algunos sectores de las rutas más cortas acumulan rápidamente gruesas capas de feromonas, mientras que las rutas menos convenientes prácticamente carecen de ellas.

Tras repetir varias sesiones de envíos de viajantes de comercio virtuales con tendencia a soltar feromonas a su paso, la inteligencia emergente del sistema da sus frutos: se alcanza una solución casi óptima para el problema del viajante de comercio sin usar nada que se parezca al cálculo tradicional o a un centro de resolución de problemas.

El problema se resuelve mediante una avalancha de pruebas y errores que interaccionan entre sí y se mejoran a sí mismos.

Ello ha originado que Telecom en Francia, British Telecommunications y MCI apliquen estrategias de routing de este tipo a sus redes de datos y telefonía. Otros estudios demuestran que la aproximación de Dorigo es mucho más eficaz que la rutina Open Shortest Path First que usa Internet para distribuir datos entre nodos de la Red.

En unos años, nuestras interacciones en línea se basarán en el poder ascendente de la inteligencia colectiva. Y todo gracias a las inspiradoras hormigas, que lo descubrieron antes que nosotros.

Vía | Sistemas emergentes de Steven Johnson

Comentarios cerrados
Inicio