graph-theory - 如何解决修正的旅行推销员问题？

Question

经典的旅行推销员问题说你可以只访问每个节点一次。

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

即图表

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

1-3 1

3-2 500

最好的路径是从 1 到 2 再回到 1 再到 3。

解决这个问题的算法我不太清楚。如果使用常规 tsp，将导致无限循环。

标签： graph-theorytraveling-salesman

Answer 1

您可以将距离替换为每对节点之间的最短路径距离。所以在你的例子中，距离是： 1-2: 1 1-3: 1 2-3: 2 然后你在这个实例上解决一个正常的 TSP。该模型“认为”它只访问了每个城市一次，尽管其中一条边实际上第二次“穿过”了一个城市。