En Problema del vendedor itinerante es originalmente un problema de optimización matemático/informático en el que el objetivo es determinar una ruta a seguir entre un grupo de ciudades de forma que se regrese a la ciudad de partida después de visitar cada ciudad exactamente una vez y se minimice la distancia total (longitud/latitud) recorrida. En $n$ ciudades, hay $(n-1)!/2$ caminos únicos - y podemos ver que como $n$ aumenta, el número de caminos a considerar se hace enorme en tamaño. Incluso para un número reducido de ciudades (por ejemplo, 15 ciudades), los ordenadores modernos son incapaces de resolver este problema utilizando la "fuerza bruta" (es decir, calcular todas las rutas posibles y devolver la ruta más corta) - como resultado, se utilizan sofisticados algoritmos de optimización y métodos aproximados para abordar este problema en la vida real.
Estaba intentando explicarle este problema a mi amigo, ¡y no se me ocurría ningún ejemplo que demostrara por qué el Problema del Vendedor Ambulante es difícil! He intentado poner un ejemplo en el que se pide a alguien que encuentre la ruta más corta entre Boston, Chicago y Los Ángeles, pero me he dado cuenta de que el camino más corto en este caso es bastante obvio. (Es decir, moverse en la dirección general de Este a Oeste).
Las aplicaciones del problema del viajante de comercio en el mundo real tienden a tener un nivel adicional de complejidad, ya que suelen tener un "coste" asociado entre pares de ciudades, y este coste no tiene por qué ser simétrico. Por ejemplo, los autobuses pueden programarse con más frecuencia para ir de una ciudad pequeña a una grande, pero con menos frecuencia para volver de la ciudad grande a la pequeña. O incluso un ejemplo más sencillo: puede que haya que conducir "cuesta arriba" para ir de la ciudad A a la ciudad B, pero conducir "cuesta abajo" para ir de la ciudad B a la ciudad A, por lo que es probable que haya un mayor coste para ir de la ciudad A a la ciudad B. Muchas veces, estos "costes" no se conocen del todo y hay que aproximarlos con algún modelo estadístico. Sin embargo, todo esto puede resultar un poco complicado de explicar a alguien que no esté familiarizado con todos estos términos.
Pero sigo buscando un ejemplo para explicarle a mi amigo - ¿Puede alguien ayudarme a pensar en un ejemplo obvio y sencillo del Problema del Vendedor Ambulante en el que resulte evidente que la elección del camino más corto no es obvia? Cada ejemplo sencillo que se me ocurre tiende a ser muy obvio (por ejemplo, Manhattan, Newark, Nashville). No quiero abrumar a mi amigo con un ejemplo de 1.000 ciudades de EE.UU.: basta con algo sencillo con 4 o 5 ciudades en las que no esté claro de inmediato (y quizá incluso sea contraintuitivo) qué camino debe tomarse
Intenté mostrar un ejemplo utilizando el lenguaje de programación R en el que hay 10 puntos (aleatorios) en una cuadrícula - empezando por el punto más bajo, el camino recorrido implica elegir el punto más cercano desde cada punto actual:
library(ggplot2)
set.seed(123)
x_cor = rnorm(5,100,100)
y_cor = rnorm(5,100,100)
my_data = data.frame(x_cor,y_cor)
x_cor y_cor
1 43.95244 271.50650
2 76.98225 146.09162
3 255.87083 -26.50612
4 107.05084 31.31471
5 112.92877 55.43380
ggplot(my_data, aes(x=x_cor, y=y_cor)) + geom_point() + ggtitle("Travelling Salesperson Example")
Pero incluso en este ejemplo, el camino más corto parece "obvio" (imagina que te piden que empieces este problema desde el punto más a la derecha):
Lo intenté con más puntos:
set.seed(123)
x_cor = rnorm(20,100,100)
y_cor = rnorm(20,100,100)
my_data = data.frame(x_cor,y_cor)
ggplot(my_data, aes(x = x_cor, y = y_cor)) +
geom_path() +
geom_point(size = 2)
Pero mi amigo sigue argumentando que el "encuentra el punto más cercano desde el punto actual y repite" (imagina que te piden que empieces este problema desde el punto más abajo a la derecha):
¿Cómo convenzo a mi amigo de que lo que está haciendo corresponde a una "búsqueda codiciosa" que sólo devuelve un "mínimo local" y es muy probable que exista un camino más corto? (ni siquiera el "camino más corto" - sólo un "camino más corto" que la "Búsqueda codiciosa")
Intenté ilustrar este ejemplo enlazándole a la página de Wikipedia sobre búsqueda codiciosa que muestra por qué la búsqueda codiciosa a menudo puede pasar por alto el verdadero mínimo : https://en.wikipedia.org/wiki/Greedy_algorithm#/media/File:Greedy-search-path-example.gif
-
¿Podría alguien ayudarme a pensar en un ejemplo para mostrar a mi amigo en el que elegir el punto inmediatamente más cercano desde donde te encuentras, no da como resultado el camino más corto total? (por ejemplo, algún ejemplo que parezca contraintuitivo, es decir, si eliges un camino siempre basado en el punto más cercano desde tu posición actual, puedes ver claramente que ese no es el camino óptimo)
-
¿Existe alguna prueba matemática que demuestre que el algoritmo "Greedy Search" de Travelling Salesperson tiene la posibilidad de no encontrar a veces el verdadero camino óptimo?
Gracias.
