如何解决修正的旅行商问题？

Question

经典的旅行商问题说你可以恰好访问每个节点一次。

我看到了这个有趣的问题，它说你可以重新访问节点，如果这意味着更短的路径。

即图

1-2-3（三角形。 无向边权重：1-2 1

1-3 1

3-2 500

最佳路径是从 1 到 2，然后回到 1，然后到 3。

解决这个问题的算法我不太明白。如果使用普通茶匙，会导致无限循环。

Answer 1

您可以将距离替换为每对节点之间的最短路径距离。因此，在您的示例中，距离为： 1-2: 1 1-3: 1 2-3: 2 然后你在这个实例上解决一个普通的 TSP。模型 "thinks" 它只访问每个城市一次，即使其中一条边实际上第二次访问了它 "through" 一个城市。