Se trata de un problema conocido como el Problema del Agente Viajero o problema del viajante, en inglés es el Travelling Salesman Problem (TSP). El Travelling Salesman Problem de manera muy simplificada trata de encontrar el camino más corto que recorra un conjunto de ciudades. Se dice por ahí, que es el problema computacional más difícil del mundo, yo no puedo confirmarlo, pero no me quedan dudas, podría decir que sí, pero dejaré que ustedes decidan eso.
De entre los siete problemas del milenio; P versus NP, la conjetura de Hodge, la conjetura de Poincaré, la hipótesis de Riemann, la teoría de Yang-Mills o teoría cuántica de campos, las ecuaciones de Navier-Stokes, la conjetura de Birch y Swinnerton-Dyer, el que más se ha intentado solucionar debido a que probablemente sea el único que es más o menos fácil de entender es el problema P y NP.
Cuando hablamos del famoso problema P vs NP, la cosa se pone interesante. La 'P' hace referencia a esos problemas para los que ya tenemos un algoritmo rápido que nos da la solución sin hacernos sufrir demasiado. En cambio, la 'NP' se refiere a los problemas en los que, si alguien nos da la respuesta, podemos comprobar rápido que está bien… pero encontrar esa respuesta por nosotros mismos es otro cantar. Y claro, eso es lo complicado. La gran pregunta detrás de todo esto es: ¿esos problemas que parecen tragarse todos los recursos de la computadora y tardan una eternidad en resolverse son realmente difíciles, o simplemente no hemos descubierto todavía un buen método para solucionarlos? (Quién sabe, quizá la computación cuántica venga a cambiar las reglas del juego). Lo cierto es que con los algoritmos que conocemos, el tiempo de cálculo se dispara de forma exponencial conforme crece el tamaño del problema.
En este terreno, lo que suele hacerse es comparar. Se buscan problemas que sean tan complicados de resolver como el que estamos estudiando, o incluso más. Así, si alguien llega a encontrar un algoritmo eficiente para uno de ellos, ya podemos cantar victoria: significaría que P = NP. Pero si se demuestra que no hay forma sencilla de resolverlos, entonces tendremos que aceptar que hay problemas esencialmente difíciles y que P ≠ NP. Y aquí aparece la estrella de todos los ejemplos: el Travelling Salesman Problem. Este problema es un clásico, famoso por su dificultad y a la vez súper útil en muchísimos ámbitos. Es como la cara más visible de todo este debate entre P y NP.
El problema del viajante de comercio suena de lo más simple cuando lo escuchamos por primera vez: un viajante tiene que recorrer un conjunto de ciudades y quiere hacerlo recorriendo la menor cantidad posible de kilómetros. Fácil, ¿no? A simple vista cualquiera pensaría: “Bueno, se mide la distancia de todas las rutas posibles y listo, nos quedamos con la más corta”. Y sí, en teoría eso funciona… pero en la práctica es una pesadilla.
Porque aquí está el truco: la cantidad de rutas posibles crece de manera explosiva en cuanto aumentamos el número de ciudades. Con unas cuantas todavía se puede calcular a mano o con la computadora sin problema, pero en cuanto agregamos más, la cosa se dispara a niveles ridículos. Es decir, no se trata de que el problema sea imposible de plantear, sino de que la cantidad de combinaciones se vuelve tan grande que resolverlo por fuerza bruta (probando todas las rutas) deja de ser viable. Por eso este problema se ha vuelto el emblema de los NP-difíciles: parece sencillo de entender, cualquiera lo puede explicar en dos minutos, pero encontrar la mejor solución en un tiempo razonable es otra historia completamente distinta.
 |
