旅行推销员问题 (TSP) 和区别 href="http://en.wikipedia.org/wiki/Route_inspection_problem" rel="nofollow noreferrer">中国邮递员问题（CPP）？
对我来说，两者都想去一个目的地，然后再回来。
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.
发布评论
评论（7）
图由边和顶点组成。 CPP 需要访问所有边缘。 TSP 需要访问所有顶点。
Graphs are made of edges and vertices. CPP requires a visit to all edges. TSP requires a visit to all vertices.
旅行推销员问题是关于每个城市去一次并走最短路线。
中国邮递员问题是关于获取从每个城市到另一个城市的路径。
例如，对于 A、B、C 和 D 点，旅行推销员可以走 ABCDA，但中国邮递员则需要一条具有 AB 和 AC 和 AD 的路线等。
旅行商路线在每个点之间没有直达（在上面的示例中没有 AC 链路）。
每个城市都是一个顶点，每个城市间的链接都是一条边。所以，我想我只是重申 Xodarap 的回答。
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.
保持超级简单：
旅行推销员问题是关于每个城市恰好访问一次，同时返回原来的城市（因此沿着哈密尔顿循环），并在满足此条件的所有可能路线中选择最短路线（如果存在这样的路线）。找到这样的循环，必然找到距离最短的可能唯一的最佳循环，是“困难的”。
中国邮递员问题或路线检查问题是关于城市之间的每条道路至少访问一次，同时返回原来的城市并采取最短路线在满足此标准的所有可能路线中（如果存在这样的路线）。每条路恰好一次的解决方案自动是最佳的，称为欧拉循环< /a>.找到这样的循环是“可行的”。
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".
中国邮递员
旅行推销员
简要阅读这两篇文章（我从未上过图论课程） ，所以我可能是在胡言乱语），看来“CPP”涉及访问所有边缘，而“TSP”涉及访问所有节点。
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.
我认为这只是计算机科学大学课程中提出的路径问题的另一种变体。
中国旅行商问题（C-TSP）是一个典型的对称TSP问题。它的简单描述是：给定 31 个中国首都城市及其成对距离的列表，任务是找到访问每个城市一次的最短路径。 C-TSP 是一个中等规模的 TSP 问题，它有 (31−1)! / 2 = 1.326 *1032 条可能的路线。
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.
旅行推销员问题：
给定城市和城市之间的距离，找到最短距离的旅行，使其恰好访问每个城市。将其可视化为图表以及与每条边关联的成本或权重，找到最便宜或最小权重的旅行（哈密尔顿路径），使得每个顶点或节点仅被访问一次。我们可以将其视为找到所有可能的哈密顿路径，然后找到其中最好的。找到所有可能的路线是一个优化问题，在 NP-complete 中意味着没有多项式时间解决方案此问题存在
中国邮递员问题：
与旅行商问题相反，CPP 要求通过图找到最小成本或最小权重旅行，使得每条边至少被访问一次。该问题具有多项式解，如果图是欧拉图，则最优解需要通过图找到欧拉游览。
否则修改图以使其成为欧拉图并定义欧拉游览。中国邮递员问题的一个特殊例子是，我们不需要遍历图的所有边，而只需遍历其中的一些边（必需边）。这种变体称为“农村邮递员问题”，并且是 NP 完全问题。换句话说，给定一个图，找到最低成本/最小权重行程，使得所有所需的边至少被覆盖一次，可以使用非必需的边。
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.