【AI】Hill Climbing 爬山算法
爬山算法
- 浅谈爬山算法
- 爬山算法的一种改进方法
- 爬山算法是对DFS的一种改进
浅谈爬山算法
爬山算法 每次拿相邻点与当前点进行比对，取两者中较优者作为爬坡的下一步。循环直到该点的相邻点中不再有比其更大的点，我们将其作为山顶。
爬山算法，是一种简单的局部贪心搜索算法。
爬山算法的缺点非常明显，那就是陷入 局部最优解 而不一定能搜索到 全局最优解。
从C点开始爬山，当爬山算法搜索到A点时，因为A点无论向哪个方向小幅度移动，都不能得到更优的解。爬山算法会停止搜索，从而将A点当作“山顶”。但是其实全局最优解是B点而非A点。
爬山算法的一种改进方法
随机重启爬山算法
顾名思义，那就是在随机地点重启爬山算法。
我们不仅仅从C点开始爬山，随机的从D点，E点，F点等等地点开始爬山，按照爬山算法，E点与F点会抵达全局最优点。但是因为示例模型的简单，所以我们抵达了全局最优解，但是事实上也许也只是一个局部最优解。
随机重启爬山算法，或称随机爬山算法，一定程度上缓解了爬山算法的弊端、算法缺陷。
爬山算法是对DFS的一种改进
DFS，Depth-first Search，深度优先搜索算法。相关博客：【AI】DFS 深度优先搜索
爬山算法是启发式的，而深度优先算法是遍历的。启发式的不用遍历，所以效率上爬山算法会比深度优先遍历算法高。