旅行推销员，包括通过城市旅行

Question

传统上，旅行推销员问题与从城市到城市的距离从其起源一起工作。如果你可以忽略通过城市的旅行成本，而不是城市之间的旅行成本，那么这种方法非常好。所以问题是，当通过一个城市的旅行费用不能被忽略时，如何找到最短的路线？

更好地解释问题的最简单的方法是采用贪心算法，例如最近邻居从A开始，他先去B然后有2个选择，一个去C去5成本，一去D去6成本。起初，C看起来像更便宜的选择，但通过城市旅行去B需要3成本，并穿过城市去D只需要1.所以最后，采取D将是更便宜的选项。

在我创建一个包含每个城市之间的旅行费用的地图之前，但正如您在示例中所看到的，在城市中旅行对真实旅行费用有很大影响。

有关如何解决此类问题的任何帮助？

编辑：首选边缘可以选择在起点（不通过城市旅游）。 当推销员进入城市时（不通过城市旅行）达到目的地。通过城市旅行的两个方向的费用相同。

Answer 1

我的想法是用大小为n = |邻居（C）|的团体来替换每个城市节点C.将C的每个邻居连接到集团中的一个节点。

集团内部的边缘表示通过C的“过境”，并且它们具有相关的相应运输成本。然后，您必须修改旅行销售员的“目标”，以访问每个城市派系的至少一个节点（而不是访问每个派系） - 或者在访问过之后将所有城市派系节点标记为已访问。

Answer 2

如果我们假设起始节点和结束节点都存在城市成本，那么您需要将该成本添加到您希望包含在路上的顶点。如果一个顶点的成本为n，其目标的成本为m，代理将不得不穿过城市，则成本为n + m。如果开始和结束节点包含在城市内部的交通成本中，那么您需要将您的总旅行成本初始化为出发城市的成本，并且您可以在每次穿过顶点时添加目标城市的成本。如果没有，那么你用0初始化成本，如果你不在最后一步，只会增加城市旅行成本。

如果代理只需访问所有城市一次，那么城市成本可以忽略算法，因为它是一个常数，可以计算并添加到最优的顶点道路成本。