2 opt swapを3 opt swapに変換する

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

あなたはここに問題を抱えている理由です、3ポイントを交換する必要がありますが、あなたのルートの3つのエッジはありません。たとえば、ツアーが0,1、...、i、i + 1、...、j、j + 1、...、k、k + 1、...、n、0であるとします。 3つのエッジ[i、i + 1]、[j、j + 1]、[k、k + 1]を削除してツアーを再構築してください。 2 OPTを実装し、現在のツアーにも戻ります）。 スライド39にhereの例があります。