模拟退火参数求调
查看原帖
模拟退火参数求调
759274
Stevehim楼主2023/7/19 17:54

rt

#include <bits/stdc++.h>
#define eps 1e-13
#define down 0.996 //一个下降常数
using namespace std;
const int N = 15,M = 2005;
double n,m,R,sumx,sumy,a[M],b[M],ans, ax,ay; //a,b表示x,y
struct node{
	double x,y,r; //题意
}s[N];
double dis(double x,double y,double xx,double yy){ //防止x1这样的已定义变量
	return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}
double query(double x,double y){
	double res = 0,d = R; //d是最大的爆炸半径,res是答案
	for(int i = 1; i <= n; i++){
		d = min(d,dis(x,y,s[i].x,s[i].y) - s[i].r); //枚举半径
	}
	for(int i= 1; i <= m; i++){
		if(dis(x,y,a[i],b[i]) <= d) res ++;
	}
	return res;
}
/*
  流程:
  设定初始温度、初始答案
  创建新解变量,随机赋值
  计算新解答案,与之前答案计算差值
  如果更优 -> 全盘接受
  如果差 -> 以一定概率接受
  每次步骤结束后进行降温
 */
void SA(){ //模拟退火
	double ansx = ax,ansy = ay;
	double tmp = 6500; //初始温度
	while(tmp > eps){
		//TODO
		double xx = ansx + ((rand() << 1) - RAND_MAX) * tmp;
		double yy = ansy + ((rand() << 1) - RAND_MAX) * tmp; //随机设定一组新的坐标
		double ans1 = query(xx,yy);
		double del = ans1 - ans;
		if(del > 0) {
			ax = xx,ay = yy;
			ansx = xx,ansy = yy;
			ans = ans1;
		}else{
			if(exp(- del / tmp) * RAND_MAX < rand()){
				ansx = xx;
				ansy = yy;
			}
		}
		tmp *= down; //降温
	}
}
void cz(){
	ax = sumx / m,ay = sumy / m; //与平衡点的那道题做法一样,最好是平均
	for(int i = 1; i <= 8; i++){
		SA();
	}
}

int main(){
	srand(3824224);
	cin >> n >> m >> R;
	for(int i = 1; i <= n; i++)
		cin >> s[i].x >> s[i].y >> s[i].r;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i];
		sumx += a[i],sumy += b[i]; //计算综合
	}
	cz();
	printf("%.0lf\n",ans);
	return 0;
}
2023/7/19 17:54
加载中...