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 ciudades, hay caminos únicos - y podemos verlo como 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!
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
Claramente, esta no es la solución óptima. Con solo mirarlo, puede ver que este es el mejor camino:
Tiene una longitud total de , 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.
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.
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.
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.
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.
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).
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.
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 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.
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 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.
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.
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".
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.
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!
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".
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