求助入门级模拟退火
  • 板块学术版
  • 楼主llzzxx712
  • 当前回复13
  • 已保存回复13
  • 发布时间2020/8/11 17:43
  • 上次更新2023/11/6 20:37:41
查看原帖
求助入门级模拟退火
235658
llzzxx712楼主2020/8/11 17:43

一道团队内的题

我将

i=1nxxi+yyidi\sum_{i=1}^{n}|x-x_i|+|y-y_i|-d_i

作为系统能量(x,yx,y)为当前点,但是最后一个数据点怎么调参都过不去。有没有大佬帮忙看一看。

有注释的代码:

#include <bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int read() { 
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
#define N 1010
struct node{
	int x,y,d;
}a[N];
int n,sx,sy,tot;

int ansx,ansy,anss; //全局最优解的坐标,anss记录解的数量 
double ans=1e18,t; //全局最优解、温度
const double delta=0.97; //降温系数

inline int calc(int x,int y) { //计算整个系统的能量
    int rt=0;
    for (re int i=1;i<=n;i++) {
        rt+=abs(abs(x-a[i].x)+abs(y-a[i].y)-a[i].d);
    }
    if(rt==0){
    	for(int i=1;i<=anss;i++){//看看这个解之前有没有 
    		if(x==ans1[i].x && y==ans1[i].y) return rt;
		}
		ans1[++anss].x=x;//没有的话添加这个解 
		ans1[anss].y=y;
	}
    return rt;
}
inline void simulate_anneal() { //SA主过程
    int x=ansx,y=ansy;
    t=1000; //初始温度
    while (t>1e-14) {
        int X=((ll)x+(ll)((((rand()<<1)-RAND_MAX)*t)))%4000007;
        int Y=((ll)y+(ll)(((rand()<<1)-RAND_MAX)*t))%4000007; //得出一个新的坐标
        int now=calc(X,Y);
        int Delta=now-ans;
        if (Delta<0) { //接受
            x=X,y=Y;
            ansx=x,ansy=y,ans=now;
        }
        else if (exp(-Delta/t)*RAND_MAX>rand()) x=X,y=Y; //以一个概率接受
        t*=delta;
    }
}
inline void Solve() { 
	while(!anss) simulate_anneal();
    simulate_anneal();
    simulate_anneal();
}
int main() {
    srand(time(0));
    n=read();
    for (re int i=1;i<=n;i++) {
        a[i].x=read(),a[i].y=read(),a[i].d=read();
    }
    Solve();
    if(anss==1) printf("%d %d\n",ansx,ansy);
    if(anss>1) printf("uncertain\n");
    if(!anss) printf("impossible");
    return 0;
}
2020/8/11 17:43
加载中...