百度一下 藏锋者 就能快速找到本站! 每日资讯归档 下载藏锋者到桌面一键访问

当前位置:主页 > 人工智能 > 启发性信息和评估函数

启发性信息和评估函数

所在栏目:人工智能 时间:11-17 13:18 分享:

在搜索过程中,关键的一步就是如何选择下一个要考察的节点,选择的方法不同就形成了不同的搜索策略。如果在选择节点时能充分利用与问题有关的特征信息,估计出节点的重要性,就能在搜索时选择重要性较高的节点,以利于求得最优解。我们称这个过程为启发式搜索。“启发式”实际上代表了“大拇指准则(ThumbRules)”:在大多数情况下是成功的,但不能保证一定成功的准则。

用来评估节点重要性的函数称为评估函数。评估函数f(x)定义为从初始节点S0出发,约束地经过节点x到达目标节点Sg的所有路径中最小路径代价的估计值。其一般形式为:f(x)=g(x)+h(x)其中,g(x)表示从初始节点S0到节点x的实际代价;h(x)表示从x到目标节点Sg的最优路径的评估代价,它体现了问题的启发式信息,其形式要根据问题的特性确定,h(x)称为启发式函数。因此,启发式方法把对问题状态的描述转换成了对问题解决程度的描述,这一程度用评估函数的值来表示。

如对8数码问题,评估函数可以表示为:f(x)=d(x)+w(x)其中,d(x)表示节点x在搜索树中的深度,w(x)表示节点x中不在目标状态中相应位置的数码个数。则w(x)就包含了问题的启发式信息。

数码问题一般来说,某节点w(x)越大,即“不在目标位置”的数码个数越多,说明它离目标节点越远。

对初始节点S0,由于d(S0)=0,w(S0)=4,因此,f(S0)=4。

这里只是说明了评估函数的含义及如何选择评估函数和计算评估函数值。

在搜索过程中除了需要计算初始节点的评估函数外,更多地是需要计算新生成节点的评估函数。

大多数前向推理问题可以表示为OR图,其中图中的节点表示问题的状态,弧表示应用于当前状态的规则,该规则引起状态的转换。当有多个规则可用于当前状态的时候,我们可以从该状态的各个子状态中选择一个比较好的状态作为下一个状态。

启发性信息和评估函数 免费邮件订阅: 邮件订阅

图片推荐

热点排行榜

CopyRight? 2013 www.cangfengzhe.com All rights reserved