爬山算法(Hill Climbing)


前言
最近在学习爬山算法以及模拟退火,爬山算法是模拟退火的前置技能。
我之所以写下这篇博客,是因为时间已经很晚了而我还没搞懂模拟退火。
但是爬山我已经差不多懂了,代码啥的也会敲了,是一种比较简单的贪心算法。
欢迎各位大佬来指出不足2333333


算法简介
爬山算法,顾名思义,往高处爬升。
是一种用到了随机化的比较简单的贪心算法。


缺陷
简单粗暴点说:
随机选取一点,看它两边的点,哪个更高走哪边,
直到它的两边的高度都比当前的高度要低。
这就是爬山算法。
那么问题来了!
在我们刚开始接触贪心的时候,就会发现:
贪心所选择的路径不一定是全局最优解,往往是局部最优解。
爬山算法同样如此。


改进
上面的那种只选择一个点的爬山算法,我们称之为单点爬山。
单点爬山随便造几个小数据都能卡死这是显然意见的对吧?
(当然那个人欧气太好我就没办法了,多测几遍取值也许可行)
为了提高成功率,我们可以随机一堆点然后依次进行单点爬山,这就是多点爬山。
(据说这才是正宗的爬山虽说仍然能被卡掉)
我是喜欢个点。
具体多少个点看你们自己喜好咯,点多了可能会T,点少了又可能会WA。
另外,如果这个点里面有重复出现的点,那就会做多余的事,会降低正确率。
所以我们就需要开个桶来保证出来的点一定是互不相同的。
大概就是这样,至于题目能不能A,就看你欧气了2333333



发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s