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

Question

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

Matemáticas
Teoría de grafos
mejoramiento
combinatoria
Matemáticas discretas

estadísticas_noob

El problema del vendedor ambulante es originalmente un problema de optimización de matemáticas/ciencias de la computación en el que el objetivo es determinar un camino a seguir entre un grupo de ciudades de modo que regrese a la ciudad de inicio después de visitar cada ciudad exactamente una vez y la distancia total (longitud/ latitud) recorrida se minimiza. Para $n$ ciudades, hay $(n-1)!/2$ caminos únicos - y podemos verlo como $n$ aumenta, el número de caminos a considerar se vuelve enorme en tamaño. Incluso para un pequeño número de ciudades (por ejemplo, 15 ciudades), las computadoras modernas no pueden resolver este problema usando "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. utilizado para abordar este problema en la vida real.

¡Estaba tratando de explicarle este problema a mi amigo y no pude pensar en un ejemplo que mostrara por qué el problema del vendedor ambulante es difícil! De repente, traté de dar un ejemplo en el que se requiere que alguien encuentre la ruta más corta entre Boston, Chicago y Los Ángeles, ¡pero luego me di cuenta de que la ruta más corta en este caso es bastante obvia! (es decir, muévase en la dirección general de este a oeste).

Las aplicaciones del mundo real del problema del vendedor ambulante tienden a tener una capa adicional de complejidad, ya que generalmente tienen un "costo" asociado entre pares de ciudades, y este costo no tiene que ser simétrico. Por ejemplo, los autobuses pueden programarse con mayor frecuencia para ir de una ciudad pequeña a una ciudad grande, pero programarse con menos frecuencia para regresar de la ciudad grande a la ciudad pequeña; por lo tanto, podríamos asociar un "costo" con cada dirección. . O incluso un ejemplo más simple, es posible que tenga 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 tanto, es probable que el costo de ir de la ciudad A a la ciudad sea mayor. Ciudad B. Muchas veces, estos "costos" no son del todo conocidos y tienen que ser aproximados con algún modelo estadístico. Sin embargo,

Pero todavía estoy buscando un ejemplo para explicárselo a mi amigo: ¿alguien puede ayudarme a pensar en un ejemplo obvio y simple del problema del vendedor ambulante donde queda evidentemente claro que la elección del camino más corto no es obvia? Cada ejemplo simple en el que trato de pensar tiende a ser muy obvio (por ejemplo, Manhattan, Newark, Nashville). No quiero abrumar a mi amigo con un ejemplo de 1000 ciudades en los EE. UU.: solo algo simple con 4-5 ciudades en que no está inmediatamente claro (y tal vez incluso contraintuitivo) qué camino se debe tomar?

Traté de mostrar un ejemplo usando el lenguaje de programación R en el que hay 10 puntos (aleatorios) en una cuadrícula: comenzando desde el punto más bajo, el camino tomado implica elegir el punto más cercano de 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, la ruta más corta parece "obvia" (imagínese que debe comenzar este problema desde el punto inferior derecho):

Probé 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 todavía argumenta que "encuentra el punto más cercano desde el punto actual y repite" (imagina que debes comenzar este problema desde el punto inferior derecho):

¿Cómo convenzo a mi amigo de que lo que está haciendo corresponde a una "búsqueda codiciosa" que solo está devolviendo un "mínimo local" y es muy probable que exista un camino más corto? (ni siquiera el "camino más corto", solo un "camino más corto" que la "Búsqueda codiciosa")

Traté de ilustrar este ejemplo vinculándolo a la página de Wikipedia sobre Greedy Search que muestra por qué Greedy Search a menudo puede pasar por alto el verdadero mínimo: https://en.wikipedia.org/wiki/Greedy_algorithm#/media/File:Greedy-search -ruta-ejemplo.gif

¿Alguien podría ayudarme a pensar en un ejemplo para mostrarle a mi amigo en el que elegir el punto más cercano inmediato desde donde se encuentra no da como resultado el camino más corto total? (por ejemplo, algún ejemplo que parece contradictorio, es decir, si elige una ruta siempre basada en el punto más cercano a su posición actual, puede ver claramente que esta no es la ruta óptima)
¿Existe una prueba matemática que muestre que el algoritmo de "búsqueda codiciosa" en Travelling Salesperson tiene la posibilidad de perder a veces el verdadero camino óptimo?

¡Gracias!

Randall

Hay ejemplos simples en

K_{4}

$K_4$ que muestran que la codicia no funciona. Haga 5 aristas de peso 1 y una arista de peso 10000.

JG

A juzgar por el panel extra de este cómic , deberías leer esto . Una elección adecuada de ciudades haría que la búsqueda codiciosa lo atrapara en un ciclo.

rana globo ocular

@JG ¿No consideraría el algoritmo solo las ciudades que aún no se han visitado?

rana globo ocular

@Randall Es posible que el amigo no acepte ese ejemplo ya que las distancias no obedecen a la desigualdad del triángulo.

JG

