模拟退火求调
查看原帖
模拟退火求调
593791
_Catluo_楼主2023/3/25 14:01

rt

#include<bits/stdc++.h>
using namespace std;
int n,m;
double nowx,nowy,now;
double ansx,ansy,ans=1e9;
struct node{
	double x,y,c;
}a[65];
double Rand(){return (double)rand()/RAND_MAX;}
double ls[66];
double w(double x,double y){
	for(int i=1;i<=n;i++){
		ls[i]=(double)a[i].c*sqrt((a[i].x-x)*(a[i].x-x)+(a[i].y-y)*(a[i].y-y));
	}
	sort(ls+1,ls+n+1);
	if(ls[m]<ans){
		ansx=x;
		ansy=y;
		ans=ls[m];
	}
	return ls[m];
}
void SA(){
	double T=100000;
	while(T>1e-4){
		double nxtx=nowx+(Rand()-0.5)*T;
		double nxty=nowy+(Rand()-0.5)*T;
		double nxt=w(nxtx,nxty);
		if(nxt<now){
			nowx=nxtx;
			nowy=nxty;
			now=nxt;
		}else if(exp((double)(now-nxt)/T)>Rand()){
			nowx=nxtx;
			nowy=nxty;
			now=nxt;
		}
		T*=0.98;
	}
	for(int i=1;i<=1000;i++){
		double nxtx=nowx+(Rand()-0.5)*T;
		double nxty=nowy+(Rand()-0.5)*T;
		double nxt=w(nxtx,nxty);
		if(nxt<now){
			nowx=nxtx;
			nowy=nxty;
			now=nxt;
		}else if(exp((double)(now-nxt)/T)>Rand()){
			nowx=nxtx;
			nowy=nxty;
			now=nxt;
		}
		T*=0.98;
	}
}
int main(){
	srand(19260817);
	cin>>n>>m;
	double z=19.920725;
	for(int i=1;i<=n;i++){
		double x,y;
		scanf("%lf %lf %lf",&x,&y,&a[i].c);
		a[i].x=cos(z)*x-sin(z)*y;
		a[i].y=sin(z)*x+cos(z)*y; 
	}
	now=w(nowx,nowy);
	while((double)clock()/CLOCKS_PER_SEC<1.92){SA();}
	printf("%.7lf",ans);
	return 0;
}
2023/3/25 14:01
加载中...