模拟退火 学习笔记

## 模拟退火用来干什么 ~~用来骗分~~ 用来求解一个 **方案数量极大** 且 **可能不是单峰函数** 的问题。 ## 模拟退火的主过程 顾名思义，就是模拟金属的**退火** 定义：初始温度 $T_0$，当前温度 $T$，降温系数 $\Delta$，终止温度 $T_k$。 1. 赋初值 $T=T_0$（一个较大的数），$\Delta <1$，$T_k>0$。 2. 执行如下过程：（求最小值） > $\mathrm{ans\gets \infty}$ > $\mathrm{While\ T>T_k:}$ >> $\mathrm{now\gets Make\ a\ new\ solution}$ >> $\mathrm{calc\ val=W(now)}$ >> $\mathrm{If\ }val<ans:$ >>> $\mathrm{ans\gets val}$ >> $\mathrm{Else\ If\ }e^{\frac{ans-now}{T}}<rand():$ >>> $\mathrm{Restores\ now}$ >> $\mathrm{T\gets T\cdot \Delta}$ ## 例题 - [P3878 [TJOI2010]分金币](https://www.luogu.com.cn/problem/P3878) ```cpp #include<bits/stdc++.h> using namespace std; #define fo(v,a,b) for(int v=a;v<=b;v++) #define fo2(v,a,b) for(v=a;v<=b;v++) #define fr(v,a,b) for(int v=a;v>=b;v--) #define rg register #define il inline typedef long long ll; typedef double db; const int N=40; int n;int v[N]; int ans; int calc() { int sum1=0,sum2=0; fo(i,1,(n+1)>>1) sum1+=v[i]; fo(i,((n+1)>>1)+1,n) sum2+=v[i]; return abs(sum1-sum2); } void SA() { db t=2000,delta=0.99,t_k=1e-11; while(t>t_k) { int x=rand()%n+1,y=rand()%n+1; swap(v[x],v[y]); ll now=calc(); if(now<ans)ans=now; else if(exp((ans-now)/t)<(db)rand()/RAND_MAX) swap(v[x],v[y]); t*=delta; } } void solve() { cin>>n; fo(i,1,n)scanf("%d",&v[i]); srand(rand()); ans=calc(); fo(i,1,300)SA(); printf("%d\n",ans); } int main() { srand(1919810+time(0)); srand(rand());srand(rand()); int T;cin>>T; while(T--)solve(); return 0; } ```