我一直在阅读有关解决旅行商问题的不同算法的信息,但似乎找不到您不希望访问图中所有点头的示例。例如,假设我有一个由点头 n1、n2、n3、n4、n5、n6 组成的图。在经典的旅行推销员问题中,我希望在尽可能短的时间内访问所有点头点。但是如果我想从 n1 离开并只访问 n3 n5 和 n6 怎么办?如果必须的话,我可以通过其他点头,但我绝对必须访问的唯一点是 n1 n3 n5 n6,然后回到 n1。也就是说我要找的是从n1到n1经过这3个点的最短路径。欢迎任何关于要查看哪种算法的提示。
谢谢
塞缪尔·贝尼塔
最佳答案
设 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
的最短路径替换该段并改进最优解。
关于algorithm - 带有额外点头的有向图上的旅行推销员,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27466005/