题解 P1337 【[JSOI2004]平衡点 / 吊打XXX】

这道题调了好久，果然非洲人是得不到眷顾的吗。。。

本题采用模拟退火解决。

模拟退火是一种简洁明了而又高效的近似算法，基本上可以套到任何求最优解的题目上去。

它的原理是模拟物理中金属退火的现象，凭借选手逆天的RP跳出局部最优解，来到全局最优解。

比较常用的近似算法还有爬山和遗传，但是我个人觉得没太大必要掌握（像我这种脸黑的选手有一次遗传算法WA52。。）。

模拟退火总体就是一个持续降温的流程。

在降温的过程中，坐标随机跳动的范围会越变越小。

当然，为了防止搞错，我们每一次都会以一定概率接受一个比较奇怪的解，这一点有些类似遗传算法中的突变。

inline void simulateAnneal(){

	double x=ansx,y=ansy;t=5000;

	while(t>1e-14){

		double X=x+((rand()<<1)-RAND_MAX)*t,Y=y+((rand()<<1)-RAND_MAX)*t;

		double now=calcEnergy(X,Y),dist=now-ans;

		if(dist<0){

				ansx=x=X,ansy=y=Y,ans=now;

		}else if(exp(-dist/t)*RAND_MAX>rand())x=X,y=Y;

		t*=delta;

	}

}

这里t代表温度，它会一直递减。

然后每一次我们会根据t的值（控制范围）随机跳一个新的解。

求一下它的值，看一下值能不能接受。

假如这个值不能接受，那就以一定概率接受一个奇奇怪怪的解，选择解的方法遵循Metropolis准则（我也不知道这是什么玩意别问我）。

求值的流程因题而异，总之就是一个衡量解的标准。

template<typename T>inline T calcEnergy(T x,T y){

	T tmp=0;

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

		T disx=x-a[i].x,disy=y-a[i].y;

		tmp+=sqrt(disx*disx+disy*disy)*a[i].val;

	}

	return tmp;

}

主要的部分大概就这么多了，其他要注意的无非就是常数什么的了。

M_sea大佬用的常数是

delta=0.993

t=2000

loop=5

（loop指的是运行次数）

然而这个常数对于脸黑的我来说比较窒息，所以做了一点小调整，最后是

delta=0.9932

t=5000

loop=5

最后，AC代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstdlib>

using namespace std;

namespace StandardIO{

	template<typename T>inline void read(T &x){

		x=0;T f=1;char c=getchar();

		for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

		for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';

		x*=f;

	}

	template<typename T>inline void write(T x){

		if(x<0)putchar('-'),x*=-1;

		if(x>=10)write(x/10);

		putchar(x%10+'0');

	}

}

using namespace StandardIO;

namespace Solve{

	const int N=1010;

	const double delta=0.9932;

	struct SA{

		private:

			int n,sumx,sumy;

			double ans=1e18,t;

			struct node{

				int x,y,val;

			}a[N];

			template<typename T>inline T calcEnergy(T x,T y){

				T tmp=0;

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

					T disx=x-a[i].x,disy=y-a[i].y;

					tmp+=sqrt(disx*disx+disy*disy)*a[i].val;

				}

				return tmp;

			}

			inline void simulateAnneal(){

				double x=ansx,y=ansy;t=5000;

				while(t>1e-14){

					double X=x+((rand()<<1)-RAND_MAX)*t,Y=y+((rand()<<1)-RAND_MAX)*t;

					double now=calcEnergy(X,Y),dist=now-ans;

					if(dist<0){

						ansx=x=X,ansy=y=Y,ans=now;

					}else if(exp(-dist/t)*RAND_MAX>rand())x=X,y=Y;

					t*=delta;

				}

			}

		public:

			SA(){}

			~SA(){}

			double ansx,ansy;

			inline void init(){

				srand(19260817),srand(rand()),srand(rand());

				read(n);

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

					read(a[i].x),read(a[i].y),read(a[i].val);

					sumx+=a[i].x,sumy+=a[i].y;

				}

			}

			template<typename T>inline void SimulateAnneal(T times){

				ansx=(double)sumx/n,ansy=(double)sumy/n;

				for(register int i=1;i<=times;++i)simulateAnneal();

			}

	}ljz;

	inline void solve(){

		ljz.init();

		ljz.SimulateAnneal(5);

		printf("%.3lf %.3lf",ljz.ansx,ljz.ansy);

	}

}

using namespace Solve;

int main(){

	solve();

}

巴特西

题解 P1337 【[JSOI2004]平衡点 / 吊打XXX】

最新文章

热门文章