问一下为什么这样的模拟退火可以至少50分,至多100
查看原帖
问一下为什么这样的模拟退火可以至少50分,至多100
445896
I_m_FW楼主2022/2/6 11:10
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int dw=0.9985;
int n,m,a[N],rd=1;
double ans1,ans2;
double em(){
	double res=m;
	for(int i=2;i<=n;i++){
		if((double)a[i]*(i-1)+1e-15>=res){
			res=(double)(res+m);
		}
	}
	return (double)res/n;
}
void sa1(){
	double t=1000;
	while(t>1e-10){
		int crx=rand()%(n-1),cry=rand()%(n-1);
		while(crx==cry)cry=rand()%(n-1);
		swap(a[crx],a[cry]);
		double e=em(),dt=ans1-e;
		if(dt<0){
			ans1=e;
		}else if(exp((double)(-dt/t))*RAND_MAX>rand()){
			swap(a[crx],a[cry]);
		}
		t*=dw;
	}
}
void sa2(){
	double t=1000;
	while(t>1e-10){
		if((double)clock()/CLOCKS_PER_SEC>=0.400){
			printf("%.2lf %.2lf",ans1,ans2);exit(0);
		}
		int crx=rand()%(n-1),cry=rand()%(n-1);
		while(crx==cry)cry=rand()%(n-1);
		swap(a[crx],a[cry]);
		double e=em(),dt=ans2-e;
		if(dt>0){
			ans2=e;
		}else if(exp((double)(dt/t))*RAND_MAX>rand()){
			swap(a[crx],a[cry]);
		}
		t*=dw;
	}
}
int main(){
	srand((unsigned)time(0));
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	ans1=em();
	while((double)clock()/CLOCKS_PER_SEC<=0.480)sa1();
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	ans2=em();
	while(1)sa2();
}
2022/2/6 11:10
加载中...