模拟退火

好久没写博客了，写个模拟退火水一水

思想

模拟退火的思想是基于显示中的退火，当能量逐步减小时，最后的状态将趋于稳定态。

一般的模拟退火有$t$（温度参数），$delta$（降温系数），$beg$（起始温度）和$end$（终止温度）四个变量，其中降温系数对答案的影响比较显著。

下面是温度慢慢降低时的一幅比较直观的图

实现

每次随机变换状态，然后比当前答案优的直接接受这个状态，否则有一个极小的概率接受这个状态，这个小概率事件可以帮助我们跳出局部最优解。

这个小概率$f$为

$$f=\begin{cases}1,\text{比之前状态更优时} \\exp(\Delta ans/t),\text{状态不优时} \end{cases}$$

大概的代码实现可以看下面的例题.

例题

[SCOI2008]城堡

题目背景

2008NOI四川省选

题目描述

在一个国家里，有 $n$ 个城市（编号为 $0$ 到 $n-1$）。这些城市之间有 $n$ 条双向道路相连（编号为 $0$ 到 $n-1$），其中编号为 $i$ 的道路连接了城市 $i$ 和城市 $r_i$（一条道路可以连接一个城市和它自身），长度为 $d_i$。$n$ 个城市中有 $m$ 个拥有自己城堡，可以抵御敌人侵略。如果没有城堡的城市遭受攻击，则离它最近的城堡将派兵前往救援。

你的任务是在不超过 $k$ 个没有城堡的城市中建立城堡，使得所有城市中“离最近城堡的距离”的最大值尽量小。换句话说，若令 $dist(c)$ 表示城市 $c$ 的最近城堡离它的距离，则你的任务是让 $\max\{dist(c)\}$ 尽量小。

输入数据保证存在方案使得对于每个城市，至少有一个城堡能够到达。

输入格式

输入第一行为三个正整数 $n, m, k$。第二行包含 $n$ 个整数 $r_0,r_1,\ldots,r_{n-1}$。第三行包含 $n$ 个整数 $d_0,d_1,\ldots,d_{n-1}$。第四行包含 $m$ 个各不相同的 $0$ 到 $n-1$ 之间的整数，分别为 $m$ 个城堡所在的城市编号。

输出格式

输出仅一行，包含一个整数，即 $\max\{dist(c)\}$ 的最小值。

样例

样例输入

5 0 1
1 2 3 4 0
1 1 1 1 1

样例输出

2

提示

$100\%$ 的数据满足: $2\leq n\leq 50$，$1\leq d_i\leq 10^6$，$0\leq m\leq n-k$。

题解

考虑模拟退火，随机一个序列，然后取前k个序列中的地块建城堡，然后计算答案，模拟退火即可。

代码实现

#include<iostream>
#include<array>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
using gg=long long;
array<gg,110> nxt,to,val;
array<gg,51> r,d,dep,head;
bitset<51> alr;
vector<gg> cb,cs;
queue<gg> list;
gg n,m,k,cnt=0,ans;
void add(const gg &fr,const gg &t,const gg &v){
	cnt++;
	nxt[cnt]=head[fr];
	head[fr]=cnt;
	to[cnt]=t;
	val[cnt]=v;
	return;
}
gg check(){
	gg tmp=0;
	for(gg i=0;i<n;i++) dep[i]=1145141919810;
	alr=0;
	for(gg i=0;i<cb.size();i++){
		dep[cb[i]]=0;
		list.push(cb[i]);
		alr[cb[i]]=1;
	}
	for(gg i=0;i<k;i++){
		dep[cs[i]]=0;
		list.push(cs[i]);
		alr[cs[i]]=1;
	}
	while(list.size()){
		gg p=list.front();
		list.pop();
		alr[p]=0;
		for(gg i=head[p];i;i=nxt[i]){
			if(dep[to[i]]>dep[p]+val[i]){
				dep[to[i]]=dep[p]+val[i];
				if(!alr[to[i]]){
					list.push(to[i]);
					alr[to[i]]=1;
				}
			}
		}
	}
	for(gg i=k;i<cs.size();i++) tmp=max(tmp,dep[cs[i]]);
	return tmp;
}
void sa(){
	for(double t=2000;t>=0.001;t*=0.998){
		gg x=rand()%k,y=rand()%(n-m);
		swap(cs[x],cs[y]);
		gg tmp=check(),del=ans-tmp;
		if(del>0) ans=tmp;
		else if(exp(del/t)*RAND_MAX<=rand()) swap(cs[x],cs[y]);
	}
	return;
}
int main(){
	gg in;
	cin>>n>>m>>k;
	for(gg i=0;i<n;i++){
		cin>>r[i];
	}
	for(gg i=0;i<n;i++){
		cin>>d[i];
	}
	for(gg i=0;i<m;i++){
		cin>>in;
		alr[in]=1;
	}
	for(gg i=0;i<n;i++){
		if(alr[i]) cb.push_back(i);
		else cs.push_back(i);
		add(i,r[i],d[i]);
		add(r[i],i,d[i]);
	}
	ans=check();
	for(gg i=1;i<=100;i++) sa();
	cout<<ans<<'\n';
	return 0;
}

其它例题

外太空旅行

【JSOI2016】炸弹攻击

【JSOI2004】 平衡点 / 吊打XXX