程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1379 模擬退火算法

POJ 1379 模擬退火算法

編輯：C++入門知識

POJ 1379 模擬退火算法

求規定平面上一點到已知點的最小距離最大的點。

模擬退火的流程是，隨機構造幾組解作為初始解空間，每次對當前解空間進行隨機擴展，若發現更優解則替換。

進行的次數由參數人為控制，而隨機擴展的幅度也是隨著次數逐漸減小的。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define eps 1e-2
double pi=acos(-1.0);
double x[10004],y[10004];
double qx[10004],qy[10004];
double X,Y;
int n;
const int num=15;   //初始解空間大小
const int numf=30;  //擴展解空間大小
double dist(double x,double y,double xx,double yy)
{
    return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
double get(double xx,double yy)
{
    double mins=1111111111;
    for(int i=1;i<=n;i++)
        mins=min(mins,dist(xx,yy,x[i],y[i]));
    return mins;
}
double getr()   //返回[0,1]的浮點數
{
    return (rand()%10000+1.0)/10000.0;
}
int main()
{
    srand(time(NULL));  //多次提交= =防RP差
    int ca;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%lf%lf%d",&X,&Y,&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&x[i],&y[i]);
        }
        for(int i=1;i<=num;i++) //構造初始解空間
        {
            qx[i]=X*getr();
            qy[i]=Y*getr();
        }
        double dd=max(Y,X);     //最大溫度
        while(dd>eps)
        {
            for(int i=1;i<=num;i++)
            {
                double now=get(qx[i],qy[i]),t;
                for(int j=1;j<=numf;j++)
                {
                    double dt=getr()*2*pi;      //隨機角度
                    double tmpx=qx[i]+dd*cos(dt);
                    double tmpy=qy[i]+dd*sin(dt);
                    if(tmpx<0||tmpx>X||tmpy<0||tmpy>Y) continue;
                    if((t=get(tmpx,tmpy))>now) //擴展新解
                    {
                        qx[i]=tmpx;
                        qy[i]=tmpy;
                        now=t;
                    }
                }
            }
            dd*=0.9;            //冷卻速度
        }
        double mins=0;
        int k;
        for(int i=1;i<=num;i++)
        {
            double tmp=get(qx[i],qy[i]);
            if(tmp>mins) {mins=tmp;k=i;}
        }
        printf("The safest point is (%.1lf, %.1lf).\n",qx[k],qy[k]);
    }
    return 0;
}
/*
3
1000 50 1
10 10
100 100 4
10 10
10 90
90 10
90 90
3000 3000 4
1200 85
63 2500
2700 2650
2990 100
*/