首页 > 代码库 > POJ 2420

POJ 2420

2024-07-17 02:18:48   212人阅读

模拟退火算法。昨天看了PPT，原来模拟退火算法涉及到马尔什么链，开始理解，它其实就是一个关于抽样的问题。随机抽样，选取足够多的样本，然后逐步逼近。而在平面上，由于T的下降，使得逐渐缩小至一点。然后，就可以了。

算法：

在平面上随机选取一些点，当然这些点应当有一点相关的性吧。我猜的。

然后在这些点随机移动，若移动后更优，则移动，否则，留待下一次循环。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <time.h>using namespace std;const int MAXN=110;const int MAX=50;struct point {	double x,y;};point p[MAXN]; int n; point s,tt; double ans_dis,tmp_dis;point tar[MAX];double getdouble(){	double ret=(rand()*rand()%10000)*1.0/1e5;	if(rand()&1) ret*=-1;	return ret;}double dist(point &u,point &v){	return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));}double work(point &s){	double ret=0;	for(int i=0;i<n;i++){		ret+=dist(p[i],s);	}	return ret;}int main(){	srand(time(0));	while(scanf("%d",&n)!=EOF){		s.x=s.y=0; ans_dis=tmp_dis=0;		for(int i=0;i<n;i++){			scanf("%lf%lf",&p[i].x,&p[i].y);			s.x+=p[i].x; s.y+=p[i].y;		}		s.x/=n; s.y/=n;		for(int i=0;i<MAX;i++){			tar[i].x=s.x+getdouble()*100;			tar[i].y=s.y+getdouble()*100;		}		double T=100;		double ans_dis=work(s);		for(double t=T; t>1e-8;t*=0.8){			for(int i=0;i<MAX;i++){				double tmp_dis=work(tar[i]);				for(int j=0;j<10;j++){					tt.x=tar[i].x+getdouble()*t;					tt.y=tar[i].y+getdouble()*t;					double f=work(tt);					if(f<tmp_dis) tar[i]=tt;				}			}		}		for(int i=0;i<MAX;i++){			double mm=work(tar[i]);			ans_dis=min(ans_dis,mm);		}		printf("%.0lf\n",ans_dis);	}	return 0;}

　　


联系
我们