【模拟退火】poj2420 A Star not a Tree?

题意：求平面上一个点，使其到给定的n个点的距离和最小，即费马点。

模拟退火的思想是随机移动，然后100%接受更优解，以一定概率接受更劣解。移动的过程中温度缓慢降低，接受更劣解的概率降低。

在网上看到的代码都不太靠谱，我这个代码的关键之处在于，每一次随机走点时，不是1次，而是在10次随机中取最优者作为当前这一步的随机结果，这样运行时非常优秀。

T降温时乘0.9/0.99这样的数都行，越接近1越准确，但速度越慢。

这份代码即使用0.9也可以ac。

#include<cstdio>

#include<cmath>

#include<cstdlib>

using namespace std;

const double EPS=0.00000001;

const double PI=acos(-1.0);

struct Point{

	double x,y;

	Point(const double &x,const double &y){

		this->x=x;

		this->y=y;

	}

	Point(){}

	void read(){

		scanf("%lf%lf",&x,&y);

	}

	double length(){

		return sqrt(x*x+y*y);

	}

}a[105],p;

double ans;

int n;

typedef Point Vector;

Vector operator - (const Point &a,const Point &b){

	return Vector(a.x-b.x,a.y-b.y);

}

Vector operator + (const Vector &a,const Vector &b){

	return Vector(a.x+b.x,a.y+b.y);

}

Vector operator * (const double &K,const Vector &v){

	return Vector(K*v.x,K*v.y);

}

double calc(Point p){

	double res=0.0;

	for(int i=1;i<=n;++i){

		res+=(a[i]-p).length();

	}

	return res;

}

int main(){

	srand(233);

//	freopen("poj2420.in","r",stdin);

//	freopen("poj2420.out","w",stdout);

	scanf("%d",&n);

	for(int i=1;i<=n;++i){

		a[i].read();

		p.x+=a[i].x;

		p.y+=a[i].y;

	}

	p.x/=(double)n;

	p.y/=(double)n;

	ans=calc(p);

	double T=100000.0;

	while(T>EPS){

		double bestnow=10000000.0;

		Point besttp;

		for(int i=1;i<=10;++i){

			double rad=(double)(rand()%10000+1)/10000.0*2.0*PI;

			Point tp=p+T*Point(cos(rad),sin(rad));

			double now=calc(tp);

			if(now<bestnow){

				bestnow=now;

				besttp=tp;

			}

		}

		if(bestnow<ans || exp((ans-bestnow)/T)*10000.0>(double)(rand()%10000)){

			ans=bestnow;

			p=besttp;

		}

		T*=0.99;

	}

	printf("%.0f\n",ans);

	return 0;

}

巴特西

【模拟退火】poj2420 A Star not a Tree?

最新文章

热门文章