graph - 旅行推销员和中国旅行有什么区别？

Question

旅行商问题(TSP) 和中国邮差问题(CPP)有什么区别？

对我来说，两者都想去一个目的地，然后再回来。

Answer 1

图由边和顶点组成。CPP 需要访问所有边缘。TSP 需要访问所有顶点。

Answer 2

旅行商问题是关于去每个城市一次并走最短的路线。

中国邮递员问题是关于从每个城市到另一个城市的路径。

例如，对于 A、B、C 和 D 点，旅行商可以走 ABCDA，但中国邮递员需要一条有 AB 、 AC和AD 的路线，等等。

旅行商路线在每个点之间没有直达（在上面的示例中没有 AC 链路）。

每个城市都是一个顶点，每个城际链接都是一条边。所以，我想我只是重申Xodarap 的回答。

Answer 3

保持超简单：

旅行商问题是关于在返回原始城市时仅访问每个城市一次（因此沿着哈密顿循环行走），并且在满足该标准的所有可能路线中选择最短的路线（如果存在这样的路线）。找到这样一个循环，强制找到距离最短的可能唯一的最佳循环，是“困难的”。

中国邮递员问题或路线检查问题是关于在返回原城市的同时至少访问城市之间的每条道路一次，并在满足该标准的所有可能路线中选择最短的路线（如果存在这样的路线）。每条路只走一次的解决方案是自动最优的，称为欧拉循环。找到这样的循环是“可行的”。

Answer 4

• 中国邮递员

• 旅行推销员

从对这两篇文章的简短阅读（我从来没有上过图论课程，所以我可能会戴着帽子说话），似乎“CPP”涉及访问所有边，而“TSP”涉及访问所有节点.

Answer 5

两者的主要区别在于：

旅行商问题不能多次访问一个节点。生成的路径将包含所有不同的节点/城市。

中国邮递员/路线检查问题可能在生成的路径中有重复节点（但不是重复边）。即，只要您采取的路线与您采取的路线不同，就可以多次访问节点。

Answer 6

我认为这只是计算机科学学院课程中提出的路径问题的另一种变体。

中国旅行商问题（C-TSP）是一个典型的对称TSP问题。它的简单描述是：给定 31 个中国省会城市及其成对距离的列表，任务是找到每个城市恰好访问一次的最短路径。C-TSP 是一个中等规模的 TSP 问题，有 (31−1)！/ 2 = 1.326 * 1032 条可能的路线。

Answer 7

旅行商问题：

给定城市和城市之间的距离，找到最短距离的旅行，以便它访问每个城市恰好一个。将其可视化为与每条边相关的图和成本或权重，找到最便宜或权重最小的游览（哈密顿路径），以便每个顶点或节点仅被访问一次。我们可以认为这是找到所有可能的哈密顿路径，然后找到其中最好的。寻找所有可能的路线是一个优化问题，在NP 完全中意味着该问题不存在多项式时间解

中国邮递员问题：

与旅行商问题相反，CPP 需要通过图找到成本最低或权重最小的旅行，以使每条边至少被访问一次。该问题具有多项式解，如果图是欧拉图，则最优解需要通过图找到欧拉之旅。

否则修改图形以使其成为欧拉曲线并定义欧拉曲线。中国邮递员问题的一个特殊例子是我们不需要遍历图的所有边，而只需要遍历其中的一些（必需的边）。这种变化称为农村邮递员问题，是 NP 完全的。换句话说，给定一个图，找到一个最小成本/最小权重的旅程，使得所有需要的边至少被覆盖一次，可能正在使用不需要的边。