问如何解决改进的旅游销售人员问题？
EN

Stack Overflow用户

提问于 2019-04-02 04:32:34

回答 1查看 403关注 0票数 1

经典的旅行推销员问题说，您可以访问每个节点精确一次。

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

Ie图

1-2-3 (三角形)无向边权:1-21

1-3 1

3-2 500

最好的路径是从1到2，然后返回到1，然后再到3。

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

回答已采纳

发布于 2019-04-12 19:24:07

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

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/55467003

复制

相似问题

问如何解决改进的旅游销售人员问题？EN