模拟退火为什么一直 WA,系数有什么问题吗
查看原帖
模拟退火为什么一直 WA,系数有什么问题吗
482610
Mortidesperatslav楼主2024/5/18 15:07
#include<bits/stdc++.h>
using namespace std;
double T0 = 1e6, d = 1-1e-5, Tk = 1e-4;//模拟退火的三个系数 
double Exp(double x){//接受新解的概率 
	return pow(2.718281828, x);
}
double x[20], y[20];
int ans[20], nans[20];
int n;
double dis(double x, double y, double xx, double yy){
	return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}
double calc(){//计算当前解 
	double ans = 0;
	for (int i = 1; i <= n; i++)
		ans += dis(x[nans[i - 1]], y[nans[i - 1]], x[nans[i]], y[nans[i]]);
	return ans;
}
void th(){//模拟退火 
	double T = T0;
	while (T > Tk){
		for (int i = 1; i <= n; i++)
			nans[i] = ans[i];
		double lans = calc();
		int sx = rand() % n + 1, sy = rand() % n + 1;
		swap(nans[sx], nans[sy]);
		double Nans = calc();
		if (Nans < lans)
			swap(ans[sx], ans[sy]);
		else{
			double gl = Exp(-(Nans - lans) / T);
			if ((double)rand() / (double)RAND_MAX < gl)
				swap(ans[sx], ans[sy]);
		}
		T *= d;
	}
}
int main(){
    int st = clock();
	srand(time(0));
	srand(rand());
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> x[i] >> y[i];
	for (int i = 1; i <= n; i++)
		ans[i] = i;
	while (clock() - st < 0.78 * CLOCKS_PER_SEC)
		th();
	for (int i = 1; i <= n; i++)
		nans[i] = ans[i];
	printf("%.2lf", calc());
}
2024/5/18 15:07
加载中...