旅行商：如何预处理一张图表？
假设我们想要计算给定的、具有 V 顶点和 E 边的完整图 G 的 TSP（完整的意思是：每个顶点都与其他每个顶点相连）。
我会尝试再次问这个问题。希望这次我能做对。 我的目标很简单：
对于这个完整的图G，如何过滤掉一些可能不在图中的边？
Say we wanna compute the TSP for a given, complete graph G with V vertices and E edges (by complete I mean : every vertex is connected with every other vertex).
I'll try to ask the question again. Hopefully I'll get it right this time.
My goal is simple :
For this complete graph G, how does one filter out some edges that will probably not be in the graph?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Keld Helsgaun 实施 Lin-Kernighan 措施边 e 的质量为 [包括 e 的 1-树的最小成本] - [1-树的最小成本]（越低越好）。参见第 4.1 节。
Keld Helsgaun's implementation of Lin-Kernighan measures the quality of an edge e as [min cost of a 1-tree including e] - [min cost of a 1-tree] (lower is better). See Section 4.1.
没有有效的方法来决定是否在解决方案之旅中使用边缘。如果存在，那么通过问题固有的自还原性，您可以通过依次检查每个边是否是解决方案之旅的一部分并在答案是否定的情况下删除该边，在多项式时间内解决整个问题。
There's no efficient way to decide whether an edge will be used in the solution tour. If there were, then by the inherent self-reducibility of the problem you could solve the whole thing in polynomial time by checking whether each edge in turn is part of a solution tour and removing the edge if the answer is no.