爬山法搜索

4.3.1 爬山法搜索

图4.11中显示了爬山法（hill-climbing）搜索的算法。它是一个向值增加的方向持续移动的简单循环过程——也就是，登高。它将会在到达一个“峰顶”时终止，相邻状态中没有比它更高的值。这个算法不维护搜索树，因此当前节点的数据结构只需要记录当前状态和它的目标函数值。爬山法不会前瞻与当前状态不直接相邻的那些状态的值。这就像健忘的人在大雾中试图登顶珠穆朗玛峰一样。

图4.11 爬山法搜索算法（最陡上升方式），这是最基本的局部搜索技术。在每一步中当前的节点都会被最佳邻节点所代替；按这种方式，最佳邻节点意味着VALUE最高的邻居节点，但是如果使用启发式耗散估计h，我们要找的就是h最低的邻居节点

我们将用第3.2.1节介绍的八皇后问题举例说明爬山法算法。局部搜索算法通常使用完全状态形式化，即每个状态都在棋盘上放八个皇后，每列一个。后继函数返回的是移动一个皇后到和它同一列的另一个方格中的所有可能的状态（因此每个状态有8 × 7 = 56个后继）。启发式耗散函数h是可以彼此攻击的皇后对的数量，不管中间是否有障碍。该函数的全局最小值是 0，仅在找到完美解时才能得到这个值。图4.12（a）显示了一个h = 17的状态。图中还显示了它的所有后继的值，最好的后继的h =12。爬山法算法通常在最佳后继的集合中随机选择一个进行扩展，如果这样的后继多于一个的话。

图4.12 （a）八皇后问题的一个状态，其中启发式耗散估计h=17，方格中显示的数字表示将这一列中的皇后移到该方格而得到的后继的h值。最佳移动在图中标记出来了。（b）八皇后问题状态空间中的一个局部极小值；该状态的h=1，但是它的每个后继的h值都比它高

爬山法有时称为贪婪局部搜索，因为它只是选择邻居状态中最好的一个，而事先不考虑之后下一步往哪个方向走。尽管贪婪是七宗罪之一，贪婪算法却往往有很好的效果。爬山法能很快朝着解的方向进展，因为它通常很容易改进一个坏的状态。例如，从图4.12（a）中的状态，它只需要五步就能到达图4.12（b）中的状态，它的h = 1基本上很接近于解了。不幸的是，爬山法经常会遇到下面的问题：

局部极大值：局部极大值是一个比它的每个邻居状态都高的峰顶，但是比全局最大值要低。爬山法算法到达局部极大值附近就会被拉向峰顶，然后被卡在局部极大值处无处可走。图4.10示意性地表现了这种情况。更具体地，图4.12（b）中的状态事实上是一个局部极大值（即耗散h的局部极小值）；不管移动哪个皇后得到的情况都会比原来差。

山脊：图4.13显示了山脊的情况。山脊造成一系列的局部极大值，贪婪算法处理这种情况是很难的。

高原：高原是在状态空间地形图上评价函数值平坦的一块区域。它可能是一块平的局部极大值，不存在上山的出路，或者是一个山肩，从山肩还有可能取得进展。（参见图4.10。）爬山法搜索可能无法找到离开高原的道路。

在每种情况下，爬山法算法都会达到无法取得进展的地点。从一个随机生成的八皇后问题的状态开始，最陡上升的爬山法86％的情况下会被卡住，只有14％的问题实例能求解。这个算法速度很快，成功找到最优解的平均步数是4步，被卡住的平均步数是3步——对于包含88≈1千7百万个状态的状态空间这是不错的结果。

图4.11中的算法如果到达一个高原，最佳后继的状态值和当前状态值相等时将会停止。如果高原其实是如图4.10中所示的山肩，继续前进——即侧向移动是一个好主意吗？答案通常是肯定的，但是我们要小心。如果我们在没有上山移动的情况下总是允许侧向移动，那么当到达一个平坦的局部极大值而不是山肩的时候，算法会陷入无限循环。一种常规的解决办法是设置允许连续侧向移动的次数限制。例如，我们在八皇后问题中允许最多连续侧向移动100次。这使问题实例的解决率从14％提高到了94％。成功的代价是：算法对于每个成功搜索实例的平均步数为大约21步，每个失败实例的平均步数为大约64步。

人们发明了爬山法的许多变化形式。随机爬山法在上山移动中随机地选择下一步；选择的概率随着上山移动的陡峭程度而变化。这种算法通常比最陡上升算法的收敛速度慢不少，但是在某些状态空间地形图上能找到更好的解。首选爬山法实现了随机爬山法，它采用的方式是随机地生成后继节点直到生成一个优于当前节点的后继。这个算法在有很多后继节点的情况下（例如上千个）是个好策略。习题4.16要求你研究这个问题。

图4.13 为什么山脊会给爬山法带来困难的图示。图中的状态网格（黑色圆点）叠加在从左到右上升的山脊上，创造了一个不直接相连的局部极大值序列。从每个局部极大点出发，可能的行动都是指向下山方向的

到现在为止我们描述的爬山法算法还是不完备的——它们经常会在目标存在的情况下因为被局部极大值卡住而找不到该目标。随机重新开始的爬山法采纳了一条著名的谚语：“如果一开始没有成功，那么尝试，继续尝试。”它通过随机生成的初始状态[14]来进行一系列的爬山法搜索，找到目标时停止搜索。这个算法是完备的概率接近于1，原因是它最终会生成一个目标状态作为初始状态。如果每次爬山法搜索成功的概率为p，那么需要重新开始搜索的期望次数为1/p。对于不允许侧向移动的八皇后问题实例，p≈0.14，因此我们大概需要7次迭代就能找到目标（6次失败1次成功）。所需步数的期望值为一次成功迭代的搜索步数加上失败的搜索步数与(1 − p) / p的乘积，大约是22步。当我们允许侧向移动时，平均需要迭代约1 / 0.94≈1.06次，平均的步数为(1 × 21)+(0.06 / 0.94) × 64≈25步。那么对于八皇后问题，随机重新开始的爬山法实际上是非常有效的。甚至对于三百万个皇后，这个方法用不了一分钟就可以找到解。[15]

爬山法算法成功与否在很大程度上取决于状态空间地形图的形状：如果在图中几乎没有局部极大值和高原，随机重新开始的爬山法将会很快地找到好的解。另一方面，许多实际问题的地形图就像平坦的地板上的一群豪猪，每个豪猪身上刺的尖端还生活着微小的豪猪，乃至无限。NP 难题通常有指数级数量的局部极大值。尽管如此，经过少数随机重新开始的搜索之后还是能找到一个合理的较好的局部极大值的。