模拟退火学习笔记
longdie
2020-12-31 14:53:01
# 模拟退火学习笔记
---
#### [学习链接](https://www.luogu.com.cn/blog/Darth-Che/mu-ni-tui-huo-xue-xi-bi-ji)
这一篇讲的很详细，但是前面似乎没啥用，主要看一遍他给的代码就够了。
还有就是看一看他给的注意点。
然后推荐一道例题（板子题）
#### [题目链接](https://www.luogu.com.cn/problem/P1337)
这题建议直接看题解，就当板子题学习，不要管其他的计算几何。
然后是代码 ：
```
#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;
}
```