3-Opt本地搜索TSP？

Question

据我所知,3-Opt Heuristic涉及从图表中删除三条边,然后再添加三条边以重新完成游览.然而,我已经看到很多论文提到当三个边缘被移除时,仍然只有两种可能的方式重新组合巡回演出 - 这对我来说没有意义.

例如,该文件说:

3-opt算法以类似的方式工作,但不是删除两个边缘,而是删除三个.这意味着我们有两种方法可以将三个路径重新连接到有效的tour1中.3-opt移动实际上可以被视为两次或三次2-opt移动.

但是,我计算了8种不同的方式来重新连接游览(如果在删除边缘之前不计算顺序,则为7).我在这里错过了什么？

另外,有人可以将我链接到3-opt的算法吗？我只是想更好地理解它,但我还没有遇到任何问题.我找到的所有资源只是说"删除三条边,重新连接它们".而已.

Answer 1

在页面底部，它澄清了它不计算与单个 2-OPT 移动相同的连接。如果我没记错的话，可以将其减少到四种方式。其中三个看起来像旋转后的图 4，但总的来说，我不会说它们是等效的。