| Comparación de rutas posibles |
El número de rutas con 'n' ciudades es "(n-1)!/2" y eso a simple vista parece poco, pero crece muy rápido, por ejemplo, con tan solo cinco ciudades son 12 rutas, no es mucho pero mira lo que sucede con 10 ciudades, se los pondré por pasos para los que andan distraídos con el factorial (!):
1...$$\frac{(10-1)!}{2}$$
2...$$\frac{9!}{2}$$
3...$$\frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9}{2}$$
4...$$1 \cdot 1 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 = 181440$$
¿Si lo notaste? Sorprende cómo crece esto. Con tan solo diez ciudades ya estamos hablando de 181,440 rutas posibles; y si subimos a veinte ciudades, la cifra explota a más de 100,000 millones de rutas. Imagínate tratar de revisarlas todas una por una… ¡ni con miles de computadoras trabajando en paralelo acabaríamos a tiempo! Aquí es donde se vuelve evidente la importancia del problema. No se trata solo de planear un viajecito entre ciudades, no. El Travelling Salesman Problem aparece en un montón de áreas prácticas: desde el diseño de circuitos electrónicos, pasando por la logística de grandes almacenes, hasta la cristalografía de rayos X, entre muchas otras aplicaciones. Y claro, en todos estos casos, “las ciudades” son solo una metáfora: pueden ser chips, almacenes, moléculas o lo que se te ocurra.
El verdadero reto es que en estos escenarios el número de “ciudades” (o sus equivalentes) puede ser gigantesco. Y entonces llega la frustración: tenemos un problema que, en teoría, sabemos cómo resolver… pero en la práctica simplemente no podemos aplicar la solución clásica, porque comprobar todas las posibles rutas es inviable. Así que nos quedamos con la pregunta: ¿y ahora qué hacemos?
Hoy en día, muchísimos matemáticos e ingenieros siguen dándole vueltas a cómo enfrentar este problema, y los enfoques principales se dividen en dos grandes caminos.
El primero consiste en reducir la cantidad de rutas a considerar: en lugar de evaluar todas, se buscan métodos para descartar muchas desde el inicio y quedarnos con un conjunto mucho más manejable, dentro del cual sí podemos encontrar la mejor solución.
El segundo enfoque es más relajado: conformarnos con una solución aproximada. Es decir, una ruta muy corta aunque no sea la más corta de todas. La ventaja es que esto se hace rapidísimo y en la práctica suele ser más que suficiente.
A partir de ahí hay varias estrategias: desde el clásico divide y vencerás (partir el problema en pedacitos y luego unirlos), hasta los famosos algoritmos inspirados en la naturaleza, como los algoritmos genéticos o los algoritmos de hormigas. Estos últimos son fascinantes porque imitan el comportamiento de las hormigas cuando buscan comida: prueban distintas rutas, y las más cortas se “premian” porque son las que más usan, lo que acaba señalando de manera colectiva la mejor opción. Y sorprendentemente, aplicado al problema del viajante, funciona muy bien.
Y estos ejemplos que menciono, ¿Funcionan? Pues si, hay muchos buenos ejemplos donde se utilizan estos algoritmos para darle solución óptima al problema de viajante, y a pesar de la complejidad, se ha podido reducir el "(n-1)!/2" a "(n^2)(2^n)" que no parece gran cosa pero si aplicamos las dos fórmulas y las comparamos con los mismos valores se vería así.
Supongamos que n=20:
$$\frac{(20-1)!}{2} = 60,822,550,204,416,000$$
$$20^{2} \cdot 2^{20} = 419,430,400$$
Es una gran diferencia ¿No lo creen? Para todo esto hay toda una serie de Test que se emplean para comprobar la fuerza los distintos algoritmos, el más poderoso de los algoritmos exactos se llama Concord, y ha logrado resolver el Travelling Salesman Problem para un conjunto de 85,900 ciudades, que bueno, en realidad se trataba de puntos en un circuito electrónico. Y refiriéndonos a algunos de los logros de los algoritmos del Travelling Salesman Problem referente al transporte, existe el de una ruta ciclista por 57.912 monumentos en Holanda (figura 2), una ruta por lugares históricos en Estados Unidos (figura 3) y una ruta por 49.687 bares del Reino Unido (figura 4). Estos son todos logros de algoritmos exactos los de los algoritmos aproximados son aún más espectaculares.
 |
| Figura 2. Ruta, monumentos en Holanda |
 |
Figura 3. Ruta, lugares históricos E.U.
|
 |
Figura 4. Ruta, bares Reino Unido
|
Como pueden ver, hemos empezado viendo que hacer una ruta por 20 ciudades era imposible si lo hacíamos de forma ingenua o tradicional, pero con matemáticas y con buenos algoritmos se han podido hacer rutas de más de 80 mil ciudades o por más de mil millones de estrellas de nuestra galaxia. Aquí vemos la importancia de las matemáticas en el área del Transporte.
Héctor.
