2-opt-best-final.cpp

/***************2-Opt best improve start***********/
void TwoOptHeuristicBestImprovement(vector<int> vec) {
    int ii = 0, jj = 0;
    Tour.clear();
    memset(Vis, 0, sizeof(Vis));

    Tour = vec;

    while (true) {
        double Curr = Cost(Tour);
        bool Changed = false;

        for (int i = 0; i < Tour.size(); i++) {
            for (int j = i + 2; j < Tour.size(); j++) {
                reverse(Tour.begin() + i + 1, Tour.begin() + j + 1);
                double NewCost = Cost(Tour);
                if (NewCost < Curr) {
                    Changed = true;
                    ii = i;
                    jj = j;
                    Curr = NewCost;
                }
                reverse(Tour.begin() + i + 1, Tour.begin() + j + 1);
            }
            if (Changed) {
                reverse(Tour.begin() + ii + 1, Tour.begin() + jj + 1);
                break;
            }
        }

        if (!Changed)
            break;
    }
}