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

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

牛客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了