求助模拟退火,一直有一个点过不去
查看原帖
求助模拟退火,一直有一个点过不去
551375
junxis楼主2022/7/17 19:43

RT

#include<bits/stdc++.h>

using namespace std;

using db = double;

const int N = 2005, SIMULATE_TIMES=1;
const db START_T = 3000, DELTA_T = 0.997;

int n;
db x[N], y[N], w[N];
db ansx, ansy, answ;

db calc(db cx, db cy) {
	db res=0, dx, dy;
	for (int i=1; i<=n; i++) {
		dx = cx - x[i];
		dy = cy - y[i];
		res += sqrt(dx*dx + dy*dy) * w[i];
	}
	return res;
}

void augment() {
	db t = START_T;
	while (t > 1e-15) {
		db curx = ansx + (rand()*2 - RAND_MAX) * t;
		db cury = ansy + (rand()*2 - RAND_MAX) * t;
		db curw = calc(curx, cury);
		db dlt = curw - answ;
		if (dlt < 0) {
			ansx = curx;
			ansy = cury;
			answ = curw;
		} else if (exp(-dlt/t) * RAND_MAX > rand()) {
			ansx = curx;
			ansy = cury;
		}
		t *= DELTA_T;
	}
}

void simulute_anneal() {
	int tmp = SIMULATE_TIMES;
	while (tmp--) augment();
}

int main() {
	scanf("%d",&n);
	for (int i=1; i<=n; i++)
		scanf("%lf%lf%lf",x+i,y+i,w+i), ansx += x[i], ansy += y[i];
	ansx /= 1.*n;
	ansy /= 1.*n;
	answ = calc(ansx, ansy);
	simulute_anneal();
	printf("%.3lf %.3lf\n",ansx,ansy);
}
2022/7/17 19:43
加载中...