求助模拟退火
查看原帖
求助模拟退火
194093
天梦楼主2021/6/20 16:43

发现一个很神奇的事情。

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 50010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;
const dd delta=0.996;
const dd t0=3000;
const dd eps=1e-15;

template<typename T>  inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

struct point{
    dd x,y;
    point(){}
    point(dd x,dd y) : x(x),y(y) {}
};
point p[N];

int T,n;
dd sumx,sumy,ans,ansx,ansy;

inline dd dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

inline dd all_dis(dd x,dd y){
    dd res=0;
    for(int i=1;i<=n;i++) res+=dis(point(x,y),p[i]);
    return res;
}

inline void simulate(){
    dd x=ansx,y=ansy;
    dd t=t0;
    while(t>eps){
        dd dx=x+((rand()<<1)-RAND_MAX)*t;
        dd dy=y+((rand()<<1)-RAND_MAX)*t;
        dd now=all_dis(dx,dy);dd del=now-ans;
        if(del<0){
            x=dx;y=dy;ans=now;ansx=dx;ansy=dy;
        }
        else if(exp(-del/t)*RAND_MAX>rand()) x=dx,y=dy;
        t*=delta;
    }
}

inline void work(){
    ansx=sumx/n;ansy=sumy/n;
    for(int i=1;i<=5;i++) simulate();
}

int main(){
    srand(time(0));
    read(T);
    while(T--){
        ans=INF;sumx=0;sumy=0;
        read(n);
        for(int i=1;i<=n;i++){
            read(p[i].x);read(p[i].y);
            sumx+=p[i].x;sumy+=p[i].y;
        }
        work();
//        printf("%lf\n",ans);
        printf("%.0lf\n",round(ans));
        if(T) printf("\n");
    }
    return 0;
}

在那个结构体里,如果把所有的 dd 改成 int 那么每一次模拟退火的答案都不一样,请问有这么大偏差的原因是什么?

2021/6/20 16:43
加载中...