关于启发式搜索算法的改进策略分析.doc

关于启发式搜索算法的改进策略分析.doc论文写作不是一朝一夕,更不能胡编乱造。需要切身研究、调查、分析与归纳,需要大量的数据处理与查阅资料。本论文不求带给你多大的帮助,只愿做您脚下之石。该文档为word格式,方便复制修改打印,写论文就是这么简单 以下是正文 关于启发式搜索算法的改进策略分析(作者:单位:邮编:)关于启发式搜索算法的改进策略分析状态空间搜索,如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说,两点之间求一线路,这两点是求解的开始和问题的结果,而这一线路不一定是直线,可以是曲折的。由于求解问题的过程中分枝有很多,主要是求解过程中求解条件的不确定性,不完备性造成的,使得求解的路径很多这就构成了一个图,我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。一、算法的提出在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。启发中的估价是用估价函数表示的,如:f(n)=g(n)+h(n)其中f(n)是节点n的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价[1]。在这里主要是h(n)体现了搜索的启发信息。估价价函数确定后,在检索时总是沿着f(n)最小的支路进行检索直到叶子节点,。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。在这里就要用到修正启发式搜索算法了。二、最短路径问题与算法效能所谓最短路径问题有很多种意思,在这里启发式指的是一个在一个搜寻树的节点上定义的函数h(n),用于评估从此节点到目标节点最便宜的路径。启发式通常用于资讯充份的搜寻算法,例如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点;A*则会为g(n)+h(n)选择最低代价的节点,此g(n)是从起始节点到目前节点的路径的确实代价。如果h(n)是可接受的(admissible)意即h(n)未曾付出超过达到目标的代价,则A*—定会找出最佳解。任何的搜寻问题中,每个节点都有b个选择以及到达目标的深度d,—个毫无技巧的算法通常都要搜寻bd个节点才能找到答案。启发式算法借由使用某种切割机制降低了分叉率(branchingfactor)以改进搜寻效率,由b降到较低的b'。分叉率可以用来定义启发式算法的偏序关系,例如:若在一个n节点的搜寻树上,h1(n)的分叉率较h2(n)低,则h1(n)h2(n)o启发式为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率,因此它们拥有较佳效率的计算能力。三、算法的修正专家的可贵之处,就在于他们独特的推理方式,从其宝贵的经验,我们经过一系列推算,可以得到一个新型的评价函数:h(a,b)=Wo+W1f(a,b)=Wo+W1D(a,b)(1)(W是一种权矢量,D是一种相似度检测)在检索树上任选K个节点,对评价函数h(a,b)中的权矢量W进行修正:设修正后的权矢量为W,修正后的评价函数为h(a,b),则有:WJ=W+aF(a,b)(F代表一种欧氏距离*最终推出:h,(a,b)-h(a,b)=a|F(a,b)|2(2)