模拟退火学习笔记

· · 个人记录

模拟退火学习笔记

学习链接

这一篇讲的很详细，但是前面似乎没啥用，主要看一遍他给的代码就够了。
还有就是看一看他给的注意点。
然后推荐一道例题（板子题）

题目链接

这题建议直接看题解，就当板子题学习，不要管其他的计算几何。
然后是代码 ：

#include <bits/stdc++.h>
#define down 0.996
#define Max RAND_MAX
using namespace std;
int n;
struct node { int x, y, w; } object[2005];
double ansx, ansy, answ;
double suan(double x, double y) {
    double ans = 0, dx, dy;
    for(int i = 1; i <= n; ++i) {
        dx = x - object[i].x, dy = y - object[i].y;
        ans += sqrt(dx*dx + dy*dy) * object[i].w;
    }
    return ans;
}
void monituihuo() {
    double t = 10000;
    while(t > 1e-15) {
        double ex = ansx + (rand()*2 - Max)*t;
        double ey = ansy + (rand()*2 - Max)*t;
        double ew = suan(ex, ey);
        double cha = ew - answ;
        if(cha < 0) {
            ansx = ex, ansy = ey, answ = ew;
        }
        else if(exp(-cha / t) * Max > rand()) {
            ansx = ex, ansy = ey;
        }
        t *= down;
    }
}
void solve() {
    monituihuo();
    monituihuo();
    monituihuo();
    monituihuo();
    monituihuo();
}
int main() {
    srand(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> object[i].x >> object[i].y >> object[i].w;
        ansx += object[i].x, ansy += object[i].y;
    }
    ansx /= n, ansy /= n, answ = suan(ansx, ansy);
    solve();
    printf("%.3lf %.3lf", ansx, ansy);
    return 0;
}