模拟退火

模拟退火（Simulate Anneal）是一种用于解决问题方案数极大且非单峰函数的随机化算法，原理与金属退火类似。

每次随机出一个新解，若新解更优则接受，否则以一个与温度和与最优解的差相关的概率接受它。

降温

模拟退火有三个参数：初始温度 \(T_0\)，降温系数 \(\Delta\)，终止温度 \(T_k\).

其中 \(T_0\) 为较大的数，\(\Delta\) 为略小于 \(1\) 的正数，\(T_k\) 为略大于 \(0\) 的正数。

初始令温度 \(T=T_0\)，降温时 \(T\rightarrow T\times\Delta\)，直至 \(T\le T_k\).

随着温度降低，解逐渐稳定并集中在最优解附近。

生成新解

在当前解的基础上生成一个新解，方法较多。

调整

若新解更优，接受新解。

否则以一定概率接受解。设 \(\Delta W\) 为新解与当前解的差，我们希望这个概率随 \(T\) 的减小而减小，随 \(\Delta W\) 的减小而减小。

取 \(\displaystyle e^{-\frac{\Delta W}{rT}}\) 作为概率，其中 \(r\) 为随机数。

如果 \(\Delta W\) 的值比较极限就很容易崩掉，可以对 \(r\) 的范围进行一些限制。

精确度提高

为提高随机化算法的正确性，每次退火从上一次的最优解开始能够减小误差。

另外还需要对 \(r\) 的范围、\(\Delta\)、\(T_0\) 和 \(T_k\) 调参。

笼统地，可以增加模拟退火次数，调大 \(\Delta\)，调整 \(T_0\) 和 \(T_k\).

P1337 [JSOI2004] 平衡点 / 吊打XXX

使用模拟退火跑出整个系统能量的最小值。

比运气比不过别人，交了整整七发。

#include<bits/stdc++.h>
#define db double
#define N 1010
#define eps 1e-14
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
struct node{
	int x,y,w;
}a[N];
int n,sx,sy;
db ansx,ansy;
db ans=1e18,t;
const db delta=0.993;
db calc(db x,db y){
	db ret=0,dx,dy;
	for(int i=1;i<=n;i++){
		dx=x-a[i].x,dy=y-a[i].y;
		ret+=sqrt(dx*dx+dy*dy)*a[i].w;
	}
	return ret;
}
void SA(){
	db x=ansx,y=ansy;
	t=2000;
	while(t>eps){
		db X=x+((rand()<<1)-RAND_MAX)*t;
		db Y=y+((rand()<<1)-RAND_MAX)*t;
		db now=calc(X,Y),Delta=now-ans;
		if(Delta<0){
			x=X,y=Y;
			ansx=x,ansy=y,ans=now;
		}
		else if(exp(-Delta/t)*RAND_MAX>rand())
				x=X,y=Y;
		t*=delta;
	}
}
void solve(){
	ansx=(db)sx/n,ansy=(db)sy/n;
	SA(),SA(),SA();
}
int main(){
	srand(2794735),srand(rand()),srand(rand());
	n=read();
	for(int i=1,x,y,w;i<=n;i++){
		x=read(),y=read(),w=read();
		a[i]=(node){x,y,w};
		sx+=x,sy+=y;
	}
	solve();
	printf("%.3lf %.3lf\n",ansx,ansy);
	 
	return 0;
}