El problema del viajante de comercio

 

Como último problema en esta lista de problemas ‘irresueltos’, voy a agregar el único que figura en la lista de los “Problemas del Milenio” del que escribí un poco más arriba. Es uno de esos problemas que si usted (o alguien) fuera capaz de resolver, podría agregar un millón de dólares a su cuenta bancaria. Eso es la que está dispuesto a pagar el Clay Mathematics Institute.

El problema es de enunciado realmente muy sencillo y se entiende sin dificultades. Claro, eso no quiere decir que sea fácil de resolver, ni mucho menos.

De hecho, usted verá que si sigue leyendo pondrá en duda varias veces que a alguien le puedan pagar semejante suma por resolver lo que parece ser una verdadera pavada. Sin embargo, hace más de 50 años que está planteado como tal (aunque si uno rastrea la historia llega hasta el principio del siglo XIX, en 1800) y, hasta ahora, nadie le encontró la vuelta. Acompáñeme por acá.

Una persona tiene que recorrer un cierto número de ciudades que están interconectadas (pueden ser conectadas a través de rutas por donde circulan automóviles, o vías de ferrocarril o también rutas aéreas). Es decir, siempre se puede ir de una hacia otra en cualquier dirección.

Además, otro dato importante es que uno sabe el costo de ir de una hacia otra (y viceversa). A los efectos prácticos, voy a suponer que viajar desde la ciudad A hasta la ciudad B, sale lo mismo que viajar desde B hasta A.

El problema consiste en: elegir una ciudad en la que empezar el recorrido. Construir un itinerario que pase por cada una (y todas) de las ciudades una sola vez, y que termine en el mismo lugar inicial. Naturalmente, si el problema terminara allí, no sería un ‘problema’. Lo que falta es saber cuál, de todos los posibles caminos que se puedan diseñar, es….¡el más barato!

Eso es todo. No me diga que no le dan ganas de volver para atrás y leer de nuevo, porque estoy seguro que a esta altura, usted debe dudar de que entendió correctamente el enunciado del problema. En vista de la experiencia que tengo (y tuve) con todos aquellos a quienes les conté el problema por primera vez, puedo ‘casi’ asegurar que esto es lo que le está pasando a usted:

1. O usted cree que no entendió bien el planteo o,
2. hay algo que anda mal en este mundo.

Sin embargo está todo bien, sólo que la dificultad aparece escondida. Los intentos que distintas generaciones de matemáticos han hecho tratando de resolverlo han permitido múltiples avances, sobre todo en el área de optimización, pero hasta ahora, octubre del 2018, el problema general no tiene solución [1].

Yo sé que en este momento usted duda de mí, duda de usted... duda de todo. Tiene que haber algo que esté mal. Sigamos.

Hagamos algunos ejemplos sencillos, con pocas ciudades.

Las voy llamar con letras. Para dos ciudades (A y B), dos caminos posibles. Empezar en A, ir a B y volver a A, o empezar en B, pasar por A y volver a B.

ABA y BAB.

Lo que hay que hacer después es estudiar los precios de cada tramo, sumarlos y por lo tanto, cada una de las dos posibles rutas implicará un costo. Uno compara, elige la más barata (aunque podrían ser las dos iguales), y se queda con esa. Listo.

Ahora hagamos lo mismo pero con tres ciudades (A, B y C). Si usted se fija, verá que hay seis caminos y como antes cuando había dos, escribo ‘en orden’ las seis formas posibles de recorrerlas:

ABCA BACB CABC ACBA BCAB CBAC.

Una vez más, uno les agrega los precios de cada segmento, los suma y obtiene el resultado final de cada itinerario. Después elige el más barato, y se terminó.

Para cuatro ciudades (A, B, C y D) hay veinticuatro caminos posibles (que detallo acá abajo):

ABCDA BCDAB CABDC DABCD

ABDCA BCADB CADBC DACBD

ACBDA BDACB CBADC DBACD

ACDBA BDCAB CBDAC DBCAD

ADBCA BACDB CDABC DCABD

ADCBA BADCB CDBAC DCBAD

Supongamos ahora que en lugar de cuatro ciudades, hubiera cinco.

¿Cuántos caminos posibles habrá? (Y acá estará la clave.) Quiero convencerla/o de que de las 24 posibles que había con cuatro ciudades, ahora, para cinco, el número aumenta mucho: hay 120. Vea por qué.

¿En cuántas ciudades se puede empezar el recorrido? Respuesta: en cualquiera de las cinco (A, B, C, D y E).

Una vez elegida la primera, ¿cuántas posibilidades quedan para la segunda ciudad? Respuesta: cualquiera de las cuatro restantes. O sea, nada más que para recorrer las primeras dos ciudades hay ya veinte posibles maneras de empezar:

AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC y ED.

¿Y ahora? ¿Cuántas posibilidades hay para la tercera ciudad? Como ya elegimos dos, nos quedan tres para elegir. Luego, como ya teníamos veinte maneras de empezar, y cada una de éstas puede seguir de tres formas, con tres ciudades, entonces ahora tenemos 60 (sesenta) formas de empezar con tres ciudades. (¿Advierte ya en dónde empieza a estar la dificultad?) Es como si estuviéramos construyendo un árbol, o las ramas de un árbol. Mientras tanto, yo sigo.

