旅行商问题c++模拟退火

以下是使用C++实现模拟退火算法求解旅行商问题的示例代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const double eps = 1e-8;

int n;
double ans = 1e18;
int path[N], tmp_path[N];
double dis[N][N], tmp_dis[N][N];

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

void SA() {
    double T = 1e4, delta = 0.99;
    memcpy(tmp_path, path, sizeof(path));
    memcpy(tmp_dis, dis, sizeof(dis));
    while (T > eps) {
        int x = rand() % n + 1, y = rand() % n + 1;
        while (x == y) y = rand() % n + 1;
        swap(tmp_path[x], tmp_path[y]);
        double delta_dis = calc(tmp_path) - calc(path);
        if (delta_dis < 0 || exp(-delta_dis / T) * RAND_MAX > rand()) {
            memcpy(path, tmp_path, sizeof(path));
            memcpy(dis, tmp_dis, sizeof(dis));
            if (calc(path) < ans) {
                ans = calc(path);
            }
        } else {
            swap(tmp_path[x], tmp_path[y]);
        }
        T *= delta;
    }
}

int main() {
    srand(time(NULL));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%lf", &dis[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        path[i] = i;
    }
    random_shuffle(path + 1, path + n + 1);
    ans = calc(path);
    SA();
    printf("%.2lf\n", ans);
    return 0;
}