Run Away
题目:http://poj.org/problem?id=1379
题意:平面上有一个矩形,在矩形内有一些陷阱。求得矩形内一个点,该点离与它最近的已知陷阱最远。
题解:我是用模拟退火解的,这题本身不难,但是可以从中大致了解模拟退火的基本的概念。
这个是别人写的模拟退火模型,挺准确的:
模拟退火算法的模型
①初始化:初始温度T(充分大),初始解状态S(算法迭代的起点),每次迭代次数L
②fork=1toL做③至⑥
③产生新解S’
④计算增量Δt′=C(S′)-C(S),其中C(S)为评价函数
⑤若Δt′<0则接受S’作为新的当前解,否则以概率e-Δt/k接受S’作为新的当前解
⑥如果满足终止条件则输出当前解作为最优解,结束程序
⑦T逐渐减少,然后转②
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> using namespace std; #define inf (1e20) #define eps (1e-3) #define pi (acos(-1.0)) double ansx[35],ansy[35],d[35],x[1005],y[1005]; double dist(double a,double b,double x,double y)//求两点距离 { return sqrt((a-x)*(a-x)+(b-y)*(b-y)); } int main() { int cas,n; double xi,yi,px,py,cnt,dx,dy,tx,ty,td; scanf("%d",&cas); srand((unsigned)time(NULL));//设置随机数种子 for(;cas--;) { scanf("%lf%lf%d",&xi,&yi,&n); for(int i=0;i<n;++i) scanf("%lf%lf",x+i,y+i); for(int i=0;i<35;++i)//初始解集 { ansx[i]=double(rand()%1000)/1000*xi; ansy[i]=double(rand()%1000)/1000*yi; d[i]=inf; for(int j=0;j<n;++j) d[i]=min(d[i],dist(ansx[i],ansy[i],x[j],y[j])); } double delta=double(max(xi,yi))/(sqrt(1.0*n));//初始温度 for(;delta>eps;) { for(int i=0;i<35;++i) { px=ansx[i]; py=ansy[i]; for(int j=0;j<35;++j) { cnt=double(rand()%1000)/1000*10*pi; dx=delta*cos(cnt); dy=delta*sin(cnt); tx=px+dx; ty=py+dy; if(tx<0||tx>xi||ty<0||ty>yi) continue; td=inf; for(int k=0;k<n;++k) td=min(td,dist(tx,x[k],y[k])); if(td>d[i])//更新更优解 { d[i]=td; ansx[i]=tx; ansy[i]=ty; } } } delta*=0.8;//减小温度 } double ans=0; int k; for(int i=0;i<35;++i)//找最优解 if(d[i]>ans) { k=i; ans=d[i]; } printf("The safest point is (%.1f,%.1f).\n",ansx[k],ansy[k]); } return 0; }来源: http://www.jb51.cc/article/p-hxzqsxku-zr.html