Para la cuarta ciudad a elegir, ¿cuántas posibilidades quedan?

Respuesta: dos (ya que son solamente dos las ciudades que no hemos utilizado en el itinerario que hicimos hasta ahora). Luego, para cada una de las 60 formas que teníamos de empezar con tres ciudades, podemos continuar con dos ciudades. Luego, tenemos 120 itinerarios con cuatro ciudades.

Y ahora, para el final, no nos queda nada para elegir, porque de las cinco ciudades que había, ya hemos seleccionado cuatro: la quinta queda elegida por descarte, es la única que queda.

Moraleja: tenemos 120 itinerarios.

Si usted relee lo que escribimos recién, al número 120 llegamos multiplicando los primeros cinco números naturales:

120 = 5 x 4 x 3 x 2 x 1

Este número se conoce con el nombre 5!, pero no es que se lea con gran admiración, sino que los matemáticos llamamos a este número el factorial de cinco. En el caso que estamos analizando, el número cinco es justamente el número de ciudades.

Es fácil imaginar lo que va a pasar si en lugar de tener cinco ciudades, se tienen seis (y le propongo que lo haga). El número de caminos posibles será:

6! = 6 x 5 x 4 x 3 x 2 x 1 = 720

Sigo algunos pasos más.

Siete ciudades, 7! = 5.040 posibles caminos

Ocho ciudades, 8! = 40.320 caminos

Nueve ciudades, 9! = 362.880 caminos

Diez ciudades, 10! = 3.628.800 caminos

Acá paro. Como usted se da cuenta, el total de rutas posibles que habría que analizar con sólo diez ciudades es de ¡más de tres millones seiscientos mil! Agregarle los precios de cada tramo, sumarlos y asociar a cada ruta con el número que saldría recorrer las ciudades en ese orden. Después, elegir la más barata.

La primera conclusión que uno saca es que el factorial de un número aumenta muy rápidamente [2] a medida que uno va avanzando en el mundo de los números naturales. Tan rápido aumenta, que lo invito a que usted haga las cuentas para convencerse.

Imagine que ahora usted es un viajante de comercio y necesita decidir cómo hacer para recorrer –por ejemplo- las capitales de las 23 provincias argentinas, de manera tal que el costo sea el menor posible. O sea, de acuerdo con lo que vimos recién, habría que analizar el factorial de 23 posibles caminos. Pero el factorial de 23 (que se escribe 23!) supera los 25.000 trillones de caminos posibles. Aún a las computadoras más potentes les resulta complicado decidir cuál de todos los recorridos es el óptimo.

23! = 25,852,016,738,885,000,000,000

Con las computadoras más potentes y más rápidas que existen hoy, aún con un ejemplo tan pequeño (solamente 23 ciudades), el número de caminos posibles (y el precio de cada itinerario) se ha transformado en un número gigantesco.

Como usted habrá advertido ya, la dificultad no está en escribir los caminos posibles, ni siquiera en estimar el costo. No. El problema reside en el número descomunal de posibilidades que hay que recorrer hasta poder elegir esa ruta óptima, y si con 23 ciudades hay más de 25.000 trillones, no hace falta que le diga lo que sucedería si uno tiene 100 o 1.000 ciudades.

Por lo tanto, la dificultad reside no en hacer las cuentas, ni siquiera en el método a emplear, ni en sumar los costos y después comparar. El problema, insalvable por ahora, es que hay que hacerlo con una cantidad descomunal de rutas, que como escribí más arriba, aún en los casos más sencillos, parece inabordable.

Hay varios casos particulares que fueron resueltos, pero en esencia el problema está abierto.

Un último comentario: con los actuales modelos de computación, el problema no parece que tenga solución. Hará falta entonces que aparezca alguna nueva idea que revolucione todo lo conocido hasta acá.

Acá termino con este brevísimo recorrido. ¿Habré logrado interesarla/o? ¿Habré logrado motivarla/o? ¿Sabe por qué le pregunto? Es muy claro que usted no va a cambiar su vida leyendo y/o tratando de interpretar los problemas que figuran más arriba, pero, si uno tenía ni idea de lo que pasa en este "mundo" (el de la matemática), ¿no siente que se ha mejorado un poco como persona sabiendo que en el mundo hay muchísima gente pensando soluciones a problemas que nosotros no teníamos la menor idea que existían?

En todo caso, permítame decirle que a mí sí, tanto como me interesaría saber (si pudiera), en qué están pensando los científicos en el mundo, todos los días, no importa la disciplina, no importa el lugar, no importan las condiciones, no importa nada: cuando se despiertan a la mañana y van a ‘trabajar’, ¿se imagina algo mejor que tener un problema irresuelto y pensar que ese día, ese día particular puede que se le ocurra algo que mejore la dirección a la que le estaba apuntando o que le dé una idea que no tenía antes? ¿Qué cosa mejor le podría o puede pasar a uno en la vida (profesional, claro está), que contribuir en ese sentido?

Aunque no esté de acuerdo con lo que escribí (no estoy seguro de que yo lo esté), creo que vale la pena pensar el último párrafo.

 

 

 

 

 

--------------------------------

Para suscribirte con $ 1000/mes al Cohete hace click aquí

Para suscribirte con $ 2500/mes al Cohete hace click aquí

Para suscribirte con $ 5000/mes al Cohete hace click aquí