玄(pian)学(fen)算法——模拟退火
模拟退火
算法
OI
NOIP在即，还是复习一下经典玄(pian)学(fen)算法，多骗个二三十分，以免爆零。
我个人理解模拟退火就是随机猜，不过通过温度机制，让当前状态越接近正确答案时随机变化幅度越小，来尽量接近正确答案。大概过程是每次随机出一个新答案，如果这个答案比现在更优秀就直接接受它，否则就根据某个热力学公式按照一定概率接受它，防止被卡在局部最小值，最后降低温度参数。
调参是模拟退火的主要乐趣，可以利用用对拍大法。如果有条件最好卡时。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
#define SEED time(0)
const double TBEGIN = 3000;
const double EPS = 1e-14;
const double TEND = EPS;
const double DELTAT = 0.99;
const double INF = 1e18;
template<typename T,typename TComp>
T SA(T s){
srand(SEED);
double t = TBEGIN;
double ans = INF;
T now = s;
while(t>EPS){
T n = now.get_new([](double t)->double{
return (rand()*2-RAND_MAX)*t;
},t);
double nans = n.get_ans();
if(TComp()(nans,ans)){
ans = nans;
now = n;
}else{
if(exp((ans-nans)/t)*RAND_MAX>rand()){
now = n;
}
}
t *= DELTAT;
}
return now;
}
const double MAX_TIME = 0.8;
template<typename T,typename TComp>
T SA_Time(T s){
state ans = SA<state,less<double> >(s);
while((double)clock()/CLOCKS_PER_SEC<MAX_TIME)
ans = SA<state,less<double> >(ans);
return ans;
}
|
代码说明：T是状态结构体，需要定义T get_new(double(*prand)(double),double t)方法用于更新状态，double get_ans()方法用于计算状态最小值。TComp是less<double>(最小化ans)或greater<double>(最大化ans)
