P1337 [JSOI2004]平衡点 吊打XXX
模拟退火
初始温度\(T_0\) 终止温度\(T_k\) 温度变化率\(d\)
\(T_k\)略大于0，\(d\)略小于1
当前状态\(x,y\) 当前解\(E\) 当前最优解\(minE\) 当前温度\(T\)
新状态\(nx,ny\) 新解\(nE\) 新解与当前解差值\(\Delta E = nE-E\)
\(if\)新解比当前解更优\(nE<E\)
当前状态\(x,y\)移动到 \(nx,ny\)
当前解\(E\)移动到\(nE\)
$else \(我们有\)e^{\frac{\Delta E}{kT}}\(的概率使当前状态移动到\)nx,ny\((其中\)k\(为随机数) 当前温度\)T\(降至\)T*d$
最后\(T\)降到等于低于\(T_k\)时，算法结束。
Tips：
1.\(nx,ny\)可通过将\(x,y\)加上一个\([-T,T]内的随机数(T*(Rand()*2-1))\)得到。
其中Rand()函数如下：
inline double Rand(){ ???return double(rand())/double(RAND_MAX);}2.判断当前状态是否能移动到新状态
(本题求的是最小值，因此当\(\Delta E = nE-E\)<0时更优)
inline bool Accept(double delta,double T){ ???return delta<0||Rand()<exp(-delta/T);}3.这是个看脸的算法，这是个玄学的算法。（参见代码中的八位大质数和八遍退火）
4.别学我拿两个退火对拍。。。
AC CODE：(Warning ： 本题不保证每次都能AC)
#include<cstdio>#include<cstring>#include<algorithm>#include<ctime>#include<cstdlib>#include<cmath>using namespace std;const int N = 1000 + 10;int n;struct node{ ???double x,y,w;}a[N];node Ans;double minE;inline double dis(double x,double y,double _x,double _y){ ???return sqrt((x-_x)*(x-_x)+(y-_y)*(y-_y));}inline double cal(double x,double y){ ???double ans=0; ???for(int i=1;i<=n;i++){ ???????double _x=a[i].x,_y=a[i].y; ???????ans+=a[i].w*dis(x,y,_x,_y); ???} ???if(ans<minE){ ???????minE=ans; ???????Ans.x=x,Ans.y=y; ???} ???return ans;}inline double Rand(){ ???return double(rand())/double(RAND_MAX);}inline bool Accept(double delta,double T){ ???return delta<0||Rand()<exp(-delta/T);} void SA(node poi,double T0,double Tk,double d){ ???double x=poi.x,y=poi.y;//当前坐标 ????double E=cal(x,y);//当前解 ????minE=E;//最优解 ????double T=T0;//当前T ????while(T>Tk){ ???????double nx=x+T*(Rand()*2-1),ny=y+T*(Rand()*2-1); ???????//新坐标 T*(Rand()*2-1) 生成[-T,T]内的实数 ????????double nE=cal(nx,ny);//新解 ????????if(Accept(nE-E,T)){//转移 ????????????x=nx,y=ny; ???????????E=nE; ???????} ???????T*=d;//get low ???} ???for(int i=1;i<=1000;i++){ ???????x=Ans.x+T*(Rand()*2-1),y=Ans.y+T*(Rand()*2-1); ???????cal(x,y); ???}}int main(){// ?freopen("data.in","r",stdin);// ?freopen("sol.out","w",stdout); ???srand(19260817);srand(rand());srand(rand()); ???scanf("%d",&n); ???node _;_.x=0,_.y=0; ???for(int i=1;i<=n;i++){ ???????double x,y,w;scanf("%lf%lf%lf",&x,&y,&w); ???????a[i]=(node){x,y,w}; ???????_.x+=x,_.y+=y; ???} ???_.x/=n,_.y/=n; ???double T0=2333,Tk=1e-3,d=1-7e-2; ???SA(_,T0,Tk,d); ???SA(Ans,T0,Tk,d); ???SA(Ans,T0,Tk,d); ???SA(Ans,T0,Tk,d); ???SA(Ans,T0,Tk,d); ???SA(Ans,T0,Tk,d); ???SA(Ans,T0,Tk,d); ???SA(Ans,T0,Tk,d); ???printf("%.3lf %.3lf\n",Ans.x,Ans.y); ???return 0;}P1337 [JSOI2004]平衡点 ?吊打XXX - 模拟退火
原文地址：https://www.cnblogs.com/Loi-Brilliant/p/9780923.html