El problema del viajante

El problema del viajante es un ejercicio de optimización muy interesante. El enunciado es muy sencillo y, sin embargo, la resolución es muy compleja. Toda una obsesión para los matemáticos, un juego para los geeks y una pesadilla para las empresas de transporte, para las que buscar la ruta más barata es vital. El enunciado es tan tonto como:

Un viajante debe recorrer varias ciudades y volver a la ciudad de origen. Conocidas todas las distancias entre todos los destinos, debe buscar el itinerario más corto.

¿A que es sencillo? Pues la resolución no lo es, en absoluto… Hay mucho que pensar, tanto, que acabas saliendo del mundo de las matemáticas para empezar a filosofar.

El algoritmo del vecino más próximo

En un primer acercamiento, lo normal, es pensar que la estrategia más sencilla y rentable es ir siempre a la ciudad no visitada que más cerca esté. Y esa es la definición del algoritmo del vecino más próximo. También conocido como el glotón. Es muy sencillo, puede dar buenos resultados en poco tiempo, pero también puede ofrecer soluciones disparatadas. Ya avisan en la wikipedia:

Como norma general, si los últimos pasos del recorrido son comparables en longitud al de los primeros pasos, el recorrido es razonable; si estos son mucho mayores, entonces es probable que existan caminos mucho mejores.

O dicho de otra forma, quien se preocupa sólo de las decisiones inmediatas, puede descalabrarse a largo plazo. ¿Veis como era para filosofar?

Tampoco hay que exagerar: El glotón es un algoritmo razonablemente bueno y muy rápido, y la solución propuesta por mala que sea, siempre será mucho mejor que la mayoría de soluciones posibles. Aunque no siempre sea la óptima.

Deshaciendo nudos

El glotón, en ocasiones, hace que el itinerario se cruce. Si analizamos localmente (olvidando el resto del itinerario) dos tramos que se cruzan, podemos encontrar otras dos maneras de conectar, dos a dos, los cuatro nudos. Esas dos posibilidades dan una longitud menor, pero una de ellas no será válida, porque convertiría el recorrido en dos itinerarios inconexos. Si desconectamos, en otros cuatro nudos habrá que cambiar la conexión para volver a conectar.

4puntos

Para conectar 4 puntos, 2 a 2 siempre hay tres alternativas. La de las diagonales es la peor.

Deshaciendo los cruces podemos mejorar la solución. Como en el ajedrez, cada vez que movemos una ficha, cada vez que tomamos una decisión, cambiamos el tablero de juego, entramos en una partida diferente, descartando todas las opciones que se abrían si la decisión hubiera sido otra. No hay un algoritmo perfecto que nos diga qué tenemos que hacer; prueba y error…

Siempre, para cuatro nodos conectados dos a dos, habrá tres soluciones. La que usa las diagonales es, necesariamente, la peor. Y de las otras dos, hay una que no es válida porque desconectaría el circuito en dos circuitos inconexos.

Además, como actuamos localmente (mirando sólo el problema de dos tramos, no el de toda la ruta), lo mejor que podremos conseguir será acabar en un mínimo local. Que no tiene por qué ser la mejor solución posible.

Puede haber soluciones mejores, pero para llegar a ellas hay que hacer nuevos planteamientos globales. Me fascina la cantidad de relaciones que se pueden encontrar en este problema con el cálculo de estructuras o con la organización de nuestra sociedad.

A fuerza bruta

Cuando se llega a la conclusión de que no hay una fórmula mágica que ofrezca el mejor itinerario, es normal empezar a pensar en evaluar todas las opciones. La resolución por fuerza bruta consistiría en hacer todas las permutaciones posibles de la n ciudades y calcular la suma de las distancias para cada uno de estos posibles itinerarios.

Resolver las cosas por fuerza bruta es como reventar la cerradura de un disparo. Muy chulo pero menos elegante que saber manejar la ganzúa:

