在这里准备总结一下使用模拟退火时的经验和技巧。

先上个成功案例(其中的注释很重要)

牛客2021-5-J

题意经过简化后就是将z,v数组和t数组一一对应匹配，求最小的$\sum(z_i+v_i\cdot t_j)^2$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
const int maxn=333;
int n,m,a[maxn],x[maxn],y[maxn],z[maxn],v[maxn];
int choice[maxn];
LL ans=1e18,sum;
int num=0;
LL sqr(const LL &x){return x*x;}
void doit()
{
    long double T=1e12,q=0.999;//T为初始温度，是一个应该设置的时候应该差不多和sum-sumt成正比的值；q是降温速度，需要慢慢调参
    while (T>1e-6)//末态温度，可以控制结果的精度和所花的时间（比如函数进入了一个深谷，总不能没走到底就跑出来，也不应该在底上逗留一半时间吧）
    {
        rep(times,1,20)//这里调整：每几次变化尝试造成一次温度降低
        {
            /////////这一段是尝试变化
            LL sumt=sum;
            int r1=rnd()%n,r2=rnd()%n;
            if (r1==r2) continue;
            sumt-=sqr(z[choice[r1]]+v[choice[r1]]*r1);
            sumt-=sqr(z[choice[r2]]+v[choice[r2]]*r2);
            swap(choice[r1],choice[r2]);
            sumt+=sqr(z[choice[r1]]+v[choice[r1]]*r1);
            sumt+=sqr(z[choice[r2]]+v[choice[r2]]*r2);
            //////////判断是否接受当前变化
            if (sumt<sum)//如果更优 一定接受
            {
                sum=sumt;
                ans=min(ans,sum);
            }
            else if (exp((sum-sumt)/T)*RAND_MAX>((unsigned int)rnd())%RAND_MAX) sum=sumt;//退火的核心-接受更劣解，这里的公式要注意是否写反等问题，下面附了
            else swap(choice[r1],choice[r2]);//撤回变化
        }
        if (T>1e-3) T*=q;
        else T*=0.7;//当温度较低的时候多半是在谷里了，可以稍微加点速
    }
}
bool cmp(const int &x,const int &y){return v[x]>v[y];}
bool cmp2(const int &x,const int &y){return z[x]>z[y];}
int main()
{
#ifdef DEBUG
    freopen("a.in","r",stdin);//先在本地测数据很重要
#endif
    srand(time(0)^19260817);
    read(n);
    rep(i,0,n-1) {read(x[i],y[i]);read(z[i],v[i]);}
    LL sum_static=0;
    rep(i,0,n-1) sum_static+=sqr(x[i])+sqr(y[i]);
    int t=1;
//////////////////////
    while (t--)
    {
        rep(i,0,n-1)
        {
            choice[i]=i;//直接按照输入顺序进行的初始状态
            sum+=sqr(z[i]+v[i]*i);
        }
        ans=min(ans,sum);
        doit();
    }
//////////////////////
    t=1;
    while (t--)
    {
        sum=0;
        sort(choice,choice+n,cmp);//第一种sort的初始状态
        rep(i,0,n-1) sum+=sqr(z[choice[i]]+v[choice[i]]*i);
        ans=min(ans,sum);
        doit();
    }
//////////////////////
    t=1;
    while (t--)
    {
        sum=0;
        sort(choice,choice+n,cmp2);//第二种sort的初始状态
        rep(i,0,n-1) sum+=sqr(z[choice[i]]+v[choice[i]]*i);
        ans=min(ans,sum);
        doit();
    }
//////////////////////
    t=1;
    while (t--)
    {
        sum=0;
        random_shuffle(choice,choice+n);//随机初始状态
        rep(i,0,n-1) sum+=sqr(z[choice[i]]+v[choice[i]]*i);
        ans=min(ans,sum);
        doit();
    }
//////////////////////
//上面是对于不同初始态都做一遍模拟退火，其中random_shuffle的情况可以多做几次。sort主要用于应对特殊构造的数据，或是优先先找出某几个谷中的最优值
//经过测试，对于本题，前三种模式各做一遍即可ac；若去掉第一种，将random多试两次也可通过
    cout<<ans+sum_static<<endl;
    return 0;
}

接受更劣方案概率的公式：
$$
P(Accept)=exp(\frac{-\Delta x}{T})
$$

经验：

  1. 能用本地数据测试就尽量用本地生成数据测试。输出每一步的值察看收敛情况
  2. 多种方式都进行尝试，比如只跑没几次但每次都跑很久（应对谷很深的情况）；以及多撒初始点但每次跑到差不多就停下（应对谷很宽的情况）
  3. 对于某些退火感觉收敛情况不太好的，但是过题人数不少的，甚至可以尝试把退火的接受更劣解删了变爬山，贪心看看是不是能出更优解。如果是的话，很可能就要往贪心角度思考了(贪心能出最优解的话其实就是一个谷又宽又深但是相对平坦，退火跳来跳去反而浪费了很多时间)（牛客2021-1-K）

通过运气、经验和多次尝试，加上出题人的善意，相信就能ac了