北大公开课-人工智能基础 24 局部搜索与群体智能之局部搜索算法（一）爬山法

爬山法是局部搜索算法的一种

通过迭代，找到这个局部内最小（山谷）或者最大值（山峰）

（最陡峭版本的）爬山算法逻辑

定义两个变量 current 当前节点

和neighbour 相邻节点

首先，将当前节点current 设置为初始问题状态 make-node(problem. initial-state)

然后开始循环 loop do

        将当前节点的后继节点successor 计入neighbour相邻节点

        如果 相邻节点 小于等于 当前节点的，则返回当前节点的状态

        否则，将该相邻节点（也就是大于当前节点的后继节点）计入当前节点

直到当前节点的后继节点均小于等于当前节点，则返回当前节点，为该局部的最大值。

爬山算法是一种最基础的局部搜索算法

它同样也是一种贪婪算法

因为该爬山算法并不考虑整体效果，而只考虑当前节点和它相邻节点的比较值

速度很快，内存占用小

八皇后问题，在一个国际象棋棋盘上，放置八个皇后，使他们不会相互冲突，有几种摆法。

爬山法的缺点，只能找到局部的最大值，而非全局最大值。

几种特殊的爬山法——随机爬山法

（1）随机选择后继节点，进行爬山，保留更高的后继节点。

（2）随机生成后继节点进行爬山

（3）随机生成初始节点——进行爬山，这样一定能找到一个全局最大值。