模拟退火

具有某些优点的随机化算法，适用于最优解问题。

可以根据温度系数决定跳出当前最优解的概率，可以避免陷于局部最优解的情况。

定义最大温度，降温系数，最低温度，当前温度。当前温度初始化为最大温度，每次乘以降温系数，直到低于最低温度。

当前解更优时，更新最优解。

否则通过计算含温度的多项式概率，决定是否接受这个劣解。

if (exp((ans - eans) / t) * RAND_MAX < (double)rand()) // not acceptable

可以得出，温度越低，多项式概率越小，解的范围越稳定。

有几个技巧，可以提升欧率。

• 去厕所洗把脸

• 随机种子

srand(time(NULL));

• 卡时

while ((double)clock() / CLOCKS_REC_SEC < MAX_TIME) SA();

原因：既然题目给了足够的时限，那为什么不都用上呢。

\text{MAX\_TIME} 为自定义变量，个人喜欢设为 $0.8$。

• \text{random\_shuffle()}

求最优序列时，可以打乱一下原序列。用法类似 $\text{sort()}$。

一些感想：

当一个人下定决心学这个的时候，他多半是内心遭受了什么挫折，才来学这种奇奇怪怪的玩意儿。

当然如果你只是个想拓宽眼界的 dalao 那就当我放了个 p。

其实也没有很吃脸白了。

主要还是靠调参技巧。

当你学会了这个你会巴不得 $\text{NOIP}$ 年年 $4$ 道最优解问题。

例题

P1337

最裸的模板题了。

首先根据物理知识可以得知，当每个点的势能贡献矢量和为零时，达到平衡点。

所以对平衡点的坐标随机枚举，判断势能和是否比当前解更接近零，然后根据模拟退火的规则决定是否更新。

参数参考：$10000,0.997,1^{-13}$

#include <bits/stdc++.h>
#define rei register int
#define N 100010
using namespace std;
const double down = 0.997;
const double T0 = 10000;

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

struct node {int x, y, w;} a[N];
double ansx, ansy, answ;
int n;

inline double energy(double x, double y)
{
	double r = 0, delx, dely;
	for (rei i = 1; i <= n; i++)
	{
		delx = x - a[i].x; dely = y - a[i].y;
		r += sqrt(delx * delx + dely * dely) * a[i].w;
	}
	return r;
}

inline void SA()
{
	double t = T0;
	while (t > 1e-13)
	{
		double ex = ansx + (rand() * 2 - RAND_MAX) * t;
		double ey = ansy + (rand() * 2 - RAND_MAX) * t;
		double ew = energy(ex, ey);
		double dele = ew - answ;
		if (dele < 0) ansx = ex, ansy = ey, answ = ew;
		else if (exp(-dele / t) * RAND_MAX > rand()) ansx = ex, ansy = ey;
		t *= down;
	}
}

inline void solve() {SA(); SA(); SA();}

int main()
{
	srand(time(NULL));
	read(n);
	for (rei i = 1; i <= n; i++)
	{
		read(a[i].x); read(a[i].y); read(a[i].w);
		ansx += a[i].x; ansy += a[i].y;
	}
	ansx /= n; ansy /= n; answ = energy(ansx, ansy);
	solve();
	printf("%.3lf %.3lf", ansx, ansy);
	return 0;
}

P2210

求最优的序列顺序，常见的模拟退火板子。

思路是随机交换两个数，使序列发生变化。

代码中运用了卡时的技巧。

参数：$10000,0.999,1^{-12},0.9$

#include <bits/stdc++.h>
#define rei register int
#define N 25
using namespace std;
const int inf = 1e9;
const double MAX_TIME = 0.9;
const double T0 = 10000;
const double down = 0.999;

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

int a[N], n, m, g[N][5], pos[N], ans = inf;

inline int solve()
{
	int ret = 0;
	for (rei i = 1; i <= n; i++)
		for (rei j = 1; j <= 3; j++)
			ret += abs(pos[i] - pos[g[i][j]]);
	return ret;
}

inline void SA()
{
	double t = T0; int x, y, eans, delans;
	while (t > 1e-12)
	{
		do
		{
			x = rand() % n + 1;
			y = rand() % n + 1;
		} while (x == y);
		swap(pos[x], pos[y]);
		eans = solve();
		delans = eans - ans;
		if (delans < 0) ans = eans;
		else if (exp(-delans / t) * RAND_MAX > rand()) swap(pos[x], pos[y]);
		t *= down;
	}
}

int main()
{
	srand(time(NULL));
	read(n);
	for (rei i = 1; i <= n; i++)
		for (rei j = 1; j <= 3; j++)
			read(g[i][j]);
	for (rei i = 1; i <= n; i++) pos[i] = i;
	random_shuffle(pos + 1, pos + n + 1);
	ans = solve(); int sum = 0;
	while ((double)clock() / CLOCKS_PER_SEC < MAX_TIME) SA(), sum++;
	printf("%d", ans / 2);
	return 0;
}

P3878

一道可以大大提升退火人对自己运气自信的题。

因为数据实在是太 $**$ 水了。

就连笔者这种非酋都一遍过了

求最优序列，同样选择交换顺序。

参数：$10000,0.997,1^{-12}$

#include <bits/stdc++.h>
#define rei register int
#define N 35
using namespace std;
typedef long long ll;
const double MAX_TIME = 0.8;
const double T0 = 10000, down = 0.997, T1 = 1e-12;

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

ll n, T, a[N], suma, sumb, ans;

inline ll solve()
{
	ll suma = 0, sumb = 0;
	for (rei i = 1; i <= (n + 1) / 2; i++) suma += a[i];
	for (rei i = (n + 1) / 2 + 1; i <= n; i++) sumb += a[i];
	return abs(suma - sumb);
}

inline void SA()
{
	double t = 10000; ll x = 0, y = 0;
	while (t > 1e-15)
	{
		x = rand() % n + 1;
		y = rand() % n + 1;
		swap(a[x], a[y]);
		ll eans = solve();
		if (eans < ans) ans = eans;
		else if (exp((ans - eans) / t) * RAND_MAX < (double)rand()) swap(a[x], a[y]);
		t *= 0.997;
	}
}

inline void WORK()
{
	read(n); suma = sumb = ans = 0;
	for (rei i = 1; i <= n; i++) read(a[i]);
	random_shuffle(a + 1, a + 1 + n);
	ans = solve();
	for (rei i = 1; i <= 20; i++) SA();
	printf("%lld\n", ans);
}

int main()
{
	srand(time(NULL));
	read(T);
	while (T--) WORK();
	return 0;
}