.: MATEMATICALIA :. - Pasatiempos

Recibido: lunes, 12 junio 2006

¿Qué pasaría si... (*)

...quisieras reproducir el diseño de la Figura 1:

recortando y pegando trozos de papel? ¿Cuánto papel necesitarías de cada color, si el diseño está dentro de un cuadrado de un metro de lado?

[La solución, en el próximo número]

Solución al problema anterior

...partiendo de la capital de la provincia donde vives y regresando al mismo sitio, imaginaras que visitas todas las capitales de provincia de España “a vuelo de pájaro”, sin repetir ninguna y cubriendo la menor distancia total posible? ¿Podrías encontrar un itinerario? ¿Cómo lo harías?

Respuesta: Sí, habrá un itinerario, quizá varios, que cubra la menor distancia posible. En principio, una manera de encontrar un itinerario así podría ser la siguiente: primero hacemos una lista de todos los itinerarios posibles, sin preocuparnos de las distancias. Luego comenzamos por calcular el kilometraje de los dos primeros itinerarios en nuestra lista y los comparamos entre sí, quedándonos con la ruta más corta. Desde luego, si son iguales da lo mismo elegir una u otra. Comparamos esta ruta con la tercera y continuamos así hasta que hayamos agotado todas las posibilidades. Esta estrategia, que en teoría parece muy fácil, nos muestra que sin duda debe de haber una solución. Pero hay una diferencia muy grande entre saber que existe una solución y encontrarla.

Para entender mejor cuáles son las dificultades en nuestro caso, vamos a usar nuestra estrategia en una situación más sencilla. En lugar de considerar las cincuenta capitales de provincia de España, digamos que consideramos solamente las ocho capitales de provincia de Andalucía, como se muestra en este mapa:

Mapa de las provincias de Andalucía.

Digamos que partimos de Málaga. Tenemos entonces 7 maneras de elegir la primera capital que visitaremos. Desde cada una de estas 7 posibilidades, tenemos 6 maneras de elegir la segunda capital. Desde cada una de estas 6, tenemos 5 maneras de elegir la tercera capital, y así siguiendo hasta la séptima capital, para la que tenemos una sola alternativa y desde la que regresamos a Málaga. ¿Cuál es el número total de itinerarios? Pues será el número

7 × 6 × 5 × 4 × 3 × 2 × 1 = 5.040,

¡que es bastante grandecito!. Si lo pensamos un momento, nos daremos cuenta que este número no depende de la capital donde iniciamos el recorrido. Es verdad que podemos hacer una simplificación si observamos que entre estas rutas hay muchas que seguro tendrán el mismo kilometraje. En efecto, desde nuestro punto de vista, da lo mismo considerar, por ejemplo, la ruta

Málaga → Almería → Granada → Jaén → Córdoba → Sevilla → Huelva → Cádiz → Málaga

o la ruta

Málaga → Cádiz → Huelva → Sevilla → Córdoba → Jaén → Granada → Almería → Málaga

Es decir, que nos podemos quedar con la mitad de las rutas, o sea con

7 × 6 × 5 × 4 × 3 = 2.520,

¡que todavía es un buen número de rutas! Si imaginamos que tardamos nada más que un minuto en escribir a mano cada ruta, necesitaremos 2.520 minutos, o sea 42 horas, o más de un día y medio, para preparar nuestra lista. Digamos que nos hemos puesto muy prácticos en calcular kilometrajes y que con ayuda de una calculadora necesitamos un minuto para calcular el kilometraje de una ruta y decidir si nos quedamos con esa ruta o la descartamos. Eso significa que necesitamos otros 2.520 minutos, o sea 42 horas, o más de un día y medio, para hacer esto. ¡En total, con nuestra estrategia, aplicada a mano, nos llevaría tres días y medio de trabajo continuo el identificar una ruta óptima!

Ya te puedes figurar cuál sería la situación si intentáramos el mismo procedimiento con las cincuenta capitales. En ese caso el número de rutas que tendríamos que considerar sería

50 × 49 × 48 ×... × 3,

o sea, aproximadamente, ¡152070466 seguido de 56 ceros! Si dejáramos en manos de un ordenador el identificar una ruta óptima, suponiendo que tardara UNA MILLONÉSIMA DE SEGUNDO en cada suma y comparación, necesitaría un número de SIGLOS aproximadamente igual al número ¡4822122844 seguido de 39 ceros!

Nuestro problema de apariencia tan inofensiva se ha tornado en una pesadilla numérica debido a la cantidad enorme de posibilidades que hay que analizar para llevar a cabo nuestra estrategia. En términos matemáticos, la cantidad n × (n-1) × (n-2) ×...× 3 × 2 × 1 se llama factorial del número n y se indica n! Esta cantidad tiene un crecimiento, con n, aún más rápido que el crecimiento exponencial. Si recuerdas el ejercicio de doblar una hoja de papel que vimos en el primer ¿Qué pasaría si...? te darás cuenta del crecimiento temible que tiene el factorial. Su aparición en un procedimiento numérico es un indicio de su dificultad, en términos del tiempo necesario para llevarlo a cabo.

Quizá estés pensando que sería mejor olvidarnos de nuestro paseíto por las capitales de provincia de España. ¡De ninguna manera! En muchas situaciones prácticas es muy importante el encontrar rutas que son eficientes en algún sentido que puede tener que ver con distancia, tiempo, adjudicación de recursos o personal y en definitiva, dinero.

Por ejemplo, el optimizar el funcionamiento de redes telefónicas, el seleccionar rutas aéreas o rutas de reparto de mercadería o paquetes postales, el ordenar las tareas de producción en una fábrica y el diseñar el movimiento de brazos robóticos que hacen perforaciones o sueldan circuitos impresos, son todas variaciones del llamado problema del viajante de comercio. En este problema, un viajante que vive en una cierta ciudad tiene que visitar varias ciudades y regresar a su lugar de residencia, recorriendo la menor distancia posible. En casos concretos, hay miles o millones de ciudades que visitar, así que nuestra estrategia de fuerza bruta, analizando todas las posibilidades, es inútil.

No se conoce ningún procedimiento, o algoritmo, que permita a un ordenador o grupo de ordenadores el encontrar una ruta exacta para cualquier número de ciudades. Sin embargo, se conocen procedimientos que con la ayuda de superordenadores permiten encontrar en un tiempo razonable, semanas o meses, rutas que están muy cerca de ser las mejores. Entre esos procedimientos, el más sencillo de aplicar, pero no el mejor, es el llamado algoritmo avaricioso, que consiste en elegir en cada paso la ciudad más cercana, o una de las más cercanas, entre todas las que quedan por visitar. ¿Te atreves a aplicar este algoritmo avaricioso a las capitales de provincia de Andalucía? ¿Y a todas las capitales de provincia de España?

Si esta situación no es la más deseable teóricamente, desde el punto de vista de las aplicaciones, una ruta que es, digamos, un 2% peor que la óptima, ya es una muy buena solución y no se ganaría mucho intentando reducir ese 2%.

Desde luego, desde el punto de vista teórico, el desafío sigue siendo el encontrar rutas exactas. En mayo del 2004, el problema de visitar todas las 24.978 ciudades de Suecia fue resuelto, encontrándose un itinerario óptimo de aproximadamente 72.500 kilómetros de largo. Así se rompió el record establecido en abril del 2001 con un itinerario óptimo de las 15.112 ciudades de Alemania.

Parece que el problema del viajante se inició con el economista y matemático austríaco Karl Menger (1902-1985), quien en los años 1920 lo mencionó a sus colegas en Viena. Desde entonces el problema ha crecido en popularidad e interés tanto desde el punto teórico como el de sus aplicaciones.

Dodecaedro

Ya con anterioridad, el matemático irlandés William Hamilton (1805-1865) y el matemático inglés Thomas Kirkman (1806-1895) habían estudiado problemas vinculados al problema del viajante. En particular, Hamilton había diseñado un juego de ingenio basado en el dodecaedro que consistía en encontrar una ruta que saliendo de uno de los vértices y caminando a lo largo de las aristas, visitara una vez cada vértice, regresando finalmente al vértice de partida. Esto de las aristas y los vértices ¿te resulta familiar? ¡Claro que sí! En el último ¿Qué pasaría si...? exploramos el acertijo de los siete puentes de Königsberg. En esa ocasión lo que queríamos era salir de un vértice, caminar a lo largo de cada arco una vez y regresar, al mismo vértice o a otro vértice. Ahora lo que importa es visitar cada vértice una vez, regresando al vértice del que hemos salido. Así, lo que Euler y Hamilton comenzaron como juegos, se ha transformado a través de los años en una fuente de problemas y aplicaciones muy importantes.

Una buena fuente de información sobre la historia del problema del viajante, sus conexiones con la teoría de gráficos y los esfuerzos hechos para resolverlo, es la página http://www.tsp.gatech.edu, mantenida por el Instituto Tecnológico de Georgia, en los Estados Unidos.

Sobre la autora

Josefina (Lolina) Álvarez es Professor of Mathematics en New Mexico State University (USA). Especialista en análisis armónico y funcional, se doctoró en Matemáticas por la Universidad de Buenos Aires (Argentina), bajo la dirección de A.P. Calderón. Ha ocupado diversos puestos y cargos académicos en la Universidad de Buenos Aires y en las estadounidenses de Princeton, Chicago, Florida Atlantic University y New Mexico. Ha sido investigadora del CONICET (Argentina). Miembro de la Unión Matemática Argentina, Mathematical Association of America y American Mathematical Society, formó parte del Committee on Committees de esta última entre 1999 y 2002. Ha dictado numerosas conferencias en congresos y sesiones especiales e impartido seminarios en Alemania, Argentina, Bélgica, Brasil, Canadá, Colombia, España, Estados Unidos, México, Perú, Polonia, Suecia y Venezuela. Ha pertenecido y en varias ocasiones presidido los comités organizadores de distintos congresos y minisimposia. Ha ejercido como evaluadora para prestigiosas revistas especializadas. Desde 2002 es Editora Asociada del Rocky Mountain Journal of Mathematics. Autora o coautora de numerosos artículos científicos y varias monografías en análisis armónico y funcional y directora de dos tesis doctorales, ha desarrollado asimismo una intensa actividad en el campo de la educación matemática, habiendo recibido diversos galardones a la excelencia docente.