¿Cuál es la diferencia entre un vendedor ambulante y un viajero chino?

Question

¿Cuál es la diferencia entre traveling-salesman problem y chinese postman problem? Para mí, ambos quieren ir a un destino y luego regresar.

Answer 1

The Traveling Salesman se trata de ir a cada ciudad una vez y tomar la ruta más corta.

El problema del cartero chino se trata de obtener un camino de cada ciudad a otra ciudad.

E.g. con los puntos A, B, C y D del viajante de comercio podría ir ABCDA pero el cartero chino iba a necesitar una ruta que tenía AB y AC y AD, etc.

La ruta itinerante vendedor no tiene un directo entre cada punto (en el ejemplo anterior no hay un enlace AC).

EDIT:
Cada ciudad es un vértice y cada enlace interurbano es una ventaja. Entonces, creo que estoy repitiendo la respuesta de @ Xodarap.

Answer 2

• cartero chino: http://en.wikipedia.org/wiki/Route_inspection_problem
• viajante: http://en.wikipedia.org/wiki/Travelling_salesman_problem

De una breve lectura de los dos artículos (y nunca hice un curso en la teoría de grafos, por lo que podría estar hablando a través mi sombrero), parece que el "CPP" implica visitar todos los bordes, y el "TSP" implica visitar todos los nodos.

Answer 3

Creo que es solo otra variación del problema presentado en los cursos de la universidad de ciencia ficción.

El problema del vendedor chino de viajes (C-TSP) es un problema TSP simétrico típico. Su descripción simple es: Dada una lista de 31 ciudades capitales chinas y sus distancias pares, la tarea es encontrar el recorrido más corto posible que visita cada ciudad exactamente una vez. El C-TSP es un problema de TSP de escala media, que tiene (31-1)!/2 = 1.326 * 1032 posibles rutas.

Answer 4

Los gráficos están hechos de bordes y vértices. CPP requiere una visita a todos los bordes. TSP requiere una visita a todos los vértices.

Answer 5

La diferencia clave entre los dos es:

El problema del viajante no puede visitar un nodo más de una vez. La ruta producida consistirá en todos los diferentes nodos/ciudades.

El problema del Inspector chino de ruta/ruta puede tener nodos duplicados en la ruta producida (pero no en los bordes duplicados). Es decir. los nodos se pueden visitar más de una vez, siempre y cuando se toma una ruta diferente hacia fuera que usted tomó en

Answer 6

Problema del viajante:. ciudades dado y distancia entre ciudades, encontrar el recorrido más corto distancia tal que se visita cada ciudad exactamente uno. Visualizando esto como un gráfico y un costo o peso asociado con cada borde, encuentre el recorrido más barato o menos pesado (ruta hamiltoniana) de modo que cada vértice o nodo se visite exactamente una vez. Podemos pensar en esto como encontrar todo el camino posible de Hamilton y luego encontrar el mejor entre ellos.Encontrar todas las rutas posibles es un problema de optimización y en NP - medios completos ninguna solución polinomio tiempo existe para este problema

problema del cartero chino: Contrariamente a Problema del viajante, CPP requiere encontrar un menor costo o tour peso mínimo a través del gráfico de modo que cada borde se visita al menos una vez. El problema tiene una solución polinómica y la solución óptima requiere encontrar un recorrido por Euler a través del gráfico si el gráfico es euleriano. De lo contrario, modifique el gráfico para que sea Eulerian y defina un recorrido de Euler. Una instancia especial del problema del cartero chino es cuando no necesitamos recorrer todos los bordes del gráfico, sino solo algunos de ellos (bordes requeridos). Esta variación se llama Problema de cartero rural y es NP-completo. En otras palabras, dado un gráfico, encuentre un recorrido de menor costo/peso mínimo de modo que todos los bordes requeridos estén cubiertos al menos una vez que pueda estar utilizando los bordes no requeridos.

Answer 7

Manteniendo la ultra-simple:

El Traveling Salesman Problema se trata de ir a cada ciudad exactamente una vez al regresar a la ciudad original (caminar por lo tanto a lo largo de un Hamiltonian cycle) y teniendo también el camino más corto entre todos los posibles rutas que cumplen este criterio (si tal ruta existe). Encontrar ese ciclo, por fuerza encontrar el ciclo óptimo posiblemente único con la distancia más corta, es "difícil".

El china problema del cartero o ruta de inspección Problema está a punto de visitar cada ruta entre las ciudades al menos una vez al regresar a la ciudad original y tomar la ruta más corta entre todas las rutas posibles que cumplen este criterio (si tal ruta existe). Una solución que toma cada ruta exactamente una vez es automáticamente óptima y se llama Eulerian Cycle. Encontrar tal ciclo es "factible".