模拟退火板子

参数

初始温度 \(tmp\)， 降温系数 \(\Delta\)。

接受不优解的条件

卡时间代码

while((double)clock()/CLOCKS_PER_SEC < 时限) 模拟退火();

板子

double ans=1e18;
struct ANS_type {
    /*
        balabala
    */
} ansnode;

double t;
const double delta = 0.993;
void SA() {
    t = 2000.0;
    ANS_type nownode = ansnode;
    //可能要SA多次， 从上一次结束的地方继续
    while(t>1e-14) {
        /*
            随机生成一个新解， 当前解与新解的距离 通常与温度有关 
        */
        if(calc_ans(新解) 优于 ans) {
            ans = calc_ans(新解);
            nownode = ansnode = 新解 
        } else if(exp(-当前解与最优解的差/t)*RAND_MAX > rand()) {
            nownode = 新解; 
        }
        t *= delta;
    }
}

例题代码

#[JSOI2004]平衡点 / 吊打XXX

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n;
int x[maxn], y[maxn], w[maxn];

double calcans(double X, double Y) {
    double res = 0;
    for(int i=1;i<=n;++i) {
        double dx = x[i]-X, dy=y[i]-Y;
        res += sqrt(dx*dx+dy*dy) * w[i];
    }
    return res;
}

double ans=1e18, ansx, ansy;
double t;
const double delta = 0.994;
void SA() {
    double X=ansx, Y=ansy;
    t = 3000;
    while(t>1e-14) {
        double nowx = X + (rand()*2-RAND_MAX)*t;
        double nowy = Y + (rand()*2-RAND_MAX)*t;
        double nowans = calcans(nowx, nowy);
        double Delta = nowans - ans;
        if(Delta < 0) {
            ansx = X = nowx, ansy = Y = nowy;
            ans = nowans;
        } else if(exp(-Delta/t)*RAND_MAX > rand()) X=nowx, Y=nowy;
        t*=delta;
    }
}

int main()
{
    srand(13333337); srand(rand()); srand(rand());

    int sx=0, sy=0;
    scanf("%d", &n);
    for(int i=1;i<=n;++i)
        scanf("%d%d%d", &x[i],&y[i],&w[i]), sx+=x[i], sy+=y[i];
    ansx = (double)sx/n, ansy=(double)sy/n;
    SA();
    SA();
    SA();
    printf("%.3lf %.3lf\n", ansx, ansy);
    return 0;
}