文档介绍：(读书报告、研究报告)考核科目:人工智能学生所在院(系):计算机学院学生所在学科:计学生姓名:学号:学生类别:学考核结果算机术科学与技术阅卷人人工智能读书报告——基于动态加权的a*搜索算法研究启发式搜索启发式搜索就是在状态空间中对每一个搜索的位置进行评估,选择最好的位置,再从这个位置进行搜索直到目标。在启发式搜索中,对位置的估价是十分重要的。采用了不同的评估方法可以有不同的效果。最佳优先搜索的最广为人知的形式称为a*(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价:d(n)=g(n)+h(n),因为以g(n)给出了从起始节点到节点n的路径耗散,而h(n)是从节点n到目标节点的最低耗散路径的估计耗散值,因此d(n)=,如果我们想要找到最低耗散解,首先尝试找到g(n)+h(n)值最小的节点是合理的。由a*定义可以发现这个策略不只是合理的:倘若启发函数h(n)满足一定的条件,搜索既是完备的也是最优的。如果把a*搜索用于tree-search,它的最优性是能够直接分析的。在这种情况下,如果h(n)是一个可采纳启发式--也就是说,倘若h(n)从不会过高估计到达目标的耗散--a*算法是最优的。可采纳启发式天生是最优的,因为他们认为求解问题的耗散是低于实际耗散的。因为g(n)是到达节点n的确切耗散,我们得到一个直接的结论:d(n)永远不会高估经过节点n的解的实际耗散。常用的启发算法有:蚁群算法,遗传算法、模拟退火算法等。greedysearchondoutperformssearchonh动态加权启发式搜索算法应用启发式搜索中的加权技术,其主要目的是调整搜索中深度优先与宽度优先的比值,以提高搜索效率。通常有两种加权技术,即常数加权与动态加权技术。由于在常数加权中,同样的加权量毫无区别地施用在每一个节点上,加权的作用取决于各单一节点。而在动态加权中,则会动态地对不同层上的节点施以不同的加权量。故一般地,采用动态加权技术的启发式搜索效率要比静态(即常数)加权好。,如果该算法总能找到一条求解路径,其耗散值至少为??ft*(s)。这里ft*(s)表示从初始节点s出发至目标节点的最佳路径的耗散值,ε∈(0,1)。根据加权技术的基本思想,启发式评价函数的动态加权应达到这样的效果:在搜索树的浅层,搜索应呈现深度优先搜索的特性;而随着搜索树的层次越来越深,应逐步呈现出宽度优先搜索的特性。据此,我们可以定义动态加权的启发式评价函数为:ft(n)?t(gt(n),??(1?d(n)/n)?ht(n))其中d(n)表示节点n在搜索树中的深度,n表示预期的目标节点在搜索树中的深度;?采用上述的启发式评价函数ft,且ht≥ht*,则称算法raε为算法ra?*。若模t满足t(??a,??b)???t(a,b),这里ε∈(0,1),属于最佳路径上的且在open表中属于最浅层的任意节点n,仍然有gt(n)=gt*(n),最后经过推导可以得到:ft(n)?t(gt(n),??(1?d(n)/n)?ht(n))=t(gt*(n),??(1?d(n)/n)?ht(n))≥t(gt*(n),??(1?d(n)/n)?ht*(n))≥t(gt*(n),??ht*(n))≥t(??gt*(n),??ht*(n))≥??ft*(s)动态加权不能克服指数爆炸问题martelli已经证明了,在最坏情况下,算法a*的时间复杂度为o(2n)这里m是图的节点数。使用动态加权技术的本质在于提高搜索效率,但是动态加权技术很难消除指数爆炸现象。’被称为引导了一个?(n)的标准化误差,若对于b元树上的所有节点,存在两个固定的正数β和γ和一个正交函数?(.),ht(n)?ht*(n)ht(n)?ht*(n)|??]??/b,γ>1和p[||??]??/b?<1使得p[|?(ht*(n))?(ht*(n))(n)引出?(n)=n的标准化误差,则当0<?0<1<a≤11??d(n)时,启发式评价函数为aht(n)???(1?)?ht(n)引出同样的?(n)?n的n标准化误差。这里??(0,1],?0得含义如同极限、概率定义中常见的,它与?不同。ht(n)?ht*(n)ht(n)?ht*(n)证明过程:令y(n)?;y(n)?因为**?(ht(n))?(ht(n))11?aht*(n)y(n)1?a????(y)=y,故有y(n)?y(n)?根据定理成立条aa?(ht*(n))aa件可知,当a1?时,p[|y(n)|?(1?a)?a??]?p[|y(n)|?(a?1)?a??]?令?=(β+1)a–1,当0??0?