TSP 的 3-opt 优化代码

Question

我有这段代码（tsp 问题）适用于 2-opt 优化，我想将其更改为 3-opt 优化。我知道我必须添加一个 for，但并不真正了解第三个 for 的范围。你能帮助我吗？

    double bestDecrement = tsp.infinite;
    // intial and final position are fixed (initial/final node remains 0)
    for ( uint a = 1 ; a < currSol.sequence.size() - 2 ; a++ ) 
    {
        int h = currSol.sequence[a-1];
        int i = currSol.sequence[a];
        for ( uint b = a + 1 ; b < currSol.sequence.size() - 1 ; b++ ) 
        {
            int j = currSol.sequence[b];
            int l = currSol.sequence[b+1];
            double neighDecrement = - tsp.cost[h][i] - tsp.cost[j][l] + tsp.cost[h][j] + tsp.cost[i][l] ;
            if ( neighDecrement < bestDecrement ) 
            {
                bestDecrement = neighDecrement;
                move.from = a;
                move.to = b;
            }
        }
    }

Answer 1

基本上，您正在寻找 3 个边缘以移除然后重新插入。例如：

for ( uint a = 1 ; a < currSol.sequence.size() - 3 ; a++ ) 
    ...
    for ( uint b = a + 1 ; b < currSol.sequence.size() - 2 ; b++ ) 
        ...
        for ( unit c = b + 1 ; c < currSol.sequence.size() - 1 ; c++)
            ...

更棘手的部分是确定新成本，因为有一些可行的重新插入（而不是 2-opt 中只有一个）。

TSP 的 3-opt 优化代码

3-opt optimization code for TSP

c++

traveling-salesman