爬山算法

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

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

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

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

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

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

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

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

解决方法：随机重启爬山算法

深度优先搜索算法深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。2

其他相关算法stochastic hill climbing

First-choice hill climbing

Random-restart hill climbing

Simulated annealing search

Local beam search

本词条内容贡献者为:

黄伦先 - 副教授 - 西南大学