将2个opt交换转换为3个opt交换

Question

我正在为旅行推销员问题写一个3-opt算法，我已经得到了2-opt的工作，我正在尝试将它转换为3-opt。我不知道怎么交换这3分，有人能帮我吗？

我的代码：

private void ThreeOptSwap(int i, int k, int l) {
    int size = route.size();
    new_Route = new ArrayList<Point>();
    new_Route.addAll(route);
    // 1. take route[0] to route[i-1] and add them in order to new_route
    for ( int c = 0; c <= i - 1; c++ )
    {
        new_Route.set(c, route.get(c) );
    }

    // 2. take route[i] to route[k] and add them in reverse order to new_route
    int dec = 0;
    for ( int c = i; c <= k; c++ )
    {
        new_Route.set( c, route.get( k - dec ) );
        dec++;
    }

    // 3. take route[k+1] to end and add them in order to new_route
    for ( int c = k + 1; c < size; c++ )
    {
        new_Route.set( c, route.get( c ) );
    }
}

Answer 1

你不需要交换三个点，而是你的路线的三个边，这就是为什么你在这里有问题。例如，假设您的巡视是0,1，...，i，i+1，...，j，j+1，...，k，k+1，...，n,0。你要做的是删除三条边i，i+1，j，j+1和k，k+1，并尝试重建你的浏览(请注意，如果你尝试使用所有可能的重建，你也将实现2-OPT，你也将返回到当前浏览)。幻灯片39中有一个here示例。