搜索算法--爬山法

参考链接： 不知情的搜索算法

爬山算法即是模拟爬山的过程，随机选择一个位置爬山，每次朝着更高的方向移动，直到到达山顶，即每次都在临近的空间中选择最优解作为当前解，直到局部最优解。这样算法会陷入局部最优解，能否得到全局最优解取决于初始点的位置。初始点若选择在全局最优解附近，则就可能得到全局最优解。 

爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 属于人工智能算法的一种。 

算法描述 

从当前的节点开始，和周围的邻居节点的值进行比较。 如果当前节点是最大的，那么返回当前节点，作为最大值(既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。 

算法优缺点 

优点 

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

缺点 

因为不是全面搜索，所以结果可能不是最佳。 爬山算法一般存在以下问题： 1）局部最大：某个节点比周围任何一个邻居都高，但是它却不是整个问题的最高点。 2）高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 3）山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。