hill-climbing algorithm 爬山算法简介

参考链接： Hill爬山算法

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

 属于人工智能算法的一种。

 算法：

 function HILL-CLIMBING(problem) returns a state that is a local maximum

 inputs: problem, a problem

   local variables: current, a node

                          neighbor, a node

   current <- MAKE-NODE(INITIAL-STATE[problem])

   loop do

 neighbor <- a highest-valued successor of current

 if VALUE[neighbor]<= VALUE[current] then return STATE[current]

 current <- neighbor

 算法解释：

 从当前的节点开始，和周围的邻居节点的值进行比较。 

 如果当前节点是最大的，那么返回当前节点，作为最大值 

 (

 既山峰最高点

 )

 ；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。

 算法优缺点

 优点

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

 缺点

 因为不是全面搜索，所以结果可能不是最佳。

 爬山算法一般存在以下问题：

 1

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

 2

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

 3

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

 算法解释： 

 从当前的节点开始，和周围的邻居节点的值进行比较。 

 如果当前节点是最大的，那么返回当前节点，作为最大值 

 (

 既山峰最高点

 )

 ；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。

 算法优缺点

 优点 

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

 缺点

 因为不是全面搜索，所以结果可能不是最佳。 

 爬山算法一般存在以下问题： 

   1

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

  2

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

   3

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