@eyeballfrog Me pregunto si el texto sugerido incluye ejemplos en los que incluso ese algoritmo codicioso no es adecuado.

estadísticas_noob

@Randall: ¡Gracias por tu respuesta! ¿Es posible pensar en un ejemplo así sin peso alguno? ¡Gracias!

estadísticas_noob

@JG: ¡Gracias por este cómic y estas recomendaciones! ¡Los vigilaré!

Acumulación

"Para n ciudades, hay (n−1)!/2" Entonces, ¿por qué trataste de dar ejemplos con tres ciudades? Si

n = 2

$n=2$ , su fórmula proporciona solo una ruta única, por lo que, por supuesto, es trivial encontrarla.

kaya3

Para ser claros, un algoritmo codicioso no necesariamente devuelve un "mínimo local", en el sentido de que a menudo puede tomar la salida de un algoritmo codicioso, intercambiar el orden de dos vértices consecutivos y obtener un camino más corto. La respuesta de Andrew P. a continuación es un ejemplo de esto.

profilaes

Los ejemplos suficientemente grandes de TSP a menudo tienen errores evidentes en su solución vecina más cercana, donde el algoritmo termina seleccionando un montón de puntos que se pasaron por alto, a menudo dibujando líneas obvias en todo el mapa.

Rayo

Si puedes demostrar que es difícil, hay un Premio del Milenio esperándote.

Rob Pratt

@Ray El mismo premio si puedes demostrar que no es difícil.

sku

El problema con el algoritmo codicioso no es el algoritmo sino su prueba. Demostrar que GA está bien o mal es tan complejo como el mismo TSP.

daniel r collins

El último ejemplo falla en el proceso propuesto de "encontrar el punto más cercano desde el punto actual y repetir". El segundo paso de la solución (en sentido contrario a las agujas del reloj) es más largo que el paso que podría haber dado hasta el punto en ~(170, 60), etc.

toby mak

Otra idea que tuve fue encontrar el centro de masa y luego dibujar un camino en sentido antihorario/horario alrededor de él. Esperaba otro contraejemplo a esto.

ben

Estoy bastante sorprendido de que ggplot conecte esos puntos, ¿lo hace buscando el óptimo global? Quiero decir, ¿cómo se vería cuando hay 1000 puntos? O los conectaste?

usuario11153

No existe el "problema del vendedor ambulante (?)"

MJD

Algo relacionado: ¿Por qué la solución de Dantzig al problema de la mochila es solo aproximada ? Pregunta por qué un problema relacionado, la "mochila", es difícil y por qué un algoritmo "codicioso" análogo no funciona. En mi respuesta di algunas razones que se aplican aquí también: “Podríamos caracterizar la dificultad general de la siguiente manera: una elección que parecía buena al principio se topó con problemas más tarde, porque nuestra elección inicial nos obliga a tomar [una jugada muy mala] después. . La solución óptima requiere muchas opciones que parecen subóptimas a corto plazo, pero que funcionan bien juntas”.

mao wao

@stats_noob En caso de que se pregunte de qué se trataba esta edición: creo que tuvo el único propósito de eliminar su pregunta de la lista Hot Network Question (HNQ). Las preguntas con mathjax en el título no son elegibles para esta lista porque ni todos los sitios de SE admiten mathjax. Personalmente creo que eso es vandalismo...

naranja_caramelizada

Todavía estoy tratando de descubrir cómo "los autobuses podrían programarse con más frecuencia para ir de una ciudad pequeña a una ciudad grande" sin terminar con un excedente de autobuses sin usar en la ciudad pequeña.

Respuestas (10)

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

