爬山算法学习笔记

爬山算法是一种局部择优的算法，采用启发式方法，是一种对深搜的改进。 **它利用反馈的信息帮助生成解的决策。** 就是讲，目前无法到达最优解，但是可以选择两个答案时，根据反馈信息生成一个新的可能解。 如果把最优状态看作山的最高峰，那么，我们在当前的山峰（不一定是最优解）附件找一个点，如果更优就转移到那个点。 就好像你一直在山顶边徘徊，一会左边，一会右边。 所以，如果只有一个最高的山峰时，最终一定可以落脚在山顶，对吧。 转化回来，就是，**爬山算法对于单峰函数一定可行！** 这个算法的应用就是如果你不会正解时，可以用它来写暴力或玄学的做法！ 摘自OI-WIKI： >爬山算法一般会引入温度参数（类似模拟退火）。类比地说，爬山算法就像是一只兔子喝醉了在山上跳，它每次都会朝着它所认为的更高的地方（这往往只是个不准确的趋势）跳，显然它有可能一次跳到山顶，也可能跳过头翻到对面去。不过没关系，兔子翻过去之后还会跳回来。显然这个过程很没有用，兔子永远都找不到出路，所以在这个过程中兔子冷静下来并在每次跳的时候更加谨慎，少跳一点，以到达合适的最优点。 >兔子逐渐变得清醒的过程就是降温过程，即温度参数在爬山的时候会不断减小。 **这个降温参数通常在0.985到0.999这个区间内。** 爬山算法的劣势就是： **当答案不是单峰函数时，会陷入局部最优解**--从而一场空！ 所以我们引入模拟退火。