模拟退火算法覆盖路径c++

模拟退火算法可以用于求解覆盖路径问题。覆盖路径问题是指在一个图中，找到一条路径，使得该路径覆盖了所有的节点，并且路径长度最短。下面是一个简单的c++实现：

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

const int MAXN = 100;
const double INF = 1e9;
const double eps = 1e-8;
double x[MAXN], y[MAXN];
double dis[MAXN][MAXN];
int n;

double calc_dis(int i, int j) {
    return sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
}

double calc_path(int *path) {
    double res = 0;
    for (int i = 0; i < n-1; i++) {
        res += dis[path[i]][path[i+1]];
    }
    res += dis[path[n-1]][path[0]];
    return res;
}

void SA() {
    int path[MAXN];
    for (int i = 0; i < n; i++) {
        path[i] = i;
    }
    double T = 10000;
    double delta = 0.98;
    while (T > eps) {
        int a = rand() % n;
        int b = rand() % n;
        swap(path[a], path[b]);
        double dE = calc_path(path) - calc_path(path);
        if (dE < 0) {
            continue;
        }
        double p = exp(-dE/T);
        double r = (double)rand() / RAND_MAX;
        if (r < p) {
            continue;
        }
        swap(path[a], path[b]);
        T *= delta;
    }
    cout << "最短路径长度为：" << calc_path(path) << endl;
    cout << "最短路径为：";
    for (int i = 0; i < n; i++) {
        cout << path[i] << " ";
    }
    cout << endl;
}

int main() {
    srand(time(NULL));
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            dis[i][j] = dis[j][i] = calc_dis(i, j);
        }
    }
    SA();
    return 0;
}