Hay ejemplos simples en $K_4$ que muestran que la codicia no funciona. Haga 5 aristas de peso 1 y una arista de peso 10000.
A juzgar por el panel extra de este cómic , deberías leer esto . Una elección adecuada de ciudades haría que la búsqueda codiciosa lo atrapara en un ciclo.
@JG ¿No consideraría el algoritmo solo las ciudades que aún no se han visitado?
@Randall Es posible que el amigo no acepte ese ejemplo ya que las distancias no obedecen a la desigualdad del triángulo.
@eyeballfrog Me pregunto si el texto sugerido incluye ejemplos en los que incluso ese algoritmo codicioso no es adecuado.
@Randall: ¡Gracias por tu respuesta! ¿Es posible pensar en un ejemplo así sin peso alguno? ¡Gracias!
@JG: ¡Gracias por este cómic y estas recomendaciones! ¡Los vigilaré!
"Para n ciudades, hay (n−1)!/2" Entonces, ¿por qué trataste de dar ejemplos con tres ciudades? Si $n=2$ , su fórmula proporciona solo una ruta única, por lo que, por supuesto, es trivial encontrarla.
Para ser claros, un algoritmo codicioso no necesariamente devuelve un "mínimo local", en el sentido de que a menudo puede tomar la salida de un algoritmo codicioso, intercambiar el orden de dos vértices consecutivos y obtener un camino más corto. La respuesta de Andrew P. a continuación es un ejemplo de esto.
Los ejemplos suficientemente grandes de TSP a menudo tienen errores evidentes en su solución vecina más cercana, donde el algoritmo termina seleccionando un montón de puntos que se pasaron por alto, a menudo dibujando líneas obvias en todo el mapa.
Si puedes demostrar que es difícil, hay un Premio del Milenio esperándote.
@Ray El mismo premio si puedes demostrar que no es difícil.
El problema con el algoritmo codicioso no es el algoritmo sino su prueba. Demostrar que GA está bien o mal es tan complejo como el mismo TSP.
El último ejemplo falla en el proceso propuesto de "encontrar el punto más cercano desde el punto actual y repetir". El segundo paso de la solución (en sentido contrario a las agujas del reloj) es más largo que el paso que podría haber dado hasta el punto en ~(170, 60), etc.
Otra idea que tuve fue encontrar el centro de masa y luego dibujar un camino en sentido antihorario/horario alrededor de él. Esperaba otro contraejemplo a esto.
Estoy bastante sorprendido de que ggplot conecte esos puntos, ¿lo hace buscando el óptimo global? Quiero decir, ¿cómo se vería cuando hay 1000 puntos? O los conectaste?
Algo relacionado: ¿Por qué la solución de Dantzig al problema de la mochila es solo aproximada ? Pregunta por qué un problema relacionado, la "mochila", es difícil y por qué un algoritmo "codicioso" análogo no funciona. En mi respuesta di algunas razones que se aplican aquí también: “Podríamos caracterizar la dificultad general de la siguiente manera: una elección que parecía buena al principio se topó con problemas más tarde, porque nuestra elección inicial nos obliga a tomar [una jugada muy mala] después. . La solución óptima requiere muchas opciones que parecen subóptimas a corto plazo, pero que funcionan bien juntas”.
@stats_noob En caso de que se pregunte de qué se trataba esta edición: creo que tuvo el único propósito de eliminar su pregunta de la lista Hot Network Question (HNQ). Las preguntas con mathjax en el título no son elegibles para esta lista porque ni todos los sitios de SE admiten mathjax. Personalmente creo que eso es vandalismo...
Todavía estoy tratando de descubrir cómo "los autobuses podrían programarse con más frecuencia para ir de una ciudad pequeña a una ciudad grande" sin terminar con un excedente de autobuses sin usar en la ciudad pequeña.

Andrés P. · Answer 1

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

