模拟退火

简介

模拟退火是一种随机化算法。
对于一个当前最优解附近的非最优解，爬山算法直接舍去了这个解。而很多情况下，我们需要去接受这个非最优解从而跳出这个局部最优解，即为模拟退火算法。
当一个问题的方案数量极大（甚至是无穷的）而且不是一个单峰函数时，常使用模拟退火求解。

实现

如果新状态的解更优则修改答案，否则以一定概率接受新状态。

模拟退火时有三个参数：初始温度T_0，降温系数d ，终止温度T_k。

是一个比较大的数（至少需要大于搜索范围，）是一个非常接近但是小于的数是一个接近的正数定义当前温度为，新状态与已知状态（由已知状态通过随机的方式得到）之间的能量差为，（当要求的为最大值时）发生状态转移（修改最优解）的概率为当新解优于最优解时，

否则P(Delta E)=e^{frac{Delta E}{T}}

首先让温度T=T_{0}，进行转移尝试，再让T=T*d。当T 有时为了使得到的解更有质量，会在模拟退火结束后，以当前温度在得到的解附近多次随机状态，尝试得到更优的解（其过程与模拟退火相似）。

随着温度的降低，跳跃越来越不随机，最优解也越来越稳定

例题

1.JSOI2004平衡点/吊打XXX

当重力势能最小时稳定，将物理模型简化
设桌子的高度为h，绳子的长度为l,每个点到x的距离为dis[i]
重力势能为sum_{i=1}^{n}(h-(l-dis[i]))*W[i]

由于h-l为定值，所以重力势能最小的情况等价于sum_{i=1}^{n}dis[i]*W[i]最小
即 求n个点的带权费马点

#include
#define For(i,a,b) for(int i=(a),i##_=(b);i<=i##_;++i)
#define M 1005
#define db double
using namespace std;
int X[M],Y[M],W[M],n;
db ans,ansx,ansy;
db Pow(db x){return x*x;
}
db Dis(db x,db y){return sqrt(Pow(x)+Pow(y));
}
db Rand(){return (db)rand()/RAND_MAX;//返回一个[0,1]之前的小数
}
db Cal(db x,db y){db res=0;For(i,1,n)res+=Dis(x-X[i],y-Y[i])*W[i];//在Cal中更新答案if(resTk){//Rand()*2-1 返回一个[-1,1]之间的数db nxtx=nowx+T*(Rand()*2-1);db nxty=nowy+T*(Rand()*2-1);db tmp=Cal(nxtx,nxty)-Cal(nowx,nowy);//tmp<0 即新解更优，那么一定接受新解//否则 以一定概率接受新解if(tmp<0||exp(-tmp/T)>Rand())nowx=nxtx,nowy=nxty;T*=d;}//以当前温度在得到的解附近多次随机状态，尝试得到更优的解int t=1000;For(i,1,t){db nxtx=ansx+T*(Rand()*2-1);db nxty=ansy+T*(Rand()*2-1);Cal(nxtx,nxty);}
}
int main(){srand(20020310);scanf("%d",&n);For(i,1,n){scanf("%d%d%d",&X[i],&Y[i],&W[i]);ansx+=X[i],ansy+=Y[i];}//初始值可以随机，在本题中采用所有点坐标的平均值ansx/=n,ansy/=n;ans=Cal(ansx,ansy);SimulateAnneal();printf("%.3f %.3f
",ansx,ansy);return 0;
}