贪婪最佳优先搜索

4.1.1 贪婪最佳优先搜索

贪婪最佳优先搜索[9]试图扩展离目标节点最近的节点，建立在这样可能很快找到解的基础上。因此，它只用启发函数f(n) = h(n)来评价节点。

我们来看看这个算法在罗马尼亚寻径问题中是怎样进行的，它使用直线距离启发式，我们称之为hSLD。如果目标是Bucharest，我们需要知道到达Bucharest的直线距离，如图4.1所示。例如，hSLD(In(Arad))=366。注意hSLD的值不能由问题本身的描述计算得到。此外，通过一定的经验可以得知hSLD和实际路程相关并因此是一个有用的启发式。

图4.1 hSLD的值——到Bucharest的直线距离

图4.2显示了使用hSLD的贪婪最佳优先搜索寻找从Arad到Bucharest的路径的过程。从Arad出发最先扩展的节点是Sibiu，因为它到Bucharest的距离比Zerind和Timisoara都近。下一个扩展的节点是 Fagaras，因为它是离目标最近的节点。Fagaras 接下来生成了 Bucharest，也就是目标节点。对于这个特殊问题，使用 hSLD的贪婪最佳优先搜索在没有扩展任何不在解路径上的节点的情况下就找到了问题的解；因此，它的搜索代价是最小的。然而它不是最优的：经过Sibiu到Fagaras到Bucharest的路径比经过Rimnicu Vilcea到Pitesti到Bucharest的路径要长32公里。这说明了为什么这个算法被称为“贪婪的”——在每一步它都要试图找到离目标尽可能最近的节点。

使启发函数h(n)最小化会对错误的起点比较敏感。考虑从Iasi到Fagaras的问题，由启发式建议先扩展Neamt，因为它离Fagaras最近，但是这是条死路。解决方案是先到Vaslui——根据启发式实际上是离目标较远的一步——然后继续前往Urziceni，Bucharest，到Fagaras。在这种情况下，启发式将会引起扩展不必要的节点。此外，如果我们不仔细检查重复状态的话，将永远找不到解——搜索将会在Neamt和Iasi之间振荡。

贪婪最佳优先搜索在某些方面与深度优先搜索类似，它和深度优先搜索一样都更倾向于沿着一条路径搜索下去直到目标，但是在遇到死路的时候会退回。它和深度优先搜索有同样的缺陷——它不是最优的，也是不完备的（因为它可能沿着一条无限的路径走下去而不回来尝试其它的选择）。在最坏情况下，它的时间复杂度和空间复杂度都是 O(bm)，其中 m 是搜索空间的最大深度。然而，如果有一个好的启发函数，复杂度可以得到实在的降低。下降的幅度取决于特定的问题本身和启发函数的质量。

图4.2 使用直线距离启发式hSLD的贪婪最佳优先搜索，寻找前往的Bucharest的最短路径的几个阶段。节点都标明了该节点的h值