[HDU1109]Run Away(模拟退火,爬山算法)

发布于 2018-04-05  70 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU1109]Run Away(模拟退火,爬山算法)

Description

One of the traps we will encounter in the Pyramid is located in the Large Room. A lot of small holes are drilled into the floor. They look completely harmless at the first sight. But when activated, they start to throw out very hot java, uh ... pardon, lava. Unfortunately, all known paths to the Center Room (where the Sarcophagus is) contain a trigger that activates the trap. The ACM were not able to avoid that. But they have carefully monitored the positions of all the holes. So it is important to find the place in the Large Room that has the maximal distance from all the holes. This place is the safest in the entire room and the archaeologist has to hide there.

Tag

模拟退火,爬山算法

题目大意

给出矩形内若干个点,现在要求求出一个点,使得这个点到给出所有点中距离的最小值最大。

解决思路

在平面上随机一个/多个点,然后随机向四周走,看是否更优。若更优,则直接走,否则,退火算法是一定概率接受这个不优的解,而爬山是只接受更优的解。

代码

下面的代码使用爬山实现(其实似乎是爬山与退火的混合?)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define ld double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1010;
const int maxM=50;
const ld dt=0.75;
const ld eps=1e-5;
const ld Pi=acos(-1);
const ld INF=1e14;
const int inf=2147483647;

class Pos
{
public:
    ld x,y;
};

int X,Y,N;
Pos Hole[maxN],Ans[maxN];
ld Dis[maxN];

void SA();
ld Rand(ld l,ld r);
ld Dist(Pos A,Pos B);
ld Calc(Pos P);

int main()
{
    int T;scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&X,&Y,&N);
        for (int i=1;i<=N;i++) scanf("%lf%lf",&Hole[i].x,&Hole[i].y);
        SA();
    }
    return 0;
}

ld Rand(ld l,ld r)
{
    ld dou=(ld)rand()/(ld)RAND_MAX;
    return dou*(r-l+1)+l;
}

ld Dist(Pos A,Pos B){
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

ld Calc(Pos P)
{
    ld ret=INF;
    for (int i=1;i<=N;i++) ret=min(ret,Dist(P,Hole[i]));
    return ret;
}

void SA()
{
    ld T=max(X,Y);
    for (int i=1;i<=maxM;i++)//随机多个点,增大正确性
    {
        Ans[i].x=Rand(0.0,X*1.0);
        Ans[i].y=Rand(0.0,Y*1.0);
        Dis[i]=Calc(Ans[i]);
    }
    while (T>eps)
    {
        for (int i=1;i<=maxM;i++)
            for (int t=1;t<=50;t++)//多次行走
            {
                ld theta=Rand(0.0,Pi*2.0);//随机一个角度
                Pos now;
                now.x=Ans[i].x+cos(theta)*T;
                now.y=Ans[i].y+sin(theta)*T;
                //走,然后判断是否更优
                if ((now.x<0)||(now.y<0)||(now.x>X)||(now.y>Y)) continue;
                ld d=Calc(now);
                if (d>=Dis[i])
                {
                    Dis[i]=d;Ans[i]=now;
                }
            }
        T=T*dt;
    }
    int id=1;
    for (int i=2;i<=maxM;i++) if (Dis[i]>Dis[id]) id=i;
    printf("The safest point is (%.1lf, %.1lf).\n",Ans[id].x,Ans[id].y);
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU1109]Run Away(模拟退火,爬山算法)


HNCJ OIer