konvertieren 2 opt swap zu 3 opt swap

Question

ich schreibe einen 3-opt-algorithmus für die reisenden verkäufer problem, ich habe bereits 2-opt arbeiten und ich versuche, es zu 3-opt zu konvertieren. Ich bekomme nicht, wie man die 3 Punkte eintauscht, kann mir jemand helfen?

mein Code:

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

Sie haben noch drei Punkte zu tauschen, aber drei Kanten Ihrer Route, weshalb Sie hier ein Problem haben. Angenommen, Ihre Tour ist 0,1, ..., i, i + 1, ..., j, j + 1, ..., k, k + 1, ..., n, 0. Was Sie tun müssen, ist drei Kanten zu löschen [i, i + 1], [j, j + 1] und [k, k + 1] und versuchen, Ihre Tour neu zu erstellen (Beachten Sie, wenn Sie versuchen, mit allen neu zu erstellen Möglichkeiten, Sie werden auch die 2-OPT implementieren und Sie werden auch auf die aktuelle Tour zurückkommen). Sie haben ein Beispiel here auf Folie 39.