algorithm - 带有额外点头的有向图上的旅行推销员

Question

我一直在阅读有关解决旅行商问题的不同算法的信息，但似乎找不到您不希望访问图中所有点头的示例。例如，假设我有一个由点头 n1、n2、n3、n4、n5、n6 组成的图。在经典的旅行推销员问题中，我希望在尽可能短的时间内访问所有点头点。但是如果我想从 n1 离开并只访问 n3 n5 和 n6 怎么办？如果必须的话，我可以通过其他点头，但我绝对必须访问的唯一点是 n1 n3 n5 n6，然后回到 n1。也就是说我要找的是从n1到n1经过这3个点的最短路径。欢迎任何关于要查看哪种算法的提示。

谢谢

塞缪尔·贝尼塔

Answer 1

设 V 为您需要访问的顶点集。设 d(u,v) 为从 u 到 v 的最短路径的长度。对于 V 中的每一对顶点 u 和 v，添加一条从 u 到 v< 的边 长度为 d(u,v)。设此图为 G，即 G 是由这些边扩充的原始图。设 G_V 为限制为 V 的 G。您的问题等同于解决G_V 上的TSP。要看到这一点，请注意，如果 P 是 G 中满足您的约束的最佳路径中的一个段，那么只有它的端点(比如 u 和v)位于V中，则P的长度应为d(u,v)。如果不是，您可以用从 u 到 v 的最短路径替换该段并改进最优解。