permutation - TSP中的双桥移动

Question

我想在 TSP 中实现双桥移动。我知道我必须选择 3 个随机位置并将排列分成 4 个部分，然后我必须以不同的顺序将这些部分重新连接在一起，但我想通过双桥获得所有可用于 TSP 问题的可能组合？

假设城市的数量是n，那么双桥的所有可能组合都是n吗？

Answer 1

如果我们尝试将整个排列分成大约四个相等的部分并重新连接它们以找到新的解决方案，那么对于 n 个城市，邻域解决方案的近似数量可能是 [(n-2)/4]^3。这里，[x] 表示大于或等于 x 的最小整数值。