关于此题的模拟退火
查看原帖
关于此题的模拟退火
400072
sprads楼主2022/8/31 09:52

之前的帖子似乎提到过题解中大部分都是爬山。

正经写模拟退火可能连样例都过不了。

实践发现特判掉随机到的点能产生的答案为零的情况就可以了。(为零过于离谱,干脆不跳过去)

就像这样:

void SA(){
	db nx = sx,ny = sy;
	for(db T = st;T >= ed;T *= dt){
		db xx = nx + T * (2.0 * rand() - RAND_MAX);
		db yy = ny + T * (2.0 * rand() - RAND_MAX);
		int now = query(xx,yy),d = ans - now;
		if(!now)continue;//这一行
		if(d < 0)
			sx = nx = xx,sy = ny = yy,ans = now;
		else if(exp(-d / T) * RAND_MAX > rand())
			nx = xx,ny = yy;
	}
}
2022/8/31 09:52
加载中...