模擬Δεῦρο fire

2023-11-05 11:50:10

0、抱歉标题党。

其实是模拟退火……

众所周知，检验 \(\huge\color{red}{RP}\) 的最佳方式就是退火。。。

然而有时并不是 \(\huge\color{red}{RP}\) 的问题，可能就是写挂了。。。

为了有效地提升 \(\huge\color{red}{RP}\) 并减少因写挂而带来的RP--的心理创伤，还是有必要注意一下的。

1、原理

一点也不高大上。

产生随机答案
计算答案
若比当前答案更优则接受，否则以一定概率接受
进行下一次随机计算

然后就是退火的精髓所在了：

产生随机答案时采用局部调整的方式，且调整量 随着枚举次数增多而减少
接受较劣解的概率 随着枚举次数增多而减少

然后保证 随着枚举次数增多而减少 的方式就是每次降温，温度越低越稳定。

2、写法 && 坑点

1、关于时间的判断

while((double)clock()/(double)CLOCKS_PER_SEC<=0.8){
	sa();
}

2、初始值

初温T=1e8，降温常数dn=0.996，终止值eps=1e-10

3、概率

if(exp((pans-anss)/T)*RAND_MAX>rand()){
	接受;
}

exp是一个指数函数，

exp(10)=22026.46579481
exp(2)=7.38905610
exp(1)=2.71828183
exp(0.2)=1.22140276
exp(0)=1.00000000
exp(-0.2)=0.81873075
exp(-1)=0.36787944
exp(-2)=0.13533528
exp(-10)=0.00004540

所以exp里面是一个（负数/T）的形式，保证了 "温度越高越容易接受较劣解" 且函数值在0~1之间。

注意是大于号，函数值越大越容易进入大括号。

4、调参

如果一直得不到最优解，可以增加T和dn。精度不够可以减小最终温度。
关于SA()的次数，可能不是那么有所谓……
剩下你要做的就是 少打兵兵球 以增加RP……

3、一些废话

用来骗分。。。想切掉一道数据较强的题基本在想桃子……

然后就是网上有一段话：

兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。
兔子们被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己应该向上爬。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。
兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是记忆化搜索。

码农公寓