Problema del viajero

Todos sabemos que existen problemas cuya complejidad es tal, que resultan inabordables incuso para los superordenadores más potentes. Sin embargo, su solución -si es que existe- podría encontrarseutilizando otras formas de procesamiento. Científicos de la escuela de Ciencias Biológicas de la Universidad de Londres ha descubierto que las abejas son capaces de resolver “El problema del viajero”,uno de los más más voraces consumidores de tiempo de CPU. Pero ¿Como lo hacen?


Alguna vez, en un artículo sobre el “algoritmo voraz” te contamos en que consiste el llamado “problema del viajero”.Se trata de un problema que prácticamente todos los alumnos de carreras relacionadas con la informática deben enfrentar en algún momento de sus estudios: “¿Cual es la ruta mas corta que permite a unviajero visitar una lista determinada de destinos?”. Este problema, cuya solución es trivial cuando el numero de destinos posibles es solo dos y bastante fácil de hallar para un número de destinosposibles pequeño -basta con aplicar la “fuerza bruta”, evaluando todos los recorridos posibles y quedarse el trazado que utiliza la menor distancia- se convierte en un dolor de cabeza cuando la cantidadde ciudades implicadas aumenta.

Abejas resuelven “El problema del viajero”
El número de posibles rutas que puede seguir el viajero viene dado por el factorial del número de ciudades (N!) que debevisitar, lo que hace que cada ciudad que se agregue en el recorrido eleve enormemente la complejidad del problema. Si disponemos de un ordenador que pueda analizar un millón de recorridos por segundo,podría hallar la ruta óptima para un recorrido por 10 ciudades en poco más de de 3 segundos. Si fuesen 11 ciudades, demoraría más de medio minuto. Y si fuesen solo 20 ciudades, necesitaría unos77.146 años en encontrar el recorrido más corto. Pero puede que al elegir un superordenador como herramienta para resolver este problema nos hayamos equivocado: un equipo de científicos de la escuela de...