Christofides算法中的捷径步骤如何实现？
我正在实现 Christofides 算法，以便在遵守以下规则的图中获得 TSP 的 3/2 近似值三角不等式。我已经有了使用克鲁斯卡尔算法和邻接矩阵计算最小生成树的代码。
现在，我想通过加倍边并找到欧拉游览然后快捷方式重复节点来实现 Christofides。我该如何执行此步骤？我想要算法和（可选）C 代码。
谢谢！
I am implementing the Christofides algorithm for getting a 3/2-approximation to TSP in graphs that obey the triangle inequality. I already have code for computing a minimum spanning tree using Kruskal's algorithm and an adjacency matrix.
Now, I want to implement Christofides by doubling the edges and finding an Euler tour and then shortcutting duplicate nodes. How do I perform this step? I'd like the algorithm and (optionally) C code.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
“捷径”步骤的工作原理是从欧拉巡演中删除所有已经在巡演中至少出现过一次的节点。例如，如果您参加了旅行团
最终会形成循环
执行此操作的一种方法如下。维护迄今为止您在游览中访问过的所有节点的集合。当您沿着游览路线行走时，如果遇到未访问的节点，请将其附加到您的循环并将其添加到集合中。如果遇到已访问的节点，请跳过它。最后，将找到的最后一个节点的边添加回起始节点。
希望这有帮助！
The "shortcutting" step works by cutting out from the Euler tour all nodes that have already appeared at least once in the tour. For example, if you had the tour
You would end up with the cycle
One way to do this is the following. Maintain a set of all the nodes you've visited so far in the tour. As you walk along the tour, if you encounter an unvisited node, append it to your cycle and add it to the set. If you encounter a visited node, skip it. At the very end, add an edge from the last node you found back to the start node.
Hope this helps!