|
1.为什么需要启发式搜索
盲目搜索效率低,耗费过多的计算空间与时间,这是组合爆炸的一种表现形式。 自动控制网www.eadianqi.com版权所有
2.定义
进行搜索技术一般需要某些有关具体问题领域的特性的信息,把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。 本文来自www.eadianqi.com
3.启发式搜索策略
有关具体问题领域的信息常常可以用来简化搜索。一种利用启发信息的方法是应用某些准则来重新排列OPEN表中节点的顺序。然后,搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程,需要某些估算节点“希望”的量度,这种量度叫做估价函数(evaluation function)。 本文来自www.eadianqi.com
4.估价函数
为获得某些节点“希望”的启发信息,提供一个评定侯选扩展节点的方法,以便确定哪个节点最有可能在通向目标的最佳路径上。
f(n)——表示节点n的估价函数值。
建立估价函数的一般方法:试图确定一个处在最佳路径上的节点的概率;提出任意节点与目标集之间的距离量度或差别量度;或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 自动控制网www.eadianqi.com版权所有
|