2-opt 算法，给定旅行的邻域

Question

我真的不明白如何使用 2-opt 算法找到给定旅行的邻居：

假设我们有 T = 0-1-2-4-3-0

定义说：T 的邻域定义为所有 可以通过改变 T 中的两个不相邻边（2-交汇处）到达的旅行。

所以我们有这些不相邻的边：

(0,1) 和 (2,4)

(0,1) 和 (4,3)

(1,2) 和 (4,3)

(1,2) 和 (3,0)

(2,4) 和 (3,0)

我们必须找到 5 个邻居，我们如何通过进行 2 次交换移动来生成它们？

提前致谢。

Answer 1

您找到了不相邻边对的正确想法。然后，对于每一对，只有一种可行的方法可以通过附加新的边来形成新的旅行。例如，如果我们删除 (0,1) 和 (2,4)，则存在三对边，我们可以将它们替换为：

(0,1) and (2,4): 但是这个和原来的游一样

(0,4) 和 (1,2)：但这会创建两个子路线而不是一个路线

(0,2) 和 (1,4)：这是赢家

一般来说，如果我们删除边 (i,j) 和 (k,l)，然后我们用 (i,k) 和 (j,l) 替换它们——假设这会降低成本。请注意，这会改变一半游览的方向。

所以根据你的定义，T的邻域就是这样得到的所有新游的集合。