爬山算法的实例应用

下面是一个用爬山算法求解问题的例子，动画中展示了算法的搜索过程，以及目标函数值随迭代步数的变化。

上面的算法顺利的通过了所有测试用例，但是这依赖于一个假设：“该问题是一个凸优化问题！”从上面的目标函数变化曲线可以看出来，曲线是一直在下降的，直到停留在最低点。幸运的是，这个问题确实是一个凸优化问题，证明过程在本题的官方题解里面。

假如我们没法证明这是个凸优化问题，是否存在一种更通用的算法来解决该问题呢？答案是有的，就是模拟退火算法！

模拟退火算法的思路也很简单，就是为算法引入一定的随机性，让它有一定的能力去跳出局部最优解。让我们对前面爬山算法的伪代码稍作改造：

# 模拟退火算法伪代码 cur_sol = init() while not stop: for new_sol in neighbor(cur_sol): delt = obj(new_sol) - best_obj

可以看到，在算法刚开始运行时， noise 的值较大，那么当前解的变化趋向于随机移动。但随着 noise 的降低，算法接受较差的解的概率逐渐减小，最终退化成前面的爬山算法。这样做的目的是使算法能够更充分的探索解空间，所以对于非凸优化的问题，模拟退火算法通常能够比爬山法找到更优的解，在实际生活中也有着更加广泛的应用。