Si aplica el algoritmo codicioso en este gráfico, se verá como el siguiente (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$

Claramente, esta no es la solución óptima. Con solo mirarlo, 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, hacerlo puede forzarlo más tarde a tomar un camino mucho más largo, dejándolo peor a largo plazo. Si bien es fácil de ver en este ejemplo, detectar todos los casos en los que esto sucede es mucho más difícil.

Gran ejemplo. Si prefiere números enteros, use un rombo $(0, \pm 5)$ , $(\pm 12, 0)$ por lo que los lados son 13 y las diagonales son 10 y 24. Entonces el mejor ciclo es 13+13+13+13=52, pero el ciclo codicioso (sin importar dónde empieces) es 13+10+13+24=60.
Tenga en cuenta que el camino codicioso en realidad tendría éxito aquí para un camino no circular si comienza desde las ciudades del este o del oeste. Es solo el requisito de volver a su punto de partida lo que hace que este ejemplo falle para el algoritmo codicioso.

boot4life · Answer 2

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

Experimenté con un programa de resolución de TSP llamado Concorde. Ese programa le permite colocar puntos y también puede soltar puntos al azar. Luego mostrará el proceso de resolución a medida que sucede.

A continuación, puede ver en directo cómo está evolucionando la mejor ruta actualmente conocida. Se mostrarán caminos muy diferentes, cada uno un poco mejor que el anterior.

Esto me mostró que caminos muy diferentes pueden conducir a pequeñas mejoras incrementales. Y esto me mostró cuán "no convexa" es la solución. No puede simplemente usar un algoritmo de escalada de colinas para concentrarse en 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 forma completamente no formal de ver esto, pero me ayudó mucho.

Mike Earnest · Answer 3

Mike Earnest

Aquí hay un ejemplo de 7 ciudades, de Wikipedia . El algoritmo del vecino más cercano brinda diferentes caminos según la ciudad en la que comience, por lo que el resultado debe ser subóptimo para todos menos uno de estos caminos. La ilustración usa caminos en lugar de ciclos, pero puedes conectar mentalmente todos esos caminos a ciclos y mi punto aún se aplica.

eric duminil

"El algoritmo del vecino más cercano brinda diferentes caminos según la ciudad en la que comience, por lo que el resultado debe ser subóptimo para todos menos uno de estos caminos" ¿No podrían verse todos diferentes pero aún así tener la misma distancia total? Por ejemplo, ¿3 ciudades en un triángulo equilátero?

kutschkem

@EricDuminil La distancia se muestra en esa animación, en la parte superior. Difiere de 249 - 325. Por supuesto, puede haber ejemplos en los que los caminos sean iguales, pero no son iguales en el caso general.

eric duminil

@kutschkem sí. Todo lo que necesitaba era un solo contraejemplo para demostrar que la afirmación anterior no es correcta.

mb7744

El reclamo es sobre el ejemplo específico proporcionado. No importa que haya casos triviales donde el método del vecino más cercano sea óptimo. Como dijiste, un ejemplo es todo lo que se necesita.

negro mate · Answer 4

El problema es difícil debido a la complejidad combinatoria de probar que tienes la mejor respuesta.

Hay una distinción sutil en juego cuando la gente habla de resultados óptimos en problemas como este. Un matemático o un experto en investigación operativa utiliza el término "óptimo" de manera diferente a los no expertos. Muchos no expertos interpretan lo óptimo como "suficientemente bueno", pero los expertos a menudo insisten en la prueba de la optimización.

Cuando se resuelven problemas similares a TSP del mundo real, se puede argumentar que la definición simple ("suficientemente buena") es en realidad más útil (especialmente si el costo de encontrar una mejor respuesta es alto). Pero los problemas similares a TSP tienen un problema serio al probar que cualquier respuesta es óptima en el sentido experto. No conocemos una manera eficiente de probar que una respuesta dada es la mejor que, de hecho, no implique probar todas las rutas posibles , lo cual es ridículo ya que el número de posibilidades aumenta con el factorial del número de ciudades (incluso los problemas pequeños son demasiado grandes: 50! es más que 10^64).

Para ser justos con algunos comentaristas, hay algunos métodos mejores que la fuerza bruta, pero ninguno escapa a la dificultad fundamental de los problemas NP-difíciles donde el tiempo para resolver un problema crece demasiado rápido con el tamaño del problema para que cualquier algoritmo utilizable sea práctico. uso general. Goyal , al resumir algunos resultados sobre algoritmos eficientes, expresa esta idea en términos más matemáticos (mi punto culminante):

La versión de optimización combinatoria, es decir, el problema de encontrar el ciclo hamiltoniano mínimo en un gráfico de ciudades, y la versión de decisión, es decir, el problema de comprobar la existencia de un ciclo hamiltoniano en un gráfico menor que un peso dado. En la teoría de la complejidad computacional, la versión de optimización combinatoria pertenece al conjunto de problemas NP Hard, lo que implica que no existe un algoritmo de tiempo polinomial incluso para verificar la corrección de una solución dada al problema, mientras que la versión de decisión pertenece a la clase de NP . problemas completos que implican que una solución puede comprobarse en tiempo polinomial. Aunque sin una prueba de que P≠NP, solo se puede suponer que no existe un algoritmo eficiente para resolver cualquier versión del TSP.

En la práctica, hay heurísticas que pueden obtener muy buenos resultados rápidamente, pero ninguna puede garantizar el mejor resultado absoluto.

Como señaló Andrew P en su respuesta, es posible demostrar que incluso en sistemas muy simples, un algoritmo codicioso a veces se equivoca en el criterio de optimización experto. Pero su amigo podría preguntarse si esa diferencia es importante, ya que a menudo no es enorme en comparación con la respuesta óptima conocida.

Ahí es donde es importante tener claro qué significa óptimo . Los expertos podrían argumentar que necesitan pruebas absolutas de que la respuesta es la mejor posible. Los no expertos podrían argumentar que "suficientemente bueno" está bien. O incluso que la idea de optimización debe extenderse para incluir el costo de obtener la respuesta (alguna combinación de potencia de la computadora y tiempo necesario).

Si usted es de la opinión de que el costo de encontrar la respuesta es relevante (como lo son muchos usuarios prácticos del mundo real), entonces su respuesta "óptima" será lo suficientemente buena sin ser óptima en el sentido experto. La mayoría de los problemas similares a TSP tienen muchas buenas respuestas fáciles de encontrar que están dentro de un pequeño % del óptimo experto conocido. Los algoritmos codiciosos a menudo los encontrarán en casos no patológicos, aunque hay algoritmos más complejos que son mejores.

Así que sea claro acerca de su definición de "óptimo" y gran parte del argumento podría desaparecer.

No creo que esta respuesta sea correcta. Considere la versión de optimización de TSP, donde se nos da un mapa y se nos pide que encontremos la ruta mínima. Pero también podemos considerar la versión de decisión, donde se nos da un mapa y un límite y se nos pregunta si existe alguna ruta cuya longitud no exceda el límite. La versión de decisión no es más difícil que la versión de optimización, y probablemente más fácil. Pero el problema de decisión sigue siendo NP-difícil, y no por la razón que diste, porque es fácil demostrar que una respuesta es correcta: solo da la ruta, encuentra su longitud y observa que no excede el límite.
@MJD ¿Cómo haría para probar que la respuesta es correcta cuando la respuesta es "no hay ninguno"?
@MJD Sí, abordé la pregunta de optimización. Pero eso se debe a que la cuestión de la existencia ya es una gran relajación del problema planteado y porque las rutas heurísticas también abordan el problema de la existencia. Demostrar la existencia de una respuesta no le dice a nadie si un algoritmo codicioso es problemático o no y no aborda la cuestión central de la optimización.
La pregunta era “¿por qué es difícil el viajante de comercio”. Su propuesta es que es difícil debido a la complejidad combinatoria de probar que tiene la mejor respuesta. Pero el problema del vendedor ambulante es difícil incluso sin la complejidad combinatoria de demostrar que tiene la mejor respuesta. Entonces a tu respuesta le falta algo crucial.
IIRC, cualquier problema TSP se puede formular como un problema de programación lineal (LP). Este problema de LP tiene un dual que es otro problema de LP. Si puede encontrar soluciones a los problemas de LP original y dual con el mismo valor, entonces ha encontrado una solución óptima. La mayoría de los algoritmos de TSP usan esta dualidad y pueden dar un límite sobre qué tan lejos de la óptima está una solución, y cuando ese límite se vuelve cero, es una prueba de que la solución es óptima.
@JaapScherphuis Esos algoritmos a veces son rápidos, pero no pueden abordar el problema de la optimización experta . Si encontraran rápidamente soluciones óptimas a nivel mundial, serían una prueba de que P = NP y alguien estaría en la fila para una medalla Fields.
@MJD La explosión combinatoria de rutas en el TSP es la razón por la que es difícil en general. La optimización de la solución es un subconjunto de eso, pero la causa es la misma.
Estaba refutando su afirmación de que "No conocemos una forma eficiente de probar que una respuesta dada es la mejor que no implique probar todas las rutas posibles, lo cual es ridículo ya que la cantidad de posibilidades aumenta con el factorial de la cantidad de ciudades". Probar la optimización es bastante factible para muchos problemas grandes de TSP y no tiene nada que ver con probar todas las rutas posibles. Han demostrado ser óptimos en una ruta de 85.900 ciudades, por ejemplo. Encontrar soluciones óptimas es difícil, demostrar que son óptimas a menudo es un subproducto del algoritmo.
@JaapScherphuis Si te refieres a probar en el sentido de "esta ruta es la mejor posible", entonces creo que necesito ver referencias. Las soluciones de LP pueden ser soluciones óptimas del problema de LP, pero esa es una representación imperfecta de cualquier TSP. Muy buenas soluciones a menudo son posibles muy rápidamente a través de un algoritmo LP, si tiene una prueba general de LP de la mejor solución TSP que constituiría una prueba de que P = NP y creo que podría haber notado tal avance. ¿ O está afirmando que solo algunos problemas pueden demostrarse óptimos?
Hmmm, probablemente no estoy recordando las cosas correctamente. Pensé que el límite dado por el LP dual (entero) era ajustado, por lo que siempre podría funcionar como un certificado de prueba si solo pudiera encontrar soluciones óptimas coincidentes para ambos. Pero creo que esto podría estar mal, es decir, que esto solo sucede en algunos casos afortunados, y que en la mayoría de los casos siempre queda una brecha entre ellos, por lo que no es posible una prueba automática de la optimización. Aún así, incluso si el límite fuera ajustado, no creo que eso pruebe que P = NP en absoluto, ya que encontrar las soluciones LP enteras óptimas aún es difícil.
Lo siento, pero he votado negativamente esta respuesta por razones similares a las de los comentaristas anteriores. Parece que no está al tanto de los resultados de la programación lineal, pero los detalles son un poco más sutiles que simplemente notar que hay una simple refutación de "No conocemos una manera eficiente de probar que una respuesta dada es la mejor que no implica probar todas las rutas posibles lo cual es ridículo ya que el número de posibilidades aumenta con el factorial del número de ciudades". A saber, hay un algoritmo de programación dinámica con complejidad $O(2^n \text{poly}(n))$ , basado en considerar qué ciudades han sido visitadas.
@A.Rex como dice un resumen académico : "Dado que el TSP es un problema NP-difícil, los algoritmos heurísticos se usan comúnmente para dar soluciones aproximadas que son buenas, aunque no necesariamente óptimas. Los algoritmos no garantizan una solución óptima, pero da soluciones casi óptimas en un tiempo computacional razonable". Si conoce un resultado que muestra que un método LP/heurístico puede probar la optimización universal, entonces necesitamos ver la referencia.
@matt_black: este algoritmo en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm vinculado desde la página principal de Wikipedia en TSP ya es más rápido que "probar todas las rutas posibles". Como dije, la discusión de los métodos de LP es más sutil, pero también (en forma de bifurcación y enlace) también son más rápidos que "probar todas las rutas posibles". Sugiero centrarse en el algoritmo de programación dinámica (Held-Karp) en lugar de la programación lineal, al analizar esta afirmación sobre "probar todas las rutas posibles".
@A.Rex Mi punto no era que no puede haber un algoritmo mejor que probar cada solución (quizás debería haber sido más claro), pero pensar en la complejidad combinatoria da una buena intuición de por qué los problemas NP-difíciles son difíciles (la dureza NP es bastante fundamental aquí). Se sabe que Held-Karp es mucho mejor que la fuerza bruta, pero también enormemente peor que cualquier algoritmo de tiempo polinomial. Vea el resumen en esta comparación académica de algoritmos para soluciones TSP de 2016 ...
@A.Rex Ese documento concluye: "Con estas complejidades, el algoritmo Held-Karp a menudo enfrenta un problema de memoria cuando encuentra un TSP con 30 o más nodos". lo cual es bastante poco práctico para los problemas del mundo real. Puede ser mucho mejor que la fuerza bruta, pero aún enfrenta el límite NP-hard de ser muy poco práctico para problemas reales, ya que es mucho, mucho peor que el tiempo polinomial (y, en este caso, el espacio) en complejidad. Las buenas soluciones aproximadas a través de varias heurísticas no tienen esta imitación fundamental.
Siento que esta respuesta ignora algo importante al minimizar la importancia de una verdadera solución óptima: la razón por la que el problema es interesante para empezar es que una solución eficiente se traduciría en una solución eficiente para cualquier problema en NP. Las heurísticas para soluciones casi óptimas no ayudan con esto porque la traducción de un problema que es difícil inevitablemente se asigna a casos patológicamente difíciles de TSP.

miguel kay · Answer 5

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" para esto (escrita en XSLT) que usaba el enfoque intuitivo de moverse siempre al cuadrado disponible con la menor cantidad de salidas: y pedí a mis lectores comentarios sobre si el algoritmo estaba realmente garantizado. para triunfar. Diez años después, un lector respondió con un contraejemplo: una casilla inicial donde el caballo se atascó y tuvo que retroceder. Resultó que solo había uno de esos cuadrados iniciales (ignorando las simetrías).

Menciono esto simplemente como un ejemplo de cómo un algoritmo intuitivo puede brindar una solución útil la mayor parte del tiempo, aunque sea incorrecta.

Por cierto, el ejemplo de @AndrewP sugiere que la ruta producida por un algoritmo ingenuo es solo un poco peor que la ruta óptima. Eso no siempre va a ser el caso. Considere 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 es visitar el valor atípico cuando estás en el punto más cercano a él; pero esa solución "obvia" es mucho mejor que el algoritmo codicioso simplista.

Hoagie nuclear · Answer 6

Un contraargumento a la noción de que el algoritmo voraz es óptimo es señalar que la solución voraz puede producir diferentes soluciones dependiendo de dónde comience, pero generalmente solo hay un ciclo ó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 pueden ser óptimas.

Suponga que tiene 4 ciudades, A, B, C y X. Tanto A como B tienen a X como su vecino más cercano, mientras que X tiene a C como su vecino más cercano. Si comienza en A, la ruta codiciosa incluirá AXC, mientras que si comienza en B, la ruta codiciosa incluirá BXC. Es simple construir distancias de caminos tales que las distancias totales de estas soluciones sean desiguales, y por lo tanto, no pueden ser ambas óptimas. La longitud del circuito más corto es solo una función de la matriz de costos de viaje, 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 produzca sea óptima (aunque en algunos casos, puede serlo).

Elchanán Salomón · Answer 7

Aquí hay un ejemplo que no es obvio para mí. Su objetivo es visitar las capitales de los 50 estados de EE. UU. de la manera más económica posible. Puede alquilar un automóvil, siempre que no se dirija a Hawái o Alaska, y el costo es el que tendrá que pagar para ir de una ciudad a la siguiente, teniendo en cuenta el tiempo de conducción, el tráfico, los precios de la gasolina, precios de alquiler, precios de hoteles, etc. También puede volar, y el costo del vuelo depende de qué tan popular sea la ruta y qué tan lejos vuele. Supongamos que siempre hay vuelos directos, pero pueden ser muy caros para rutas inusuales. Honestamente, no tengo ni idea de cómo encontrarías incluso una ruta medianamente decente sin la informática.

En cuanto a por qué el algoritmo codicioso no funciona: supongamos que comienza en Maine y los destinos más caros son Hawái y Alaska (no es sorprendente). Te abrirías camino con avidez por los EE. UU. continentales hasta agotar los 48 inferiores, luego probablemente volarías a Alaska, luego tomarías otro vuelo a Hawái y volarías directamente de regreso a Maine. Mi conjetura es que los vuelos directos entre Alaska y Hawái, y entre Hawái y Maine, si existieran, serían terriblemente caros, por lo que cometió un error estratégico. Habría sido mucho mejor volar a Hawái desde una ciudad de la costa oeste bien conectada, y también regresar de Hawái a una ciudad de la costa oeste bien conectada, en lugar de hacer un viaje Alaska->Hawaii->Maine.

MinnMass · Answer 8

Voy a desviarme un poco de la pregunta que se me hizo para tratar de proporcionar una explicación más intuitiva de por qué TSP es difícil. La respuesta de @matt_block es excelente, pero está dirigida a aquellos con más experiencia y/o capacitación formal en matemáticas que la mía.

Pero todavía estoy buscando un ejemplo para explicárselo a mi amigo: ¿alguien puede ayudarme a pensar en un ejemplo obvio y simple del problema del vendedor ambulante donde queda evidentemente claro que la elección del camino más corto no es obvia? Cada ejemplo simple en el que trato de pensar tiende a ser muy obvio (por ejemplo, Manhattan, Newark, Nashville). No quiero abrumar a mi amigo con un ejemplo de 1000 ciudades en los EE. UU.: solo algo simple con 4-5 ciudades en que no está inmediatamente claro (y tal vez incluso contraintuitivo) qué camino se debe tomar?

Son esos escenarios de mil ciudades los que realmente se dan cuenta de que el TSP es difícil.

Los humanos no son computadoras, y las computadoras no son humanos

Los humanos pueden hacer cosas que las computadoras aún no pueden hacer. Entre ellos se encuentra la eliminación heurística de rutas TSP obviamente malas; por ejemplo, al tratar de "encontrar la ruta más corta entre Boston, Chicago y Los Ángeles", es fácil mirar un mapa y "darse cuenta [] de que la ruta más corta en este caso es bastante obvia". Las computadoras no pueden hacer eso (al menos, no todavía). Más bien, la computadora tiene que verificar tanto B->C->LA como B->LA->C para saber cuál es mejor. Los humanos no (creen que) tienen que hacer eso para un caso tan obvio, por lo que no es intuitivo lo difícil que es para una computadora.

Comience a agregar más ciudades y se vuelve más obvio que elegir el camino correcto es difícil.

Por supuesto, TSP pide una ruta circular; es muy posible que ambas rutas tengan el mismo costo teniendo en cuenta el viaje de regreso.

Los seres humanos tienen dificultades con el crecimiento extremo

Es fácil mirar un mapa con 3, 5 u 11 puntos y elegir la ruta obviamente mejor o, al menos, elegir 2 o 3 candidatos principales para comparar. Parece intuitivo que agregar un punto más no haría mucho más difícil encontrar la ruta óptima. Y no lo es, hasta que lo es. Llega un punto (donde eso variará de persona a persona y de mapa a mapa) en el que agregar un punto más aumenta drásticamente la cantidad de candidatos: la heurística que la persona está usando para eliminar los malos caminos (Boston a Los Ángeles a Chicago) colapsar ante el hecho de tener demasiadas opciones.

Hasta que vea ese desglose en la heurística, puede ser difícil comprender cuán empinado puede ser ese acantilado.

Las computadoras son realmente tontas

Las computadoras no son inteligentes, simplemente fingen serlo haciendo trampa. Hacen trampa al poder hacer matemáticas básicas muy rápido, y luego fingen que todo en el universo es matemática básica (que, para ser justos, funciona una cantidad asombrosa de tiempo).

La mayoría de las veces, hacer trampa es lo suficientemente bueno como para que pensemos en las computadoras como cajas inteligentes (o "mágicas"): entran algunos datos, sale un archivo de Excel con gráficos bonitos; entran algunos otros datos, sale un CGI Gollum.

Pero las computadoras, incluso las nuevas y elegantes redes neuronales de aprendizaje automático, no tienen idea del contexto de las cosas que se les pide que hagan. No tienen idea de si están sumando números de boletos vendidos para la última película taquillera, contando alquileres de videos en el último Blockbuster o pilotando un avión. Simplemente pueden sumar, restar, multiplicar, dividir y hacer lógica bit a bit (a veces emulando uno a través del otro); todo lo demás se basa en eso.

Por lo tanto, las computadoras no pueden mirar un mapa (no tienen ojos, ni ningún concepto de lo que es un "mapa") y hacer que el bucle más corto salte hacia ellos (¿qué es un bucle? ¿Qué es "corto"?). Tienen que hacer cálculos, comprobando todas las rutas posibles para ver si es la más corta.

¿ Estás seguro de que es el más corto?

Como señaló @matt_block, parte del problema con TSP (y problemas relacionados) es estar 100% seguro de haber encontrado el camino más corto (es posible que haya vínculos).

Si solo te importa la distancia (o puedes encontrar alguna otra buena manera de poner los puntos en algo parecido a un mapa), los humanos pueden eliminar algunos malos planes obvios (si estás tratando de llegar a las capitales de los estados, no tiene ningún sentido para ir directamente de Boston a St. Paul), reduciendo así el espacio de búsqueda de "óptimo". Pero: probar que no hay rutas más cortas que "ésta" significa mirar un montón de variaciones en orden (es muy probable que Boston -> Concord -> Augusta -> Montpelier sea parte de la ruta óptima, pero es teóricamente posible que no hay caminos entre Boston y Concord que no pasen por Augusta, para torturar esta metáfora).

Las computadoras ni siquiera pueden eliminar los viajes obviamente malos (Boston a St. Paul) sin control. Pueden dejar de considerar una ruta cuando su longitud actual es mayor que la longitud más corta conocida, pero no pueden descartar por completo la opción de Boston a St. Paul. Por lo tanto, las computadoras deben examinar al menos parcialmente todas las rutas (n−1)!/2.

La analogía de la mochila

Si recuerdo correctamente mi clase CS101, el problema de la mochila se puede transformar en TSP. Básicamente: qué tan eficientemente puede empacar una mochila (dado un conjunto de artículos, cuál es la capacidad mínima sin usar de la mochila con la que puede terminar).

Intuitivamente, TSP es una variante del problema de la mochila: dado un conjunto de ciudades, ¿cuál es la mochila más pequeña que puede contener una ruta circular que visita cada ciudad? ... donde la capacidad de la mochila es "millas" o "dólares" o "horas" o incluso "dólares-millas por hora", dependiendo de lo que estemos optimizando.

Los algoritmos codiciosos claramente no funcionan. Considere una mochila que puede contener 12 unidades y un conjunto de artículos cuesta [ 10, 3, 3, 3, 3 ]: un algoritmo codicioso colocaría el artículo de 10 costos y le sobrarían 2 de capacidad, pero está claro que dejar sacar el artículo de costo 10 permitiría que los artículos de costo 4x3 llenen perfectamente la mochila.

Los algoritmos "anti-codiciosos" (es decir, comenzar primero con los números más pequeños) claramente tampoco funcionan. Considere la misma mochila de 12 unidades y los costos de artículos de [ 1, 12 ]: coloque el artículo de 1 costo y tenga 11 de capacidad sobrante, aunque hay un artículo de 12 costos que puede llenar perfectamente la mochila.

Nuevamente: muchos humanos (con un error de redondeo, probablemente "todos los que puedan ver esta respuesta") pueden mirar esos conjuntos de costos de artículos e inmediatamente ver cuál es la opción óptima. Pero, comience a aumentar la capacidad de la mochila y la cantidad de elementos en el conjunto, y esa inmediatez se reduce rápidamente a "bastante rápido", luego a "Me sobran 2 de capacidad y no veo una manera obvia para llenarlo, pero no estoy seguro de que no haya uno".

Volviendo explícitamente a TSP, ese último caso es "Tengo el circuito reducido a un costo de 302, y no veo una forma obvia de reducirlo, pero no estoy seguro de que no haya uno".

R.. GitHub DEJAR DE AYUDAR A ICE · Answer 9

Si desea una demostración real de la dificultad de elegir una buena ruta de viaje, obtenga una impresora 3D e imprima un modelo complejo con muchos componentes desconectados en cada capa. El software que lo corta para imprimir (nota: puede simplemente cortar cosas sin una impresora para ver los resultados, pero en realidad imprimirlo "lo hace real") tiene que elegir el orden para visitar los componentes y viajar entre ellos, e inevitablemente lo hará. cosas que "parecen mal" y, a menudo, que están mal (subóptimas) porque resolver el problema de manera óptima no es factible.

Lars · Answer 10

El problema del vendedor ambulante no es "difícil" de realizar. El problema es que es muy caro en el recuento de la búsqueda.

Para obtener la mejor ruta, debe visitar cada ciudad desde cada punto de inicio y este número de visitas crece muy rápido en un tamaño que no puede darse cuenta.

En la facultad o n!

La mejor ruta para visitar 8 ciudades da como resultado 40320 comprobaciones.
Para 12 ciudades esto da como resultado más de 4 mil millones de cheques.

En nuestro tiempo actual, lo que son 4 mil millones de cheques para computadoras con 4 GHz, en realidad no es mucho. Hace algunas décadas cuando comencé a estudiar (1992) las computadoras son mucho más lentas (~486DX40 40mhz) que hoy (Alder Lake 12900 5.2ghz) tenemos hoy 130 veces más mhz, pero el número de ciudades calculables ha crecido a la mitad. De 8 a 12 tal vez 13 en el mismo tiempo de cálculo.

Hoy puede ser más útil encontrar una resolución "suficientemente buena por ahora".

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

estadísticas_noob

Randall

JG

rana globo ocular

rana globo ocular

JG

estadísticas_noob

estadísticas_noob

Acumulación

kaya3

profilaes

Rayo

Rob Pratt

sku

daniel r collins

toby mak

ben

usuario11153

MJD

mao wao

naranja_caramelizada

Respuestas (10)

Andrés P.

rosa f

Darrel Hoffmann

boot4life

Mike Earnest

eric duminil

kutschkem

eric duminil

mb7744

negro mate

MJD

pablo h

MJD

negro mate

MJD

Jaap Scherphuis

negro mate

negro mate

Jaap Scherphuis

negro mate

Jaap Scherphuis

a.rex

negro mate

a.rex

negro mate

negro mate

R.. GitHub DEJAR DE AYUDAR A ICE

miguel kay

Hoagie nuclear

Elchanán Salomón

MinnMass

Los humanos no son computadoras, y las computadoras no son humanos

Los seres humanos tienen dificultades con el crecimiento extremo

Las computadoras son realmente tontas

¿ Estás seguro de que es el más corto?

La analogía de la mochila

R.. GitHub DEJAR DE AYUDAR A ICE

Lars