模拟退火详解

本算法建议谨慎使用,否则一不小心就会变成模拟退役

爬山算法

爬山算法是一种贪心搜索,每次从当前状态的所有后继状态中选择一个最优解继续搜索,直到达到一个局部最优解后不再搜索。

优点:好写

缺点:容易陷入局部最优解出不来

就像下图一样

多随机几个初始状态就能减小(不能消除)缺点

模拟退火

模拟退火来源于金属的冷却过程

温度高时,金属内能较大,原子活动范围大。

温度低时,金属内能较小,原子活动范围小。

搜索的时候也类似

T(温度)初始值很大,每次呈上一个小于1的数,T越大,搜索状态越容易转移

T比较大的时候,不用管下一个搜索状态是好是坏,大概率转移

T比较小的时候,类似爬山算法

可以看这个里边的gif理解

为了保证正确性,可以多做几次。

或者可以用上ctime,控制程序运行时间,卡题目时限,在规定时间多运行几次

就像下面这样

while(clock()<Time){}

注意不同的系统返回的时间的单位可能不同!


P1337 [JSOI2004]平衡点 / 吊打XXX 题解

P2538 [SCOI2008]城堡

在各种题目中都能用到,正确性不能保证,很少用作正解,但好的时候能媲美标算。

还有在各种提交答案题中都能用到

原文地址:https://www.cnblogs.com/wljss/p/14966935.html