什么是爬山算法？

概念

爬山算法是一种局部择优的方法，是一种局部贪心的最优算法。

采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解，属于人工智能算法的一种。

主要思想

随机选择一个登山的起点；

每次拿相邻点与当前点进行比对,取两者中较优者,作为爬坡的下一步；

重复第2步，直至该点的邻近点中不再有比其大的点；

选择该点作为本次爬山的顶点,即为该算法获得的最优解。

爬山算法的主要算法：

首选爬山算法

依次寻找该点X的邻近点中首次出现的比点X价值高的点，并将该点作为爬山的点(此处说的价值高，在该题中是指Z或f(x,y)值较大)。

依次循环，直至该点的邻近点中不再有比其大的点。我们成为该点就是山的顶点,又称为最优点。

最陡爬山算法

最陡爬山算法是在首选爬山算法上的一种改良，它规定每次选取邻近点价值最大的那个点作为爬上的点。

随机重新开始爬山算法

随机重新开始爬山算法是基于最陡爬山算法，其实就是加一个达到全局最优解的条件，如果满足该条件，就结束运算,反之则无限次重复运算最陡爬山算法。

优点

避免遍历，通过启发选择部分节点，从而达到提高效率的目的。

缺点

因为不是全面搜索，所以结果可能不是最佳。 爬山算法一般存在以下问题：

1. 局部最大：某个节点比周围任何一个邻居都高，但是它却不是整个问题的最高点。

2. 高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。

3. 山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。