4.3官方还将广泛.pptVIP

4.3 启发式搜索 盲目搜索法从理论上讲都能找到问题的解，但无论是广度优先还是深度优先搜索都是一种穷举遍历的过程，当状态空间很大，图中节点很多时，盲目搜索方法就存在局限性。 在许多问题求解中，有许多与问题有关的信息可利用，以加速整个问题的求解过程。这类与问题有关的信息成为启发信息，利用启发信息的搜索称为启发式搜索。 4.3.1 启发式搜索的基本概念 启发式搜索就是用启发信息去评估节点有希望的程度并排序，优先扩展最有希望的节点。 启发信息的利用就是要引导搜索选取最有希望的节点进行扩展。 评估节点的方法是采用估计函数。 引入函数k(ni,nj),g*(n),h*(n)和f*(n). k(ni,nj)表示任意节点ni和nj最小代价路径的实际代价值； g*(n)=k(s,n),即g*(n)为从初始节点S至节点n的最小代价路径的实际值； h*(n)为节点n到目标节点集ti的所有k(n,ti)中最小的值，即为从节点n到目标节点最小代价路径的实际值。 f*(n)= g*(n)+h*(n)为从S开始约束通过节点n的一条最佳路径的代价。 f*(n)= h*(n)为从S开始无约束到某个目标节点的一条最佳路径的代价。 定义估价函数f(n)=g(n)+h(n) 其中g(n)是g*(n)的估计，h(n)是h*(n)的估计。对于g(n)来说，通常选择为初始节点到节点n这段路径的代价，故g(n)>=g*(n)；h(n)依赖于有关问题的启发信息，是h*(n)的估计值。 一般来说，在f(n)中，g(n)的比重越大，越接近于广度优先的搜索方法，其完备性越好，但搜索效率降低；h(n)比重越大则越接近于深度优先的搜索方式，搜索效率高，完备性降低。 4.3.2 A算法 使用估价函数f(n)扩展和搜索节点的搜索法称为A算法。其过程如下： 4.3.3 最佳图搜索算法A* 在启发搜索A算法中，当启发函数h(n)处在h*(n)的下界范围，即满足h(n)<=h*(n)时，则我们把这个搜索算法称为A*算法。 在问题有解时，A*一定能找到一条到达目标节点的最佳路径。 A*算法从理论上给出了求解最佳解的条件h(n)<=h*(n)。 启发函数h(n)的定义(以八数码问题为例) (1)启发函数根据任意节点与目标之间的差异来定义。如上节中取h(n)=W(n)，则虽然h*(n)是未知的，但根据不在位数码的个数，就能得出至少要移动W(n)步才能达到目标，则有W(n)<= h*(n)。 (2)启发函数考虑任意节点与目标节点的距离信息，如上节中取h(n)=P(n)， P(n)定义为每一个数码与其目标节点之间的距离的总和，那么同样断定至少也要移动P(n)步才能达到目标，因此有P(n)<= h*(n)。 A*算法具有可纳性和最优性。 可纳性指对任意一个图，当初始节点S到目标节点t有一条路径存在时，如果搜索算法总是在找到一条从S到t的最佳路径上结束，则称该搜索算法是可纳的。 最优性是指A*算法效率高于其他搜索法，当h(n)的选取越接近h*（n），A*算法效率越高，搜索就像是向目标直接进发，扩展的节点数和搜索时间也越小。 * * *