Viajeros entre ciudades

Publicado el 11 de Abril de 2023 | Matemáticas

El problema de los puentes de Königsberg, también llamado más específicamente problema de los siete puentes de Königsberg, es un célebre problema matemático, resuelto por Leonhard Euler en 1736 y cuya resolución dio origen a la teoría de grafos. Su nombre se debe a Königsberg, la ciudad de Prusia Oriental y luego de Alemania que desde 1945 se convertiría en la ciudad rusa de Kaliningrado.

Esta ciudad es atravesada por el río Pregel, en ruso «Pregolya», el cual se bifurca para rodear con sus brazos a la isla Kneiphof,2 dividiendo el terreno en cuatro regiones distintas, las que entonces estaban unidas mediante siete puentes. El problema fue formulado en el siglo XVIII y consistía en encontrar un recorrido para cruzar a pie toda la ciudad, pasando sólo una vez por cada uno de los puentes, y regresando al mismo punto de inicio.

Nosotros cuando viajamos hacemos algo parecido, queremos aprovechar el tiempo de nuestro viaje. Así que os propongo un problema. Así, de buenas… Queremos pasar por todos los sitios de una ciudad: el castillo, la catedral, el bar donde hacen las mejores croquetas del mundo, etc…

¿Cómo pasar por esos puntos usando la distancia más corta? Hay que coger la distancia más corta entre los puntos que quieres recorrer. Pues esto es un problema de optimización, llamado el “problema del “viajero” (TSP, por sus siglas en inglés).

El planteamiento del TSP es muy simple: dado un conjunto de ciudades conectadas por carreteras, se trata de diseñar la ruta más corta que saliendo desde un determinado punto, recorra todas las ciudades y vuelva a dicho punto de partida. Esto lo hace el GPS y es un problema de cálculo, no tiene una solución cerrada y a veces supone un reto computacional.

Aplicación en el aula

Os lanzo un problema del viajero sencillo, un viaje que tengo que hacer y no sé cuál es la mejor opción. Quiero salir de Murcia, pasar por dos ciudades, a elegir entre Barcelona, Madrid o Sevilla, y después volver a Murcia.

Sabiendo las distancias entre ciudades: