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

· · 题解

前面的几篇题解似乎都没有重点说模拟退火的算法。

一、模拟退火步骤

选定一个初始状态（比如选定所有点坐标的平均数），选定一个初始温度T。

当温度大于一个边界值时：

{
　　随机变化坐标，变化幅度为 T 。

　　计算新解与当前解的差 DE。

　　如果新解比当前解优(DE > 0)，就用新解替换当前解。

　　否则以 exp(DE / T) 的概率用新解替换当前解。

　　温度乘上一个小于1的系数，即降温。
}

这样，随着温度不断降低，变化幅度也越来越小，接受一个更劣的解的概率也越来越小。

二、模拟退火注意事项

  1. 温度T的初始值设置问题。 初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。

  2. 退火速度问题。 模拟退火算法的全局搜索性能也与退火速度密切相关。同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。

  3. 温度管理问题 降温系数应为正的略小于1.00的常数。

关于这道题，一切自然变化进行的方向都是使能量降低，因为能量较低的状态比较稳定。

因为物重一定，绳子越短，重物越低，势能越小，势能又与物重成正比，所以，只要使得\sum_{i=1}^ndist[i]*weight[i]也就是总的重力势能最小，就可以使系统平衡

#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstdlib>

int Read()
{
    int x=0,y=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
        {
            y=-1;
        }
        c=getchar();
    }
    while(isdigit(c))
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*y;
}

struct Node
{
    int x,y,weight;
}node[10005];
int n;

double potential_energy(double nowx,double nowy)
{
    double sum=0;
    for(int i=1;i<=n;i++)
    {
        double delx=nowx-node[i].x;
        double dely=nowy-node[i].y;
        sum+=(sqrt(delx*delx+dely*dely))*node[i].weight;
        //物重一定，绳子越短，重物越低，势能越小 
        //势能又与物重成正比 
    }
    return sum;//在(nowx,nowy)处的总势能 
}

double xans,yans;//最终答案 
double ans=1e18+7,t;//势能与温度
const double delta=0.993;//降温系数

void simulate_anneal()
{
    double xx=xans;//钦定一个初始位置
    double yy=yans;
    t=1926;//t是温度
    while(t>1e-14)
    {
        double xtemp=xans+(rand()*2-RAND_MAX)*t;
        double ytemp=yans+(rand()*2-RAND_MAX)*t;
        //随机一个新的坐标，变化幅度为t
        //这里要注意rand()和rand()*2-RAND_MAX的区别
        //rand()的范围是0~RAND_MAX-1
        //rand()*2-RAND_MAX的范围是-RAND_MAX到RAND_MAX-1 

        double new_ans=potential_energy(xtemp,ytemp);//计算当前解的势能 
        double DE=new_ans-ans;
        if(DE<0)//如果是一个更优解
        {
            xx=xtemp;
            yy=ytemp;//就接受
            xans=xx;
            yans=yy;
            ans=new_ans;
        }
        else if(exp(-DE/t)*RAND_MAX>rand())//能否接受这个差 
        {
            //更新坐标
            xx=xtemp;
            yy=ytemp;
        }
        t*=delta;//降温 
    }
}

void SA()//洗把脸就AC了 
{
    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
}

int main()
{
    n=Read();
    for(int i=1;i<=n;i++)
    {
        node[i].x=Read();
        node[i].y=Read();
        node[i].weight=Read();
    }
    SA();
    printf("%.3lf %.3lf",xans,yans);
    return 0;
}