c++ - TSP的3种优化代码

我有这段代码(茶匙问题)适用于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;
            }
        }
    }

最佳答案

基本上，您正在寻找要去除的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++)
            ...

棘手的部分是确定新的成本，因为有一些可行的重新插入方法(而不是二选一的方法)。

关于c++ - TSP的3种优化代码，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28282958/