模拟退火死了,求助
  • 板块P1433 吃奶酪
  • 楼主nalemy
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/3/8 22:27
  • 上次更新2023/11/5 02:17:10
查看原帖
模拟退火死了,求助
360214
nalemy楼主2021/3/8 22:27

谁能帮我看看我的模退错在哪里了,为什么一直在406040\sim60之间徘徊

#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#define N 20
#define T0 1e7
#define eps 1e-4
#define dlt 1-3e-3
#define L 500
using namespace std;

int n, cur[N];
struct point {
    double x, y;
} p[N+1];
double dis(int i, int j) {
    return hypot(p[i].x-p[j].x, p[i].y-p[j].y);
}
double calc() {
    double sm = dis(cur[0], n);
    for (int i=1; i<n; i++)
        sm += dis(cur[i-1], cur[i]);
    return sm;
}
double randflt() {
    return 1.0 * rand() / RAND_MAX;
}
// 左闭右开!!!
int randint(int l, int r) {
    return int(randflt() * (r - l)) + l;
}
bool check(double delta, double t) {
    return delta > 0 || randflt() < delta / t;
}
double SA() {
    int t = T0;
    double cs = calc();
    while (t > eps) {
        srand(rand());
        for (int i=0; i<L; i++) {
            int u = randint(0, n), v = randint(0, n);
            swap(cur[u], cur[v]);
            double ts = calc();
            if (check(cs-ts, t)) cs = min(cs, ts);
            else swap(cur[u], cur[v]);
        }
        t *= dlt;
    }
    return cs;
}
int main() {
    cin >> n;
    srand(time(NULL));
    for (int i=0; i<n; i++)
        cin >> p[i].x >> p[i].y, cur[i] = i;
    printf("%.2f", SA());
    return 0;
}

感觉跟题解的模退没啥区别

可能就是我脸黑

2021/3/8 22:27
加载中...