模拟退火学习笔记

模拟退火

模拟退火能解决三分这类的问题，当然能解决三分不能的（暂时还不太会）

它能求出单峰函数的极值。

具体实现：

时间t初值为区间大小，每次乘上delta，delta一般设为0.992333

每次改变位置（先大范围跳，在小范围跳），计算答案，如果更优就更新，不优就用一个概率去选择更新

void tui()
{
    t=1000;//温度初值
    while(t>1e-12)
    {
        X=x+(rand()*2-RAND_MAX)*t*0.0001;//改变位置
        if(X1000)X=1000;//判断边界
        now=suan(X);//计算答案
        double anss=now-ans2;
        if(anss<0.0){ans1=X;ans2=now;x=X;}//如果更优就更新
        else if(exp(-anss/t)*RAND_MAX>rand())x=X;//用一个概率去选择更新
        t=t*delta;//温度下降
    }
}

重要：

然后，我们发现精度不够啊，没三分准，怎么办？

我们再枚举1000（.......）次的0.001（保留几位小数）

    double xu=ans1;
    double xjh=xu;
    double XJH=0.0;
    for(int i=1;i<=1000;i++)
    {    
        xjh+=0.0001;
        if(xjh>1000.0)break;
        XJH=suan(xjh);
        if(XJH<ans2)
        {
            ans1=xjh;
            ans2=XJH;
        }
    }
    xjh=xu;
    XJH=0.0;
    for(int i=1;i<=1000;i++)
    {    
        xjh-=0.0001;
        if(xjh<0.0)break;
        XJH=suan(xjh);
        if(XJH<ans2)
        {
            ans1=xjh;
            ans2=XJH;
        }
    }

这样就能保证精度了，根据时间在多做几次退火即可。

为了使答案更加准确，我们可以先随机若干次，这样的话跳动会更加优秀。

    for(int i=1;i<=3000;i++)
    {
        int X=rand()%n+1,Y=rand()%n+1;
        int ret=calc(X,Y);
        if(ret>ans)ans=ret,x=X,y=Y;
    }

例题1：#10013. 「一本通 1.2 例 3」曲线

明明做作业的时候遇到了个二次函数,,他突发奇想设计了一个新的函数 ,

明明现在想求这个函数在 的最小值，要求精确到小数点后四位，四舍五入。

题解：

这就是三分题，精度要求很高。

我们就用上面的方法，先退火，在暴力枚举确定答案。

代码：

#include
using namespace std;
//#define double long double
const int N=10005;
const double delta=0.9929;
int T,n;
double t,x,ans1,ans2,X,now,anss,k,kk,a[N],b[N],c[N];
double suan(double x)
{
    k=a[1]*x*x+b[1]*x+c[1];
    for(int i=2;i<=n;i++)
    {
        kk=a[i]*x*x+b[i]*x+c[i];
        if(kk>k)k=kk;
    }
    return k;
}
void tui()
{
    t=1000;
    while(t>1e-12)
    {
        X=x+(rand()*2-RAND_MAX)*t*0.0001;
        if(X1000)X=1000;
        now=suan(X);
        double anss=now-ans2;
        if(anss<0.0){ans1=X;ans2=now;x=X;}
        else if(exp(-anss/t)*RAND_MAX>rand())x=X;
        t=t*delta;
    }
}
void solve()
{
    ans1=0.0;ans2=suan(x);
    tui();
    double xu=ans1;
    double xjh=xu;
    double XJH=0.0;
    for(int i=1;i<=1000;i++)
    {    
        xjh+=0.0001;
        if(xjh>1000.0)break;
        XJH=suan(xjh);
        if(XJH<ans2)
        {
            ans1=xjh;
            ans2=XJH;
        }
    }
    xjh=xu;
    XJH=0.0;
    for(int i=1;i<=1000;i++)
    {    
        xjh-=0.0001;
        if(xjh<0.0)break;
        XJH=suan(xjh);
        if(XJH<ans2)
        {
            ans1=xjh;
            ans2=XJH;
        }
    }
}
int main()
{
    srand(19491001);srand(rand());srand(rand());
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
        solve();
        printf("%.4lf\n",ans2);
    }
}