引入
模拟退火是一种随机化算法，当一个问题方案数量极大且非单峰时，我们常使用模拟退火
过程
先引入几个参数：当前最优解 \(E_0\) ，新解 \(E\) ，解变动量 \(\Delta E\) （即 \(E\) 与 \(E_0\) 的差），上一个被接受的解 \(E_1\) ，初温 \(T_0\) ，末温 \(T_k\) ，当前温度 \(T\) ，温度变动量 \(\Delta\)
从 \(T_0\) 开始，每次乘上 \(\Delta\) 得到 \(T\) ，如果 \(T < T_k\) 则终止降温
在降温的同时，我们在 \(E_1\) 的基础上扰动产生新解 \(E\) （扰动大小随温度降低而变小，因为温度高时解的变化量很大，此时的任务是在全局范围中找到最优解的大致位置；随着温度的降低，解逐渐稳定，此时的任务就是确定最优解的准确位置）
每次得出新解之后，我们用Metropolis准则来接受它，假设我们碰到一个更优解，那我们就接受当前解，否则我们也要以一定概率接受更劣解，否则就会局限在一个局部峰值，而这个概率是 \(\exp(-\dfrac{\Delta}{T})\)
一般来说，对于 \(\Delta E\) ，如果其较大，即我们遇到一个差得很的解，那我们接受的概率就比较小，否则接受的概率更大。对于 \(T\) ，随着时间增加，\(T\) 变得越来越小，故我们只会接受 \(\Delta E\) 较小的解
\(T_0\) 一般设置在 \(1 \times 10^3 \sim 5 \times 10^3\) ，\(\Delta\) 则是一个略小于 \(1\) 的常数， \(T_k\) 一般设置在 \(10^{-8} \sim 10^{-15}\)
分块模拟退火
函数的峰很密集时模拟退火是不好用的，这时可以用分块模拟退火的做法，将其分为几块，然后对每块跑一遍模拟退火，最后再合并答案
随机化技巧
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
inline double rd(double l, double r) {
return uniform_real_distribution<>(l,r)(gen);
}
应用
求最小值
#include <bits/stdc++.h>
using namespace std;
const double delta = 0.997, T0 = 3e3, Tk = 1e-17;
const int N = 5e3 + 7;
struct Point {
double x, y;
} a[N];
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
double ax, ay, nx, ny, ans;
int n;
inline double rd(double l, double r) {
return uniform_real_distribution<>(l, r)(gen);
}
inline double calc(double x, double y) {
double res = 0;
for (int i = 1; i <= n; ++i)
res += sqrt((x - a[i].x) * (x - a[i].x) + (y - a[i].y) * (y - a[i].y));
return res;
}
inline void SimulateAnneal() {
for (double x = nx, y = ny, T = T0; T > Tk; T *= delta) {
double _x = x + T * rd(-1000, 1000);
double _y = y + T * rd(-1000, 1000);
double now = calc(_x, _y), deltaE = now - ans;
if (ans > now) {
nx = _x, ny = _y;
x = _x, y = _y;
ans = now;
} else if (exp(-deltaE / T) > rd(0, 1))
x = _x, y = _y;
}
}
signed main() {
srand(time(NULL));
int T;
scanf("%d", &T);
for (; T; --T) {
scanf("%d", &n);
ax = ay = 0, ans = 1e18;
for (int i = 1; i <= n; ++i) {
scanf("%lf%lf", &a[i].x, &a[i].y);
ax += a[i].x, ay += a[i].y;
}
nx = ax / n, ny = ay / n;
SimulateAnneal();
SimulateAnneal();
SimulateAnneal();
SimulateAnneal();
SimulateAnneal();
printf("%.0lf\n", round(ans));
if (T > 1)
putchar('\n');
}
return 0;
}
求最大值
#include <bits/stdc++.h>
using namespace std;
const double delta = 0.9997, T0 = 2.5e3, Tk = 1e-8;
const double eps = 1e-8, MaxTime = 0.8;
const int N = 1e3 + 7;
struct Building {
double x, y, r;
} a[N];
struct Enemy {
double x, y;
} b[N];
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
double R, nx, ny;
int n, m, ans;
inline double rd(double l, double r) {
return uniform_real_distribution<>(l,r)(gen);
}
inline double dist(double x, double y, double xx, double yy) {
return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}
inline int calc(int x, int y) {
double maxlen = R;
for (int i = 1; i <= n; ++i)
maxlen = min(maxlen, dist(x, y, a[i].x, a[i].y) - a[i].r);
if (maxlen < 0)
return 0;
int res = 0;
for (int i = 1; i <= m; ++i)
if (dist(x, y, b[i].x, b[i].y) < maxlen + eps)
++res;
return res;
}
inline void SimulateAnneal() {
for (double x = nx, y = ny, T = T0; T > Tk; T *= delta) {
double _x = x + T * rd(-10, 10);
double _y = y + T * rd(-10, 10);
double now = calc(_x, _y), deltaE = now - ans;
if (ans < now)
nx = x = _x, ny = y = _y, ans = now;
else if (exp(-deltaE / T) < rd(0, 1))
x = _x, y = _y;
}
}
signed main() {
scanf("%d%d%lf", &n, &m, &R);
for (int i = 1; i <= n; ++i)
scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r);
double bx = 0, by = 0;
for (int i = 1; i <= m; ++i) {
scanf("%lf%lf", &b[i].x, &b[i].y);
bx += b[i].x, by += b[i].y;
}
nx = bx / m, ny = by / m;
ans = calc(nx, ny);
while ((double)clock() / CLOCKS_PER_SEC < MaxTime)
SimulateAnneal();
printf("%d", ans);
return 0;
}