模拟退火学习（030920一上午成果）
目录前言：
emmmm。
你还在考虑dp死活写不出来吗？
你还在担忧贪心算法的正确性吗？
模拟退火，不要9998，只要你有耐心看完我的博客。
学会模拟退火，去骗分吧！
1. 爬山算法
由来：
想想爬山的过程，要是想爬到最高峰的话，我现在在半途看不到前面更多的山的高度，但我知道离我
最近几座山的高度，我肯定会选择去爬这几座里面最高的那个，剩下的不在看了。这就是爬山，永远找的是当前最优。
于是就会有很明显的问题：全局最优非局部最优。但是可以拿来骗分，换句话说，当达到解的方案数很少时，成功概率较大。
但是真正的题怎么可能方案数较少呢？
2.模拟退火：
算法流程：
可以说是对爬山算法的一点改进吧。
因为我直接舍弃局部不优解太过了，于是呢，就有了下面的情况：
当在当前状态下找到更优秀局部转移时，我们还是让他100%转移，但是在不优秀的局部最优解下，也让他有一定概率转移。
初学（我）的问题
大概明白了算法流程，于是问题来到：
- 我该怎么写，怎么应用于其他题上？
- 时间复杂度该如何保证？
- 我为什么要随机，随机什么？
然后我就去万能的luogu上问了下
这是讨论帖：https://www.luogu.com.cn/discuss/690367?page=1&sort=time-d
由于我也是初学者，对于这几个东西，我只能说，必须要看懂别人的做题思路什么的才明白。
用题来进行理解：
BZOJ1844 Run Away（cqbz的oj上有）
注释暂时贴到了代码里面：
#include<bits/stdc++.h>
using namespace std;
struct node{
double x;
double y;
}p[1005];
/*
求距离所有点的最小值最大
*/
double dis(double x,double y,double xx,double yy){
return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
int n;
double limitx,limity;
double cal(double x0,double y0){
double ret=1e9;
for(int i=1;i<=n;i++){
ret=min(ret,dis(x0,y0,p[i].x,p[i].y));
}
return ret;//尝试x0,y0这个坐标下的答案
}
//以上是对答案的计算部分
const int T0=10000;//初始温度
const double d=0.98; //降温系数
const double Tl=1e-14;//最终降到的温度
double ansx,ansy;//最终答案
double RD(double T){
return T*(rand()*2-RAND_MAX);
}
void fire(){
int times=10;//多做几次退火减少偶然性问题
double best=cal(ansx,ansy);//确定自己最初取得的较优解的答案
//注意这里best是写在times之外的，用于表示最终答案的最优值
while(times--){
double ans=best;//ans再times循环内，表示是这一次退火的最终答案
double mayx=ansx;
double mayy=ansy;
for(double T=T0;T>=Tl;T*=d){//模拟降温过程
double xx=mayx+RD(T);
double yy=mayy+RD(T);
//尝试新的答案，新的答案由上一次答案随机得到.
if(xx>limitx||yy>limity||xx<0||yy<0){
continue;//不在范围内的可能性直接byebye
}
double nowans=cal(xx,yy);
if(best<nowans){//如果答案更好，更新答案组成 （同于对比全局的最优值）
best=nowans;
ansx=xx;
ansy=yy;//全局的最优秀
}
if(ans<nowans||exp((ans-nowans)/T)<=1.0*rand()/RAND_MAX){//寻找局部最优，要不然答案优秀直接更新，要不然随机化更新以跳出可能的局部最优解问题
ans=nowans;
mayx=xx;
mayy=yy;
}
}
}
}
//以上是模拟退火
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
srand(time(NULL));
while(t--){
cin >> limitx >> limity >> n;
ansx=0;
ansy=0;
for(int i=1;i<=n;i++){
cin >> p[i].x >> p[i].y;
ansx+=p[i].x;
ansy+=p[i].y;
}
ansx/=n;
ansy/=n;//刚开始时建立一个初始答案，这里取得平均值。其实就是你感觉什么答案可能有点优秀就可以尝试把它当为初值。
//基本输入
fire();
printf("The safest point is (%.1lf, %.1lf).\n",ansx,ansy);
}
}
回顾上面的问题：
对于Q1
- 我认为退火的过程很明显嘛，就是让T一直变小并且变小的幅度逐渐减小噻。
但是这个T到底有什么用？（代码里面有关rand的都没写注释嘛）
于是就有了一下几个小问题：
Q1.1: 代码上exp((ans-nowans)/T)<=1.0*rand()/RAND_MAX是什么意思？
ans:这个东西呢，前面如oiwiki内所说是e的(ΔE/T)次方，表示接受局部较差解的概率。
但又不完全是概率，因为这个概率要随机，于是嘛就有了后面的rand这个东西。
Q1.2: 代码上：double xx=mayx+RD(T);double yy=mayy+RD(T);为什么这么写？
ans:其实T的意义还可用于控制当前最优解下最新最优解的范围，随着T的减小，这个范围也就不断减小，最后趋于稳定，得到最终答案。
但是还是要看概率，所以加个times来尽量避免这种情况。
Q1.3: RD函数的用途
ans:用于控制某一温度下的最优解delta。
对于Q2：
先上结论：时间复杂度在模拟退火中是难以保证的，我们要做到的是：能算就算，尽量多算（以保证答案尽量ok）。
这个时间是和T0,Tl,D,times有关系的。（相信大家也看得出来某个变量变大变小对全局的影响）。
计算的话，大家应该是算得出来的。’
关键在于时间复杂度太高时，这几个变量的取舍。
好的于是又有了一下的分枝问题：
Q2.1：T0的取舍
ans:你的取舍范围肯定是要覆盖到全部值域的，因此你的T0不能特别小，建议开到ans范围限制左右。
Q2.2：times的取舍
ans:大概在5到10次左右就好了，反正在保证Tl和D尽量细的情况下，扒点他们的时间过来。
注：比如说前者用了1e8次计算，你可以稍微让前者粗糙到1e7次计算然后给times10次。
Q2.3：D和lT的取舍(也可以说是一种两者间的博弈）
D想要尽力靠近1，lT希望尽力靠近0。
考虑D的作用：每次让T减小，同时也让接受坏解的概率/选择范围减小。
考虑lT的作用：感觉就是一个下届。
看到上面两者......感觉肯定是优先满足D 再lT呗.
D给个0.98，T0给个10000，LT给个1e-14差不多。
（但还是有概率会G，所以有T组询问的还是尽量别想这种方法吧）
Q2的补充：
你会发现其实每一次我都要用n的时间计算当前随机出来的答案是多少对吧。
这个时间复杂度也要计算哦。
其实呢，我个人觉得，大不了牺牲D到0.95，LT 到1e-6。（这就不是靠运气而是靠寿命了）
对于Q3
我认为在代码中和Q1中，您看的应该差不多清楚了。
这里就（补充）一点：
祝您在考试中遇到模拟退火时rp++。
哦不，最好是++rp。