题解 P1337 【[JSOI2004]平衡点 / 吊打XXX】

## 吐槽 模拟退火。。一个神奇的算法。。 （这道题目其实叫被XXX吊打） 这个算法靠随机。。也就是靠你的脸。。脸白一点，参数用得优秀一点就过了。。。（比如我把参数从2000换成2333就过了orz） 然后。。正式介绍一下 ## 模拟退火（SA） 可以去看看这一篇讲稿：https://www.cnblogs.com/rvalue/p/8678318.html 解释一下温度是什么东西：其实就是控制随机波动大小的参数，越接近最优解，你就要降温，也就是让T温度变小，这样就可以让随机的幅度变小，不断逼近最优解。 温度不能取太小，不然会被困在局部最优解。 根据图感性理解一下：  那么为什么叫温度呢。。因为这个东西和热力学有关orz 引用一下我发的连接里面的大佬说的： 根据热力学规律并结合计算机对离散数据的处理, 我们定义: 如果当前温度为 T , 当前状态与新状态之间的能量差为 ΔE , 则发生状态转移的概率为: P(ΔE)=e^(ΔE/kT) 显然如果 ΔE 为正的话转移是一定会成功的, 但是对于 ΔE< 我们则以上式中计算得到的概率接受这个新解。 也就是说，更优的解一定要，不优的解也不能完全不要。 我们对于不优的解，我们也要去拓展一下，不能一味取最优解，不然很容易被困在局部最优解。 ## 解法 一个重物的重力势能是和它的离地距离成正比的，因为绳长和桌面离地高度是不变的，我们可以转化为绳结到洞的距离和重力势能成正比。在比较解是否更优时，我们算出总的重力势能（可以拿距离*重力），当然是重力势能小的更优。 剩下的。。就是套模拟退火了 ## 程序 ```cpp #include<ctime> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; double T; struct node { double x,y,w; }p[1100]; double x,y; double GPE(double ux,double uy)//重力势能计算 { double sum=0; for(int i=1;i<=n;i++) sum+=sqrt((ux-p[i].x)*(ux-p[i].x)+(uy-p[i].y)*(uy-p[i].y))*p[i].w; return sum; } void SA() { T=2333.0;//信仰2333吧 double xx=x,yy=y; while(T>1e-16)//小于终温就退出，终温是控制精度的 { double vx=xx+(2.0*rand()-RAND_MAX)*T,vy=yy+(2.0*rand()-RAND_MAX)*T;//波动区间在-RAND_MAX*T ~ RAND_MAX*T double del=GPE(vx,vy)-GPE(xx,yy);//gravitational potential energy if(del<0) x=xx=vx,y=yy=vy; else if(exp(-del/T)*RAND_MAX>rand()) xx=vx,yy=vy;//相乘比较的精度会高一些 T*=0.997;//乘上降温系数 } } int main() { srand(time(NULL)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].w),x+=p[i].x,y+=p[i].y; x/=(double)n,y/=(double)n;//取平均值好一些 SA(),SA(); printf("%.3lf %.3lf",x,y); return 0; } ``` ## 忠告 ~~如果总有一两个点过不了，换一些玄学的参数~~ ~~还是过不了，那是你脸太黑了。。让欧洲人帮你改参数、交代码吧。。。~~ 如果发现经常陷入局部最优解的话考虑增大初始的T和降温系数 , 如果发现最终精度不够的话考虑减小终温