mo拟退火恒WA#2,#3,#8,#9?
查看原帖
mo拟退火恒WA#2,#3,#8,#9?
160150
WxjzKK楼主2023/9/14 20:25

如上,我也不知道为什么模拟退火会恒WA几个点,求调

//【模板】模拟退火 
#include<bits/stdc++.h>
#define MAXN 15
using namespace std;
inline void read(int &n){
	int s=0,t=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') t=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);c=getchar();
	}
	n=s*t;
}
inline void put(int n){
	if(n<0){
		putchar('-');n=-n;
	}
	if(n<10){
		putchar(n+48);return;
	}
	put(n/10);
	putchar(n%10+48);
}
int n;
double answ,pos[MAXN][MAXN],ans[MAXN],dans[MAXN],dis[MAXN];
inline double calc(double a[]){
	double res=0,sum=0;
	for(register int i=0;i<=n;++i){
		dis[i]=0;
		for(register int j=1;j<=n;++j){
			double dpos=pos[i][j]-a[j];
			dis[i]+=dpos*dpos;
		}
		//dis[i]=sqrt(dis[i]);
     //这里也是不知道为什么,本来求距离要开平方,但是开平方后会跳到一个绝对值极其巨大且复杂的数上,有没有奆佬能解释一下
		sum+=dis[i];
	}
	sum/=(n+1);
	for(register int i=0;i<=n;++i){
		double dpos=(sum-dis[i]);
		res+=dpos*dpos;
	}
	res/=(n+1);res=sqrt(res);
	return res;
}
inline void SA(){
	for(register double t=3000;t>1e-15;t*=0.995){
		for(register int i=1;i<=n;++i) dans[i]=ans[i]+(rand()*2-RAND_MAX)*t;
		double dw=calc(dans),d=dw-answ;
		if(d<0){
			for(register int i=1;i<=n;++i) ans[i]=dans[i];
			answ=dw;
		}
		else if(exp(-d/t)*RAND_MAX>rand()){
			for(register int i=1;i<=n;++i) ans[i]=dans[i];
			answ=dw;
		}
	}
}
int main(){
	srand(time(NULL));
	read(n);
	for(register int i=0;i<=n;++i)
		for(register int j=1;j<=n;++j){
			scanf("%lf",&pos[i][j]);ans[j]+=pos[i][j];
		}
	for(register int i=1;i<=n;++i) ans[i]/=(n+1);
	answ=calc(ans);
	SA();SA();SA();SA();
	for(register int i=1;i<=n;++i) printf("%.3lf ",ans[i]);
	putchar('\n');
	return 0;
}
2023/9/14 20:25
加载中...