¿Existe un problema de vendedor ambulante en el que la solución óptima tiene bordes que se cruzan?bordes de cruce en el problema del vendedor ambulante
Los nodos están en un plano x-y, por lo que cruzar en este caso significa que si dibujara el gráfico, se cruzarían dos segmentos de línea que conectan cuatro nodos separados.
Trivialmente, cualquier gráfico conectado donde cada nodo tenga dos bordes tiene una sola solución TPS, y si se dibuja con cruces, cumplirá los criterios establecidos.
Si tiene otras limitaciones, como modelar viajes alrededor del mundo usando vientos alisios, los costos están relacionados con la posición en el espacio, puede encontrar un caso más complejo donde el cruce es óptimo.
"gráfico conectado donde cada nodo tiene dos bordes" es un círculo, ¿no? – AVB
Si se cruzan dos bordes en una línea poligonal cerrada, entonces hay una línea poligonal con los mismos vértices pero con un perímetro más pequeño. Esto es una consecuencia de la desigualdad triangular. Entonces, una solución al TSP debe ser un simple polígono. Ver this article (Figura 4).
Pregunta: Como parte de la gira del vendedor ambulante, ¿no es necesario que la última ciudad visitada se conecte de nuevo a la primera ciudad visitada, y de esta manera ese último camino se "cruza"/atraviesa varios bordes anteriores? Editar: ¿Tal vez depende de cómo lo dibujas? Al igual que hay una manera de dibujarlo como un polígono sin intersecar bordes. – Jason
@Jason, el punto de mi respuesta es el del TSP euclidiano, la solución nunca se cruza por sí misma. – lhf
Solo en caso de que el artículo se mueva: ["Ventas y fichas" en: columna de características del AMS] (http: //www.ams.org/samplings/feature-column/fcarc-tsp) – Wolf
Si considera una métrica no euclidiana como L1 (distancia de Manhattan), entonces es bastante fácil construir giras más cortas que se intersecten automáticamente.
+--3--+
| | |
| | |
2--+--1
| | |
| | |
+--4--+
Si cada par vecino de intersecciones está a una distancia 1, a continuación, todos los tours tienen longitud 8, incluyendo la auto-intersección que va 1 -> 2 -> 3 -> 4 -> 1
Sin embargo, creo que esto podría traducirse en un problema de vendedor ambulante en un espacio euclidiano 3-D, en cuyo caso la solución óptima (equivalente a esta), no tendría cruces. La clave de mi adición es que todos los problemas completos de NP, incluido el problema TSP a distancia de Manhattan, se pueden "reducir" entre sí. Entonces, resolver TSP en Manhattan no es diferente a la solución del TSP euclidiano ... y en TSP euclidiano, ninguna solución óptima tendrá un cruce de límites. –
Podría obtener bordes cruzados si el costo de ir del nodo A-> C más el costo B-> D> cuesta A-> B y C-> D. Puede obtener esto cuando el costo no sea proporcional a la distancia entre los nodos.
Un ejemplo de la vida real podría ser que hay una bonificación de pasar de A a C (por ejemplo, puedes contrabandear contrabandear) o el costo depende de los pasos previos (turing izquierda un semáforo puede costar mucho de tiempo).
Defina los bordes que se cruzan, por favor. –
Si los bordes se cruzan, cada nodo depende de la ubicación. Esencialmente eso significa que un borde de cruce es un nodo y, por lo tanto, cambia la perspectiva de cuál es la solución óptima. – Pindatjuh
Porque si se cruzan dos trayectorias de vuelo de una aeronave, ¿siempre se puede saltar entre aviones a mitad de camino? –