RainAir
My OI Blog
RainAir
SA算法学习笔记

最近闲的无聊,学了一个模拟退火算法…

定义

首先,我们来了解一下这些算法的来历和用处。

人们在做一些复杂度为指数级别的题目时,忍受不住这种高复杂度的方法,于是发明了各种随机算法来获得近似最优解,例如爬山算法,模拟退火,遗传算法和蚁群算法等。

那么我们先来看一下最容易理解的爬山算法。

爬山算法

定义

所谓的爬山算法实际上就是简单的贪心算法,贪心算法通过从当前解的临近空间选择一个最优的解作为新的当前解,因此这个解很有可能是局部最优解,而不是全局最优的。因为领域周围没有比他更优的解了。

就是说,爬山算法的劣势在于容易陷入局部最优解。

那么,为了解决这种问题,从物理学出发,出现了模拟退火。

模拟退火

定义

模拟退火这个算法之所以不容易陷入局部最优解,是因为它在选择状态时,给被淘汰的状态一个“复活”的机会。这个机会是随机决定的,且越往后越小。所以说模拟退火是一种~看人品~随机算法。

总而言之,模拟退火的随机因素就是:这个随机因素就是:以一定的概率来接受一个比单前解要差的解。通过这个随机因素使得算法有可能跳出这个局部最优解。

大致实现过程

  1. 选定一个初始的符合题意的状态,选定一个温度T。

  2. 当温度大于边界时:

不难看出,随着时间不断飞逝,温度不断降低,接受一个更劣的解的可能性降低,解更稳定。

## 注意事项

  1. 温度的设置问题。过高,时间效率下降;过低,准确度下降。
  2. 退火的速度。
  3. 温度的管理问题。

大部分还要看人品。
注意:考试的时候srand()不要用time(NULL)来初始化,要自己随机选择一个种子,可以是特殊纪念的生日,不要选过于大众化的。这一点同时适用于hash算法。

例题

接下来我们以一道题目为主。
Luogu
虽然难度比较奇怪,但是这一题真的很简单……
堪称模拟退火的模板题。

思路就是不断的退火随机得到答案,然后变换答案。
由于模拟退火的随机性,不保证一遍能AC。(我是一遍A了)

详情见代码。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/118
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

SA算法学习笔记
最近闲的无聊,学了一个模拟退火算法... 定义 首先,我们来了解一下这些算法的来历和用处。 人们在做一些复杂度为指数级别的题目时,忍受不住这种高复杂度的方法,于是发明了各种随…
扫描二维码继续阅读
2018-07-08
标签
近期评论