模拟退火模板

用于随机优化暴力。

• 适用条件：函数具有连续性。

• 温度（步长）：初始温度、终止温度、衰减系数。

• 随机一个初始点。

• 当前点为 $x$ ，随机选择一个点 $y$ ，$\Delta E = f(y) - f(x)$ 。

  • 若 $\Delta E < 0$ ，则跳到新点；
  • 若 $\Delta E > 0$ ，则以一定概率 $ e ^ {- \frac {\Delta E} T}$ 跳过去。即差的越多，则概率越小；否则越大。

• 为了得到全局答案，可以做很多次模拟退火。

• 卡时间的方式

  while ((double)clock() / CLOCKS_PER_SEC < 0.9)
      SimulateAnneal();

• 初始点可以贪心尽量靠近答案。

例题：计算 $n$ 个重物的平衡点。

查看代码

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <utility>
using namespace std;
typedef pair<double, double> PDD;
const int N = 1010;
int n;
struct Point
{
    double x, y, w;
} p[N];
PDD ans;
double mn = 1e12;
double rand(double l, double r)
{
    return (double)rand() / RAND_MAX * (r - l) + l;
}
double cal(PDD x)
{
    double res = 0;
    for (int i = 0; i < n; i++)
    {
        double dx = x.first - p[i].x, dy = x.second - p[i].y;
        res += sqrt(dx * dx + dy * dy) * p[i].w;
    }
    if (res < mn)
    {
        ans = x;
        mn = res;
    }
    return res;
}
void SimulateAnneal()
{
    PDD cur(rand(0, 1e4), rand(0, 1e4));
    for (double t = 1e4; t > 1e-5; t *= 0.996)
    {
        PDD np(rand(cur.first - t, cur.first + t), rand(cur.second - t, cur.second + t));
        double delta = cal(np) - cal(cur);
        if (exp(-delta / t) > rand(0, 1))
            cur = np;
    }
}
int main()
{
    srand(time(NULL));
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].w);
    while ((double)clock() / CLOCKS_PER_SEC < 0.9)
        SimulateAnneal();
    printf("%.3lf %.3lf", ans.first, ans.second);
    return 0;
}