模拟【淬】火

a_small_penguin · 2025-11-30 23:15:55 · 算法·理论

人类的智慧

既然有模拟退火，那为什么不能有模拟淬火呢？

模拟退火是不断地降温，这时候发挥人类的智慧，想到如果是升温呢？

不难发现这种情况下是在一个小范围内密集搜索，然后再大范围的粗略搜索。于是淬火和退火就有了显著的区别：退火是范围不断收敛，而淬火则是不断开放。

那这样子有什么用呢？嗯，好像得到正确答案的概率是很低的。但是经过实际测试，它的正确性基本劣于退火很多，甚至疑似略优一些。

于是拿了几道题来测试了一番。

P1337 [JSOI2004] 平衡点 / 吊打XXX

代码是这样的：

#include<bits/stdc++.h>
using namespace std;
int n;
int x[1009];
int y[1009];
int w[1009];

double ansx, ansy, answ;

double engery(double _x, double _y) {
    double r = 0, dx, dy;
    for(int i = 1; i <= n; i++) {
        dx = _x - x[i];
        dy = _y - y[i];
        r += sqrt(dx * dx + dy * dy) * w[i];
    }
    return r;
}

void sa() {
    double t = 1e-15;
    while(t <= 3000) {
        double ex = ansx + (rand() * 2.0 - RAND_MAX)*t;
        double ey = ansy + (rand() * 2.0 - RAND_MAX)*t;
        double ew = engery(ex, ey);
        double de = ew - answ;
        if(de < 0) {
            ansx = ex;
            ansy = ey;
            answ = ew;
        }else if(exp(-de/t) * RAND_MAX > rand()) {
            ansx = ex;
            ansy = ey;
        }
        t*=1.003;

    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> w[i];
        ansx += x[i];
        ansy += y[i];
    }    
    ansx/=n;
    ansy/=n;
    answ = engery(ansx, ansy);
    while((double)clock()/CLOCKS_PER_SEC<0.95)sa();
    printf("%.3lf %.3lf",ansx,ansy);
    return 0;
}

思考

不难发现我的马蜂非常丑陋仅有三句代码和退火有差别 double t = 1e-15，while(t <= 3000) 和 t *= 1.003。

显然这非常的诡异，因为按照推论，淬火是开放的，很难找到正确的答案，但是我大致想到了正确的原因：while((double)clock()/CLOCKS_PER_SEC<0.95)。这是一段用来卡时的。如果把这个删去，那么分数就会从 78 \sim 100 变为 11 \sim 22。

不难发现是这个卡时代码出现了问题。

略微思考后得出结论，由于每次淬火都是从密集的小范围搜索到大范围，而退火又能对于非最优解进行概率取舍，于是就会出现大致这样的情况：

最终，输出了一个遇到的最优解。

用处

通过它的特性，不难发现它在可以大致预估最优值时可以基本吊打退火（？），比如 NOIP2025T1。

P14635 [NOIP2025] 糖果店 / candy

虽然这道题并不难，但是是一个不错的练手的机会，虽然和退火分不出高低（目前仅限洛谷民间数据）。

不难发现，最优情况基本上都是当重复买的一种糖果 i，购买的次数接近 \frac{2m}{x_i +y_i}，所以直接拿这个数作为淬火的初值来跑即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define eps 1e-10

int n, m;
array<int, 2> a[100009];
int d[100009];
int minn = 0x7f7f7f7f7f7f7f7f;

int ms = -1, md;

inline int check(int x) {
    int i = upper_bound(d, d + n + 2, m - x * minn) - d - 1;
    return x * 2 + i;
}

inline void SA(int seed) {
    mt19937 rnd(seed);
    double t = 3000;
    while(t >= eps) {
        int nd = md + (rnd() * 2.0 - RAND_MAX) * t;
        nd = max(nd, 0LL), nd = min(nd, m / minn);
        int ns = check(nd);
        int d = ms - ns;
        if(d < 0) {
            md = nd;
            ms = ns;
        } else if(exp(-d/t) * RAND_MAX > rnd()) {
            md = nd;
        }
        t *= 0.998;
    }
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    mt19937 rnd(time(0));

    cin >> n >> m;
    for(int i = 1; i <= n ;i++){
        cin >> a[i][0] >> a[i][1];
        if(a[i][0] + a[i][1] < minn) minn = a[i][0] + a[i][1];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n ;i++) {
        d[i] = d[i - 1] + a[i][0];
    }
    d[n + 1] = 0x7f7f7f7f7f7f7f7f;
    md = m / minn;
    SA(rnd());
    cout << ms << "\n";
    return 0;

}

但是经过实践发现，不卡时和卡时的退火和淬火都可以轻松得到100的好成绩（民间数据）。

后记

希望有人能对这个算法（？其实是魔改）进行改进？

参考的资料 ：

1.机房大佬的发明