模拟退火 学习笔记

在这么多高深算法学习笔记中，我的博客显得像个唐比。

看 seve 大佬回回模拟退火打无敌巨大多分，我每场都只能暴力水过去，感觉很不牛，遂决定重新学习模拟退火。

模拟退火就是模拟退火的过程，退火就是慢慢降低温度，让其变得不活跃。

假设有一个最优化问题，不同状态下的答案呈一个不规则的函数状，如果一味地贪心，容易进入局部最优解，所以需要尝试跳出这个部分。

而越到后边越稳定，稳定在一个最优的地方（可能最优）。

具体操作，T 为当前温度，dT 为降温系数，每次降温温度乘上此值，最后在 T 接近于 0 的时候结束。

每次在当前解附近寻找一个新解，需要随着 T 的减小而距离当前解更近。

如果新解比当前解优，那么显然新解成为当前解，否则，则会有一定的概率接受它。

那么概率是多大呢，有神人科学家证明是 e^{\frac{-\Delta E}{T}}，\Delta E 即为新解相对于当前解的变动值。

至于加不加负号，好像是要保证其为正？（作为蒟蒻没写几道，目前来看是的。）

板题（确信）：

P1337 [JSOI2004] 平衡点 / 吊打XXX

long double calc(long double x, long double y) {
    long double res = 0, dis;
    for (int i = 1; i <= n; ++i) {
        dis = sqrt((x - a[i].x) * (x - a[i].x) + (y - a[i].y) * (y - a[i].y));
        res += dis * a[i].w;
    }
    if (res < answ) answ = res, ansx = x, ansy = y;
    return res;
}

void SA() {
    long double x = ansx, y = ansy, w = answ, nx, ny, nw, delta;
    long double T = 1e5, dT = 0.97;
    while (T > 1e-14) {
        nx = x + T * ((rand() << 1) - RAND_MAX);
        ny = y + T * ((rand() << 1) - RAND_MAX);
        nw = calc(nx, ny);
        delta = nw - w;
        if (delta < 0) x = nx, y = ny, w = nw;
        else if (exp(-delta / T) > ((long double)(rand()) / RAND_MAX)) x = nx, y = ny, w = nw;
        T *= dT;
    }
}

int main() {
    srand(time(NULL));
    n = read();
    for (int i = 1; i <= n; ++i) {
        a[i].x = read(), a[i].y = read(), a[i].w = read();
        ansx += a[i].x;
        ansy += a[i].y;
    }
    ansx /= n;
    ansy /= n;
    answ = calc(ansx, ansy);
    int T = 1;
    while (T--) SA();
    printf("%.3Lf %.3Lf", ansx, ansy);
    return 0;
}

试试更新了全局最优解，可以设置退火次数，也可以进行卡时操作。