opt算法 c++

下面是一个基本的 C++ 实现 Opt 算法的例子：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>

using namespace std;

// 定义距离函数，这里使用欧几里得距离
double distance(pair<double, double> p1, pair<double, double> p2) {
    double dx = p1.first - p2.first;
    double dy = p1.second - p2.second;
    return sqrt(dx * dx + dy * dy);
}

// 定义 Opt 算法函数
vector<int> opt(vector<pair<double, double>> points) {
    srand(time(NULL));
    int n = points.size();
    vector<int> tour(n);
    for (int i = 0; i < n; i++) {
        tour[i] = i;
    }
    random_shuffle(tour.begin(), tour.end()); // 随机生成一个初始路径
    bool improve = true;
    while (improve) {
        improve = false;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 2; j < n; j++) {
                double d1 = distance(points[tour[i]], points[tour[i + 1]]);
                double d2 = distance(points[tour[j]], points[tour[(j + 1) % n]]);
                double d3 = distance(points[tour[i]], points[tour[j]]);
                double d4 = distance(points[tour[i + 1]], points[tour[(j + 1) % n]]);
                if (d3 + d4 < d1 + d2) { // 如果交换后路径更短，则进行交换
                    reverse(tour.begin() + i + 1, tour.begin() + j + 1);
                    improve = true;
                }
            }
        }
    }
    return tour;
}

int main() {
    vector<pair<double, double>> points = {{0, 0}, {1, 2}, {2, 1}, {3, 3}, {4, 2}};
    vector<int> tour = opt(points);
    for (int i = 0; i < tour.size(); i++) {
        cout << tour[i] << " ";
    }
    cout << endl;
    return 0;
}

该实现假设所有点的坐标都是二维平面上的，用一个 pair<double, double> 类型的向量存储每个点的坐标。distance 函数计算两点之间的距离。opt 函数接受一个 vector<pair<double, double>> 类型的向量，其中存储了所有点的位置信息。该函数首先生成一个随机的初始路径，然后通过不断地交换路径上的两个点，直到路径不再发生改变为止。最后返回一个 vector<int> 类型的向量，其中存储了最优路径上点的编号。在本例中，我们假设所有点的编号从 0 开始。