模拟退火算法如何提高取得正确答案的概率
查看原帖
模拟退火算法如何提高取得正确答案的概率
1017629
ZSB00000楼主2024/9/16 21:48
#include<bits/stdc++.h>
using namespace std;
struct point
{
    int x,y;
    int weight;
}a[(int)1e5+5];
double answ;
int n;
double ansx=0.0,ansy=0.0;
double get_ep(double x,double y)
{
    double r=0;
    for(int i=1;i<=n;i++)
    {
        double dx=x-a[i].x;
        double dy=y-a[i].y;
        r+=sqrt(dx*dx+dy*dy)*a[i].weight;
    }
    return r;
}
double x,y;
void solve()
{
	srand(20100121);
    double t=1000,down=0.993;
    while(t>1e-14)
    {
        double nextx=x+(rand()*2-RAND_MAX)*t;
        double nexty=y+(rand()*2-RAND_MAX)*t;
        double nexte=get_ep(nextx,nexty);
        if(nexte<answ)
        {
            x=nextx;
            y=nexty;
            answ=nexte;
        }
        else if(exp(-(nexte-answ)/t)*RAND_MAX>rand())
        {
            x=nextx;
            y=nexty;
        }
        t*=down;
    }
}
void sa()
{
   solve();
   solve();
   solve();
   solve();
   solve();
   cout<<fixed<<setprecision(3)<<x<<" "<<y<<endl;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].weight;
        ansx+=a[i].x;
        ansy+=a[i].y;
    }
    ansx/=n;
    ansy/=n;
    answ=get_ep(ansx,ansy);
    x=ansx,y=ansy;
    sa();
}

RT,此代码仅可获得89pts,修改初始温度和降温系数总会多WA几个点

2024/9/16 21:48
加载中...