【复建笔记】模拟退火

简述一下我的理解：

为什么要有那一行一定概率下接受答案？

因为如果没有就会在当前峰下爬山，有的话才能跳到别的峰上，这一行与温度有关，当温度越低，跳的概率越低。

退火随机一个二维点：

nowx = limx + ((rand() << 1) - RAND_MAX) * T;
nowy = limy + ((rand() << 1) - RAND_MAX) * T;

退火接受概率的公式：

\(e^{\frac{-del}{T}}?\frac{rand()}{RAND_{MAX}}\)

得看是最大还是最小值了。

退火的模板：

const double lim = ... // 温度最小值，通常为 1e-10 左右
const double d = ... // 变化系数，通常为 0.996 左右
void SA() {
    double T = ... // 初始温度，通常为 2021 左右
    while(T > lim) {
        ... // 获取一个随机的位置
        now = calc(); // 计算当前位置的答案 
        del = now - ans; // 计算 变化量
        if(del < 0) { // 以最小值为例
            ans = now; // 更新答案
            ...  // 更新答案和中间量的状态
        } else if(exp(-del/T) > (double)rand()/RAND_MAX) {
            ...  // 一定概率选择当前当前状态
        } 
        T *= d; // 降温
    }
}

复建例题：

P2210

很简单，直接一遍秒了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

namespace IO {
	#define pb push_back
	#define lson rt << 1
	#define rson rt << 1 | 1
	const int N = 1e3 + 10;
	const int Maxn = 2e5 + 10;
	int read() {
		int res = 0, f = 0; char ch = getchar();
		for(; !isdigit(ch); ch = getchar()) f |= (ch == '-');
		for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch - '0');
		return f ? -res : res;
	}
}

using namespace IO;

int n, a[20][5], rk[20];
const double Lim = 1e-10;
const double down = 0.996;
 
int calc() {
	int res = 0;
	bool vis[20][20];
	for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) vis[i][j] = vis[j][i] = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= 2; j++) {
			if(vis[i][a[i][j]] || vis[a[i][j]][i]) continue;
			int x = rk[i], y = rk[a[i][j]];
			if(x > y) swap(x, y);
			res += y - x, vis[i][a[i][j]] = 1, vis[a[i][j]][i] = 1;
		}
	}
	return res;
}

int ans = INT_MAX;

void SA() {
	double T = 2023;
	while(T > Lim) {
		int nowx = rand() % n + 1, nowy = rand() % n + 1;
		swap(rk[nowx], rk[nowy]);
		int nowans = calc();
		int del = nowans - ans;
		if(del < 0) {
			ans = nowans;
		}
		else if(exp(-del/T) > rand() / RAND_MAX) {
			
		}
		else {
			swap(rk[nowx], rk[nowy]);
		}
		T *= down;
	}	
}

signed main() {
	srand(2006);
	n = read();
	for(int i = 1; i <= n; i++) a[i][0] = read(), a[i][1] = read(), a[i][2] = read();
	for(int i = 1; i <= n; i++) rk[i] = i;
 	while((double)clock()/CLOCKS_PER_SEC<=0.8) SA();
 	cout<<ans;
 	return 0;
}