Problema del Viajante de Comercio

.



por Adrián Paenza

Si usted fuera capaz de resolver el problema que voy a plantear ahora, 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 y, hasta ahora, nadie le encontró la vuelta. Acompáñeme. Una persona tiene que recorrer un cierto número de ciudades que están todas interconectadas (pueden ser rutas, carreteras o por avión). Es decir, siempre se puede ir de una hacia otra en cualquier dirección.

Además, otro dato que se tiene, es cuánto sale ir de una a otra. A los efectos prácticos, vamos 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 construir un itinerario que pase por todas las ciudades una sola vez, y que termine en el mismo lugar inicial, pero con la particularidad que sea 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. Una de dos: o usted no entendió bien el planteo o 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, mayo de 2006, el problema general no tiene solución.

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.

Para dos ciudades, dos caminos:

ABA y BAB

Para tres ciudades, seis caminos:

ABCA BACB CABC

ACBA BCAB CBAC

Para cuatro ciudades, veinticuatro caminos:

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).

¿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?) 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. El número de caminos posibles será:

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

Sigo un par de pasos más.

Siete ciudades, 7! = 5040 posibles caminos

Ocho ciudades, 8! = 40.320 caminos

Nueve ciudades, 9! = 362.880 caminos

Diez ciudades, 10! = 3.628.800 caminos

Y paro acá. 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!

La primera conclusión que uno saca es que el factorial de un número aumenta muy rápidamente 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 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

25,852,016,738,885,000,000,000

rutas posibles (más de ¡veinticinco mil trillones!).

Por lo tanto, se advierte que para resolver el problema hace falta tener una computadora ciertamente muy potente. Pero aun así, este ejemplo (el de las 23 capitales) es muy pequeño.

Creo que ahora queda clara la dificultad. No reside en hacer las cuentas ni en el método que hay que emplear. ¡Esa es la parte fácil! Es que hay que sumar el costo de recorrer cada camino y luego comparar. Al final, uno se queda con el más barato y listo. Pero el problema, insalvable por ahora, es que hay que hacerlo con muchísimos números, un número enorme, que aun en los casos más sencillos, de pocas ciudades, parece inabordable. Lo que se intenta hoy es tratar de encontrar alguna manera de encontrar la ruta más barata sin tener que hacer todos los cálculos, sumar y luego comparar. Ya con 100 ciudades, se sabe que el número de itinerarios posibles es tan grande, que ni siquiera las computadoras más poderosas pueden manejarlo. 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á.

Diario Página12 18/6/2006.-



.