Se calcula la longitud del primer itinerario, del segundo, del tercero…  Se apuntan. Sin ningún tipo de actitud crítica sobre los resultados. Si el itinerario parece bueno, se punta como el resto. Si parece malo, también. Pero en ningún momento se valora en qué dirección llevar el estudio, sin aprender de los errores.

Si todos los itinerarios que recorren en un determinado orden las primeras nosecuantas ciudades, salen catastróficos, se continua con las permutaciones que empiezan así, sin sopesar que puede ser un camino erróneo. Desde luego, el nombre de fuerza bruta está muy bien escogido.

Colonia de hormigas

El algoritmo de la colonia de hormigas añade algo de criterio a la fuerza bruta. Imitando el comportamiento de una colonia de hormigas, en cada iteración se valora el resultado de ese itinerario, y se marcan todos sus tramos con la valoración. De la misma forma que las hormigas dejan un rastro de feromonas que las otras pueden seguir. Si la valoración es buena, en próximas iteraciones se tiende a imitar. Si la valoración es mala, también se tiende a evitar los tramos de ese itinerario. De forma que los recorridos acaban siendo definidos como ya aventuraba Machado:

Caminante, son tus huellas
el camino y nada más;
Caminante, no hay camino,
se hace camino al andar.
Al andar se hace el camino,
y al volver la vista atrás
se ve la senda que nunca
se ha de volver a pisar.
Caminante no hay camino
si no estelas en la mar.

Antonio Machado

Hay que saber sopesar la experiencia previa y la necesidad de explorar nuevas alternativas.

Tradición y rebeldía

Al principio de la experiencia todos los caminos son, en principio, desconocidos. Probar un itinerario sin saber nada no deja de ser un problema de azar. Pero en el momento en el que ya se ha valorado un itinerario, ya se sabe algo más que antes de haber empezado. El segundo itinerario tendrá un poco más de experiencia previa y un poco menos de azar.

Cuando no se le da ninguna importancia a lo aprendido en itinerarios anteriores, estamos en el caso de la resolución por fuerza bruta.

Si, por el contrario, se la da mucho peso a la experiencia previa, en seguida el azar desaparece. Los siguientes itinerarios repetirán los anteriores, porque es una forma relativamente segura de evitar el fracaso. Puede que los caminos conocidos no sean los mejores, pero quien los sigue tiene la garantía de no recorrer un itinerario peor. También tiene la garantía de no encontrar nada mejor, pero el cobarde, el defensor de la tradición, olvida que sólo mejora quien arriesga. La historia está plagada de actitudes reaccionarias, con miedo al cambio. Así no se mejora. Ni se empeora.

En el bando opuesto, la rebeldía: No debemos repetir lo que ha funcionado hasta ahora, porque es mejorable, seguro. Y ya tenemos servida la contradicción principal del sistema educativo. Probablemente nuestra sociedad necesita imaginación y cambios. Y la educación marca los caminos de lo conocido y los límites que no se pueden transgredir:

We don’t need no education
We dont need no thought control
No dark sarcasm in the classroom
Teachers leave them kids alone
Hey! Teachers! Leave them kids alone!
All in all it’s just another brick in the wall.
All in all you’re just another brick in the wall.

Pink floyd

PD: Toma entrada pintoresca y heterodoxa con la optimización como pretexto… 😉

Anuncios

Acerca de Pablo Nieto Cabezas

Arquitecto

Publicado el 26 marzo, 2014 en Ciencias, Matemáticas y etiquetado en . Guarda el enlace permanente. 3 comentarios.

  1. ¿QUE NO ENIENDE3S EL EXITO DEL Whatsapp??? YO TE LO DIRE!!!!!! ES EL ARMA MAS PODEROSA DE LA CIA DE TENER CONTROLADA A TODA LA POBLACION!!!! POR ESO ES GRATIS!!!! ¿ENTENDISTE AHORA NIETO?

  1. Pingback: El problema del viajante | Procedimientos de co...

  2. Pingback: El problema del viajante | Zigurat Noticias

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: