martes, 26 de abril de 2011

Laberintos y matemáticas


Este artículo fue escrito por el gran divulgador de las matemáticas:
Martín Gardner. Actualmente se encuentra publicado en su libro "Nuevos Rompecabezas Mentales"
Por respeto al autor, el artículo se presenta completo.

"Cuando el joven Teseo penetró al laberinto de Creta en Cnosos, en busca del terrible minotauro se desenredó el ovillo de seda que le proporcionó Ariadna para no perderse al volver. Los laberintos arquitectónicos de esta clase, edificios con intrincados pasadizos diseñados para desconcertar a los no iniciados, eran frecuentes en el mundo antiguo. Herodoto describe un laberinto egipcio que tenía tres mil cámaras. Las monedas de Cnosos llevaban grabado un laberinto sencillo, y modelos de laberintos más complicados aparecieron en las aceras romanas y en las túnicas de los antiguos emperadores romanos. Durante la Edad Media, los muros y el piso de muchas catedrales en la Europa continental fueron decorados con diseños similares.
En Inglaterra el más famoso laberinto arquitectónico fue el del laberinto para Rosamunda. En los relatos se cuenta que fue construido en un parque de Woodstock en el siglo XII por el Rey Enrique II, que buscaba esconder a su amante, Rosamunda la Bella, de su esposa Leonor de Aquitania. Usando la técnica del hilo de Ariadna, dice la leyenda, Leonor encontró la manera de llegar al centro del laberinto, donde forzó a la infeliz Rosamunda a beber veneno. La leyenda captó el interés de muchos escritores, entre los que destacan Joseph Addison quien escribió una ópera sobre el tema, y Algernon Charles Swinburne, cuyo poema dramático "Rosamunda" es quizás la versión literaria más conmovedora. Aunque parezca mentira, la costumbre continental de decorar el interior de una catedral con mosaicos de laberintos no fue adoptada en Inglaterra
Era una práctica inglesa muy común, sin embargo, hacer laberintos en el prado afuera de la iglesia, que eran atravesados como parte de un ritual religioso. Estos, "extraños laberintos en el caprichoso césped", como Shakespeare le llamó, florecieron en Inglaterra hasta el siglo XVIII. Los laberintos hechos en jardines, elaborados con altos setos y con el propósito único de divertir, eran la moda hacia el final del Renacimiento.
En Inglaterra, el más popular de estos laberintos hechos con setos, a través del cuál los turistas confundidos aún serpentean buscando el camino, fue diseñado en 1690 para el palacio de Justicia de Hampton de Guillermo de Orange. El plano del laberinto que existe actualmente es el siguiente:
El único laberinto de setos de importancia histórica en los Estados Unidos fue construido a principios del siglo XIX por los "Harmonistas", una secta protestante alemana que se estableció en Harmony, Indiana. El laberinto de Harmony, como los dos de las iglesias medievales, simboliza el serpentear de la serpiente del pecado y la dificultad de mantenerse en el camino verdadero.
Desde el punto de vista matemático, un laberinto es un problema de topología. Si su plano se dibuja en una lámina de hule, el camino correcto desde la entrada hasta la salida es topológicamente invariante y se mantiene correcto no importa cuanto se deforme el hule. El laberinto se puede resolver rápidamente en un papel cuando se sombrean todos los callejones sin salida hasta que sólo queden las rutas directas.
Pero cuando uno se enfrenta, como la reina Leonor, con la tarea de desenredar un hilo para penetrar al laberinto cuyo mapa no poseemos, es una cuestión diferente. Si el laberinto tiene una entrada, y el objetivo es encontrar el camino a la única salida, siempre puede resolverse el problema colocando la mano contra el muro de la derecha (o el de la izquierda) y manteniéndola ahí conforme se camina. Es seguro que se encontrará la salida, a pesar de que la ruta, con mucha probabilidad, no será la más corta. Este procedimiento también funciona en el laberinto tradicional, en el que la meta está en el interior, pero partiendo de la consideración de que no hay ruta por la que se pueda caminar alrededor de la meta y regresar a donde se empezó. Si la meta está rodeada por uno o más de estos circuitos cerrados, el método de la mano en la pared con seguridad lo llevará por la ruta más larga y lo sacará del laberinto; nunca podrá llevarlo a la "isla" dentro del circuito.
A los laberintos que no contienen circuitos cerrados, tales como el laberinto que se muestra en el siguiente dibujo,
Los topólogos los llaman "simplemente conectados". Esto equivale a decir que el laberinto no tiene muros separados. Los laberintos con muros separados sí contienen circuitos cerrados, y se les conoce como laberintos de "conexiones múltiples"; un ejemplo es el siguiente laberinto.
La técnica de la mano en la pared, que se usa sólo para laberintos "simplemente conectados", lo llevará una sola vez en cada dirección a lo largo de cada sendero, así que esté seguro que en algún momento dentro de la ruta, encontrará la salida.
¿Existe un procedimiento mecánico -un algoritmo, para usar un término matemático- que solucione los laberintos, incluyendo los que están conectados en forma múltiple, con circuitos cerrados que rodean la meta? Lo hay, y su mejor formulación se da en el libro de Edouard Lucas "Recréations mathématiques" (volumen 1, 1882). Conforme camina a través de un laberinto, dibuje una línea en un costado del camino, digamos a la derecha. Cuando llegue a una nueva unión de caminos, tome el que desee. Si al caminar a lo largo de un sendero, regresa a una unión que previamente ha visitado, o llega a un callejón sin salida, dé la vuelta y regrese por donde llegó. Si al caminar a lo largo de un camino anterior, ya recorrido (un camino marcado sobre la izquierda), llega a una unión ya visitada, tome un nuevo camino, si uno está disponible; de otra manera tome uno de los viejos caminos. Nunca entre a un camino que esté marcado por ambos lados.
Los adultos de hoy en día ya no se entretienen con tales acertijos, pero hay dos campos dentro de la ciencia en los que el interés por los laberintos permanece: la psicología y el diseño de computadoras. Los psicólogos han usado laberintos desde hace varias décadas para estudiar el comportamiento de aprendizaje en el hombre y en los animales. Aun al más inferior de los gusanos se le puede enseñar a recorrer el laberinto de un tenedor, y la hormiga puede aprender laberintos hasta con diez puntos de elección. Para los diseñadores de computadoras, los robots que manejan laberintos son parte de un emocionante programa para construir máquinas que, como los animales, saquen provecho de su experiencia.
Uno de los más antiguos de estos pintorescos instrumentos es Teseo, el famoso ratón robot para resolver laberintos inventado por Claude E. Shannon, ahora en el Instituto Tecnológico de Massachussets. El ratón hace su camino sistemáticamente a través de un laberinto desconocido, que puede ser de conexiones múltiples, usando una variación del algoritmo antes expuesto. Cuando el ratón llega a la unión en la que debe elegir, no lo hace al azar, como un hombre lo haría, sino que siempre toma el sendero más cercano a un cierto lado. "Esto es bastante difícil para máquinas de solución de problemas que contienen elementos aleatorios", explica Shannon. "Es difícil decir cuando está fallando la máquina si usted no puede predecir lo que ésta debería hacer".
Una vez que el ratón ha encontrado su camino hacia la meta, los circuitos de la memoria le permiten recorrer el laberinto una segunda vez sin error. Un verdadero ratón es mucho más lento para aprender un laberinto, porque su técnica de exploración es en gran medida (pero no por completo) de prueba y error al azar, y necesita lograr muchos éxitos antes de memorizar el camino correcto.
Las máquinas de aprendizaje del futuro adquirirán enormes poderes y jugarán papeles insospechados en las máquinas automáticas de la era espacial. Laberintos y vuelos espaciales; la combinación nos lleva de regreso al mito griego mencionado al inicio del artículo. El laberinto del Minotauro fue construido para el rey Minos por Dédalo, quien inventó un par de alas mecánicas y cuyo hijo pereció por volar muy cerca del sol.

"Un laberinto tan astutamente tramado no fue jamás visto en el mundo, ni antes ni después", escribe Nathaniel Hawthorne en su libro "Cuentos de laberintos", en el que relata la historia. "No puede haber nada más intrincado, excepto quizá que el cerebro de un hombre como Dédalo, que lo planeó, o el corazón de cualquier hombre común..."