optimization - 来自primm图的TSP和Lin-Kernighan算法

Question

我正在尝试编写 TSP 问题。由于 Primm 算法，我已经有了最小权重图，我还读到 Lin-Kernighan 算法可以从这个图构造，但看不到如何制作它。

有人可以向我解释如何执行吗？

谢谢

Answer 1

您需要从最小生成树构造一个欧拉回路，然后您可以使用 Lin Kernigan 删除重叠路径（两条边之间的 x 交叉连接）。