启发式搜索 市赛一等奖

启发式搜索前面所讨论的搜索策略的一个共同特点是它们的搜索路径是事先决定好的，没有利用问题求解的过程中所产生的状态的任何特性信息。因而这样的搜索策略都具有较大的盲目性。如果能找到一种搜索方法，能充分利用待求解问题自身的特性信息以指导搜索朝着最有希望的方向前进，就可以提高搜索的效率。我们称这种搜索策略为启发式搜索。1启发性信息和启发函数

1.启发性信息顾名思义，就是指有利于快速找到问题的解的信息。如，在搜索过程中，要对节点进行扩展，到底先扩展哪个节点更好一些？当生成一此后续节点时，同样也面临着选择生成哪些后续节点的问题。如果遇到此无用节点，我们还要对删除这些节点做出选择。有了启发性信息，我们就可以比较容易地做出选择。由此可见，启发性信息在搜索过程中起到一个引导搜索的作用。现在的问题是如何才能找到启发性信息并把它用到搜索中。

2.启发函数首先，我们应该合理定义一个问题的启发性信息并把它用具体的表示方法表示出来。这便是我们要介绍的另一个概念——启发函数。启发函数，用来估计搜索树上节点与目标节点接近程度的一种函数，通常记为h(x)。对于不同的问题，启发函数有不同的形式。如何定义一个启发函数呢？启发函数并没有固定的模式，具体问题需要具体分析。如：有些问题的启发函数可以用一个节点到目标节点的某种距离或差异度量来表示；有些可以用一个节点在最佳路径上的概率来表示；还有一些可以根据经验的主观打分来表示等等。下面我们考虑怎样来定义一个合适的启发函数以帮助我们尽可能快地沿着它所确定的搜索路径达到目标状态。首先我们要求的启发函数能够帮助我们从多个状态里找出一个看起来最有希望的状态节点。因此，启发函数应该为每个状态节点产生一个相应的最值，这个量值能够用来衡量该状态与目标状态之间的“距离”，即节点的函数值在某种意义上应能作为搜索工作量的一种度量。它能带助我们在几个状态节点中确定一个选择。从具有较小的启发雨数值的那个状态走向目标的搜索路径应应该比较短，即工作代价最低。上述讨论说明，一个启发函数应具有两个特征。首先，它们为达到目标状态的工作量提供一个合理的估计，这种估计越精确，用它来作的决定也就会越好；其次，启发函数值应该容易计算，它的使用应使搜索过程受益，而不是负担。八数码问题可以采用计算尚不在位的数码块的数目，估计它们各自离目标数码块的位置的“距离”，作为简单的启发函数。通常人们会猜想，一个尚有四个数码块未到位的状态要比一个只有两个数码块未到位的状态离目标更远（因此不会选择它）。但是这种考虑的缺点是没有考虑一个状态节点中各小块离目标位置有多远。如果两个数码块离它的目标位置很远，那么实际上还需要有许多次移动，才能生成另外的状态。一个比较合适的启发函数是：测算一个状态节点中每个数码块离目标的距离，并把这些值相加得到一个单一的值，作为该状态节点的启发函数值。具有小的启发函数值的节点较有可能处在最佳路径上。节点内各数码块的距离的计算方法：将一个数码块移至其在目标节点中的位置，至少需要移动的次数作为距离值，移动一次距离值为1。这个试探值容易计算，用它来作为从当前状态转移到目标状态要作的移动次数的一个粗略估计。例如，假定当前八数码问题的初始状态和目标状态如下图所示。2启发式搜索过程启发式搜索要用启发函数来导航，其搜索过程是在盲目搜索的一般过程中增加了启发两数值的计算与传播过程，并且OPEN表中的节点顺序是根据启发函数值来排列的。启发式搜索过程：

（1）把初始节点S，放入OPEN表，计算h(S)并建立目前只包含S的图G。（2）检查OPEN表是否为空，若为空则问题无解，退出。（3）把OPEN表的第一个节点取出放入CLOSED表中，并记该节点为n。（4）考察节点n是否为目标节点。若是，则求得了问题的解，退出。0（5）若节点不可扩展，则转到步骤2。

（6）扩展节点n，生成一组子节点，计算每个子节点x的函教值，把这些节点作为节点日的子节点加入到图G中。

（7）将第6步扩展的子节点放入到OPEN表中，再对OPEN名中所有子节点按其函数值大小以开序排序。（8）转到第2步。流程图表示启发式搜索过程如图所示。3问题与练习

1.什么是启发函数，它在启发式搜索中是如何起作用的？2.用启发式搜索