¿Por qué es "difícil" el problema del vendedor itinerante?

Question

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.

Answer 1

He aquí un sencillo ejemplo explícito en el que el algoritmo codicioso siempre falla, esta disposición de ciudades (y distancias euclidianas):

Si aplicas el algoritmo codicioso a este gráfico, tendrá el siguiente aspecto (o una versión invertida):

Esto es cierto independientemente del punto de partida. Esto significa que el algoritmo codicioso nos da un camino con una distancia total recorrida de $20 + 2 + 2\sqrt{101} \approx 42.1$

Pero está claro que no es la solución óptima. A simple vista, se puede ver que este es el mejor camino:

Tiene una longitud total de $4\sqrt{101} \approx 40.2$ que es mejor que el algoritmo codicioso.

Puedes explicarle a tu amigo que la razón por la que falla el algoritmo codicioso es porque no mira hacia adelante. Ve el camino más corto (en este caso, el vertical) y lo toma. Sin embargo, al hacerlo puede verse obligado a tomar un camino mucho más largo, lo que a la larga le dejaría en peor situación. Aunque es fácil de ver en este ejemplo, detectar todos los casos en los que esto ocurre es mucho más difícil.

Answer 2

Me parece que estás buscando una intuición, y no un contraejemplo o una prueba formal. Yo me preguntaba lo mismo hace muchos años y lo siguiente me permitió alcanzar una intuición:

He experimentado con un programa solucionador de TSP llamado Concorde. Ese programa te permite colocar puntos y también puede soltar puntos aleatoriamente. A continuación, mostrará el proceso de resolución a medida que sucede.

Así podrá ver en directo cómo evoluciona el mejor camino conocido actualmente. Se mostrarán trayectorias muy diferentes, cada una un poco mejor que la anterior.

Esto me demostró que caminos muy diferentes pueden conducir a pequeñas mejoras incrementales. Y me mostró lo "no convexa" que es la solución. No se puede utilizar un algoritmo de escalada para llegar a la mejor solución. El problema contiene puntos de decisión que conducen a partes muy diferentes del espacio de búsqueda.

Esta es una manera totalmente no formal de verlo, pero me ayudó mucho.

Answer 3

Este es un ejemplo de 7 ciudades, de Wikipedia . El algoritmo del vecino más próximo da caminos diferentes dependiendo de la ciudad en la que se empiece, así que el resultado debe ser subóptimo para todos estos caminos menos para uno. La ilustración utiliza caminos en lugar de ciclos, pero se pueden conectar mentalmente todos esos caminos a ciclos y mi argumento sigue siendo válido.

Answer 4

Un problema análogo es el recorrido del caballo (hacer que un caballo visite cada casilla de un tablero de ajedrez exactamente una vez). En mi libro XSLT Programmer's Reference incluí una "solución" a este problema (escrita en XSLT) que utilizaba el enfoque intuitivo de moverse siempre a la casilla disponible con menos salidas: e hice un llamamiento a mis lectores para que me dijeran si el algoritmo realmente garantizaba el éxito. Diez años después, un lector respondió con un contraejemplo: una casilla de salida en la que el caballo se quedaba atascado y tenía que retroceder. Resultó que sólo había una casilla de salida así (sin tener en cuenta las simetrías).

Menciono esto únicamente como ejemplo de cómo un algoritmo intuitivo puede dar una solución útil la mayoría de las veces aunque esté equivocado.

Por cierto, el ejemplo de @AndrewP sugiere que la ruta producida por un algoritmo ingenuo es sólo un poco peor que la ruta óptima. No siempre va a ser así. Consideremos 1000 puntos separados por 1 km alrededor de la circunferencia de un círculo, y un punto a 20 km fuera del círculo. Hay una buena solución "obvia" que consiste en visitar el punto más alejado cuando se está en el punto más cercano a él; pero esa solución "obvia" es mucho mejor que el algoritmo simplista codicioso.

Answer 5

Un argumento en contra de la noción de que el algoritmo codicioso es óptimo es observar que la solución codiciosa puede producir diferentes soluciones dependiendo de dónde se empieza, pero por lo general sólo hay un bucle óptimo a través de todas las ciudades, independientemente del punto de partida. El algoritmo codicioso puede producir más de una solución, y siempre que representen soluciones de diferente longitud total, no todas ellas pueden ser óptimas.

Supongamos que tienes 4 ciudades, A, B, C y X. Tanto A como B tienen a X como vecina más cercana, mientras que X tiene a C como vecina más cercana. Si empiezas en A, el camino codicioso incluirá A-X-C, mientras que si empiezas en B, el camino codicioso incluirá B-X-C. Es sencillo construir distancias de camino tales que las distancias totales de estas soluciones sean desiguales y, por tanto, no puedan ser ambas óptimas. La longitud del circuito más corto es una función de la matriz de costes de viaje solamente, el punto de partida es irrelevante. Dado que el método codicioso puede producir múltiples soluciones de diferente longitud total, ciertamente no podemos garantizar que una solución particular que produce es óptima (aunque en algunos casos, puede ser).