Problema del viajante de comercio: ¿por qué visitar cada ciudad una sola vez?

Veamos un ejemplo. Suponga que tiene cuatro ciudades, A, X, Y y Z, y A está a una distancia$1$de cada uno de los otros, mientras que la distancia entre dos cualesquiera de X, Y, Z es$100$. Entonces, por supuesto, una solución para TSP que comienza en A está dada por A a X a A a Y a A a Z a A; escribamos esto como AXAYAZA, que tiene una longitud$6$y visita A varias veces.

Ahora realicemos la construcción en el comentario de Rahul. Formamos un nuevo problema con las mismas ciudades pero con la distancia entre ciudades reemplazada por la longitud del camino más corto entre las dos ciudades. Entonces, en el nuevo problema, A todavía está a distancia.$1$de cada uno de los otros, pero la distancia entre dos cualesquiera de X, Y, Z es$2$. Ahora se satisface la desigualdad del tirangle (aunque la configuración sigue siendo irrealizable en cualquier espacio euclidiano), y AXYZA da una solución, longitud$6$, ninguna ciudad visitada dos veces (excepto por empezar y terminar en A).

Así que hemos tomado un problema donde la solución tiene múltiples visitas a una ciudad y lo hemos reemplazado con un problema equivalente que no las tiene. Espero que quede claro que puedes realizar esta construcción para cualquier conjunto (finito) de ciudades y distancias. Por lo tanto, siempre puede reemplazar un problema con un problema equivalente donde se cumple la desigualdad del triángulo y ninguna ciudad se visita más de una vez. Por lo tanto, no hay pérdida de generalidad al suponer que se cumple la desigualdad del triángulo y que ninguna ciudad se visita más de una vez. Es por eso que podemos restringir nuestra atención a lo que parece, pero en realidad no lo es, un caso especial.

Supongamos que hay caminos que van directamente de cada ciudad a cualquier otra ciudad. Eso hace que el problema sea lo suficientemente simple y general como para elaborar alguna teoría a su alrededor.
El camino AC es más corto que AB+BC, (piensa en el triángulo ABC), a menos que estén en línea recta. Entonces, si ya visitó B anteriormente, visitar B nuevamente es un desvío que alarga el camino total.

Tenía la misma pregunta porque estaba considerando esto como un problema gráfico donde la distancia entre dos nodos puede ser cualquier número arbitrario. Pero creo que TSP realmente significa un problema físico geométrico. Por eso, si eliges dos nodos al azar, la distancia máxima entre ellos está limitada por la desigualdad del triángulo. Pero incluso entonces esto es asumir un plano perfecto. ¿Qué pasa si tengo esta ciudad rodeada de montañas y no puedes ir a ninguna otra ciudad directamente a menos que pases días subiendo y bajando la montaña, pero tienes un pasaje que llega a otra ciudad y estás conectado con el resto del gráfico? al respecto? Dado que debe detenerse donde comenzó, tendría que visitar una ciudad dos veces para obtener la mejor solución.

En otras palabras, si no he entendido nada mal, cada ciudad se visitaría naturalmente una vez si el mapa es plano y las distancias se determinan geométricamente. Pero si las distancias no están limitadas por tales reglas, en mi opinión, cualquier cosa puede suceder en la solución óptima.

El TSP (y los problemas relacionados, como la programación de vehículos capacitados) generalmente asume que se proporciona un gráfico completo como entrada. Es posible que este no sea el caso en la vida real, pero puede convertir el gráfico inicial en un gráfico completo con algoritmos de cálculo de distancia mínima (Floyd-Warshall, etc.).

En ese caso, no hay necesidad de visitar la misma ciudad una vez. Y la función objetivo obviamente lo desalienta a visitar la misma ciudad más veces, por lo que creo que es una restricción de "pista" en lugar de estricta.