新式骗分——模拟退火

博客咕咕咕的时间有点长(似乎是太长了)

今天写一下模拟退火吧。。。发现了骗分的新大陆

一：背景

模拟退火解决的是一种什么样的问题呢？

模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法， 用来在一个大的搜寻空间内找寻命题的最优解。 模拟退火是由S.Kirkpatrick, C.D.Gelatt和>M.P.Vecchi在1983年所发明的。V.Černý在1985年也独立发明此演算法。模>拟退火算法是解决TSP问题的有效方法之一。
—— 来自百度百科

照例引用百度百科。

其实模拟退火就是一种解决问题的普遍方法。

二：爬山算法及其优化

针对一个求最值的问题，我们可以采用一种贪心的方法，被称作“爬山算法”。爬山算法指的就是每一步都将当前节点的值与其邻居节点比较，如果有更优值就取，否则就维持当前的解。很明显，这个算法可以找到一个局部最优解。但是其有一个致命的缺陷，那就是只能找到局部最优解，但是并不能保证找到的解是一个全局最优解。

就比如说上面这个图，当我们在D点出发，使用爬山算法，即可到达B点，很明显这既是局部最优解，又是全局最优解。但是如果从C点或E点出发，我们最后会到达A点，（然后愉快的WA）
这种做法很明显是不行的，那么怎么使其变的正确 或者说大约正确呢？
上文提到的三位大佬想出来了一个绝妙的解决方案：
使用随机算法，使得每一次搜索到比当前解差的解时，都有一定概率接受这个解。但是光随机也是不行的，所以随着循环次数的增加，会不断降低接受更劣解的概率。这就是模拟退火的主要思想。

三：具体实现

先定义一下变量及数组

t: 温度 决定了接受更劣解的概率 与down一起决定了退火的时长 更高的初始温度意味着更精确的答案， 但也意味着需要更多的时间

down: 每一次循环降低t的系数，一般是 0.9 ~ 1 的一个实数

delta: 当前解与最优解的差

now_w: 目前得到的最优解

ew：当前解

步骤：

1.透过最优解计算出当前解。

2.如果获得了更优解 直接接受
3.更劣解有概率接受

 void sa(){
	double t = 3000;
	while(t > 1e-15){
		double ex = ans_x + (rand() * 2 - RAND_MAX) * t;
		double ey = ans_y + (rand() * 2 - RAND_MAX) * t;
		double ew = get_eng(ex, ey);//构造解的函数
		double delta = ew - ans_w;
		if(delta < 0){
			ans_x = ex;
			ans_y = ey;
			ans_w = ew;
		}
		else if(exp(-delta / t) * RAND_MAX > rand()){
			ans_x = ex;
			ans_y = ey;
		}
		t *= down;
	}
}

来自luoguP1337 [JSOI2004]平衡点 / 吊打XXX

值得注意的几个点：

(rand() 2 - RAND_MAX) t : 求新解的方法

exp(-delta / t) * RAND_MAX > rand() : 来自前人的玄学判断

模拟退火流程图