What's the difference between traveling salesman and chinese traveling?

What's the difference between travelling salesman problem 开发者_如何学编程(TSP) and Chinese postman problem (CPP)?

For me, both wants go to a destination, and then back.

Graphs are made of edges and vertices. CPP requires a visit to all edges. TSP requires a visit to all vertices.

The travelling salesman problem is about going to each city once and taking the shortest route.

The Chinese postman problem is about getting a path from each city to each other city.

E.g., with points A, B, C, and D, the travelling salesman could go A-B-C-D-A, but the Chinese postman would go need a route that had A-B and A-C and A-D, etc.

The travelling salesman route does not have a direct between each point (in the above example there is no A-C link).

Each city is a vertex and each inter-city link is an edge. So, I think I'm just restating Xodarap's answer.

Keeping it ultrasimple:

The travelling salesman problem is about visiting each city exactly once while returning to the original city (thus walking along a Hamiltonian cycle) and also taking the shortest route among all possible routes that fulfill this criterium (if such a route exists). Finding such a cycle, perforce finding the possibly unique optimal cycle with the shortest distance, is "hard".

The Chinese postman problem or route inspection problem is about visiting each road between cities at least once while returning to the original city and taking the shortest route among all possible routes that fulfill this criterium (if such a route exists). A solution that takes each road exactly once is automatically optimal and called an Eulerian cycle. Finding such a cycle is "feasible".

• Chinese postman

• Travelling salesman

From a brief read of the two articles (and I never took a course in graph theory, so I could be talking through my hat), it appears that the "CPP" involves visiting all edges, and the "TSP" involves visiting all nodes.

The key difference between the two is:

The travelling salesman problem can not visit a node more than once. The path produced will consist of all different nodes/cities.

The Chinese postman/route inspection problem can have duplicate nodes in the path produced (but not duplicate edges). I.e., nodes can be visited more than once as long as you take a different route out than you took in.

I think it's just another variation of the pathing problem presented in computer science college courses.

The Chinese traveling salesman problem (C-TSP) is a typical symmetric TSP problem. Its simple description is: Given a list of 31 Chinese capital cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once. The C-TSP is a mediumscale TSP problem, which has (31−1)! / 2 = 1.326 *1032 possible routes.

Travelling salesman problem:

Given cities and distance between cities, find the shortest distance tour such that it visits each city exactly one. Visualizing this as a graph and a cost or weight associated with each edge, find the cheapest or least weight tour (Hamiltonian path) such that each vertices or node is visited exactly once. We can think of this as finding all possible Hamiltonian path and then find the best among them. Finding all possible routes is an optimization problem and in NP-complete means no polynomial time solution exists for this problem

Chinese postman problem:

Contrary to travelling salesman problem, CPP requires to find a least cost or minimum weight tour through the graph such that each edge is visited at least once. The problem has a polynomial solution and the optimal solution requires to find a Euler tour through the graph if the graph is Eulerian.

Else modify the graph to make it Eulerian and define a Euler tour. A special instance of the Chinese postman problem is where we don’t need to travel all the edges of the graph, but only some of them (required edges). This variation is called the Rural postman problem and is NP-complete. In other words, given a graph, find a least cost/ minimum weight tour such that all the required edges are covered at least once, may be using the non-required edges.