假设我们想为给定的具有 V 个顶点和 E 边的完整图 G 计算 TSP（我的意思是完整的：每个顶点都与每个其他顶点相连）。
我会尝试再次提出这个问题。希望这次我能做对。我的目标很简单：
对于这个完整的图 G，如何过滤掉一些可能不在图中的边？
问问题
777 次
2 回答
2
Keld Helsgaun 的 Lin-Kernighan 实现将边 e 的质量测量为 [包括 e 的 1-tree 的最小成本] - [1-tree 的最小成本]（越低越好）。请参见第 4.1 节。
于 2012-01-05T19:41:55.253 回答
0
没有有效的方法来决定是否在解决方案之旅中使用边缘。如果有，那么通过问题的固有自我还原性，您可以通过检查每个边是否依次是解决方案之旅的一部分并在答案是否定的情况下移除边，从而在多项式时间内解决整个问题。
于 2012-01-05T17:19:37.500 回答