人工智能读书报告-

2013年秋季学期研究生课程考核（读书报告、研究报告）考核科目:人工智能学生所在院（系）:计算机学院学生所在学科:计算机科学与技术学生姓名:学号:学生类别:学术考核结果阅卷人人工智能读书报告——基于动态加权的A*搜索算法研究启发式搜索启发式搜索就是在状态空间中对每一个搜索的位置进行评估，选择最好的位置，再从这个位置进行搜索直到目标。在启发式搜索中，对位置的估价是十分重要的。采用了不同的评估方法可以有不同的效果。最佳优先搜索的最广为人知的形式称为A*搜索.它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：d(n)=g(n)+h(n)，因为以g(n)给出了从起始节点到节点n的路径耗散，而h(n)是从节点n到目标节点的最低耗散路径的估计耗散值，因此d(n)=经过节点n的最低耗散解的估计耗散.这样，如果我们想要找到最低耗散解，首先尝试找到g(n)+h(n)值最小的节点是合理的。由A*定义可以发现这个策略不只是合理的:倘若启发函数h(n)满足一定的条件，搜索既是完备的也是最优的。如果把A*搜索用于Tree-Search,它的最优性是能够直接分析的。在这种情况下，如果h(n)是一个可采纳启发式--也就是说，倘若h(n)从不会过高估计到达目标的耗散--A*算法是最优的。可采纳启发式天生是最优的，因为他们认为求解问题的耗散是低于实际耗散的。因为g(n)是到达节点n的确切耗散，我们得到一个直接的结论：d(n)永远不会高估经过节点n的解的实际耗散。常用的启发算法有：蚁群算法，遗传算法、模拟退火算法等。Greedysearchondoutperformssearchonh动态加权启发式搜索算法应用启发式搜索中的加权技术,其主要目的是调整搜索中深度优先与宽度优先的比值,以提高搜索效率。通常有两种加权技术,即常数加权与动态加权技术。由于在常数加权中,同样的加权量毫无区别地施用在每一个节点上,加权的作用取决于各单一节点。而在动态加权中,则会动态地对不同层上的节点施以不同的加权量。故一般地,采用动态加权技术的启发式搜索效率要比静态(即常数)加权好。定义一.一个搜索算法是ε可采纳的,如果该算法总能找到一条求解路径,其耗散值至少为。这里表示从初始节点s出发至目标节点的最佳路径的耗散值，ε∈(0,1)。根据加权技术的基本思想,启发式评价函数的动态加权应达到这样的效果:在搜索树的浅层,搜索应呈现深度优先搜索的特性;而随着搜索树的层次越来越深,应逐步呈现出宽度优先搜索的特性。据此,我们可以定义动态加权的启发式评价函数为:其中表示节点n在搜索树中的深度,N表示预期的目标节点在搜索树中的深度;定义二.若算法采用上述的启发式评价函数,且≥,则称算法RAε为算法。若模T满足,这里ε∈(0,1)，属于最佳路径上的且在OPEN表中属于最浅层的任意节点n，仍然有，最后经过推导可以得到：=≥≥≥≥动态加权不能克服指数爆炸问题Martelli已经证明了，在最坏情况下，算法A*的时间复杂度为这里M是图的节点数。使用动态加权技术的本质在于提高搜索效率，但是动态加权技术很难消除指数爆炸现象。定义三.启发式评价函数hT’被称为引导了一个∅(N)的标准化误差，若对于b元树上的所有节点，存在两个固定的正数β和γ和一个正交函数∅(.)，使得,γ>1和<1定理二.若引出∅(N)=N的标准化误差，则当0<<1，<a≤1时，启发式评价函数为引出同样的的标准化误差。这里，得含义如同极限、概率定义中常见的，它与不同。证明过程：令；因为∅(y)=y，故有根据定理成立条件可知，当时，，令=(β+1)a–1，当，时，存在>0，使得：，当a1时，，令，当，时，存在，使得：故定理是成立的。定理二表明，至少存在一个区间，使得动态加权技术无法改变评价函数引出的的标准差。Pearl已经证明了使用动态加权的算法A在类似这样的区间内，动态算法仍呈现最坏情况下的指数爆炸问题，类似，算法，若使用动态加权技术，也不能避免指数爆炸问题。结论启发式搜索算法在人工智能领域应用广泛，文章提到的动态加权启发式搜索算法在某些方面要比A*算法出色，通过动态调整搜索中深度优先与宽度优先的比值,更能提高搜索的效率。但由分析可见，动态加权技术虽然在一定程度上提高了算法的搜索效率，但它也存在缺点，即不能从根本上解决指数爆炸问题。参考文献Pohl,1973.Theavoidanceof(relative)catastrophe,heuristiccompetence,genuinedynamicweightingandcomputationalissuesinheuristicproblemsolving.InProceedingsofIJCAI-73,12-17Thayer,J.T.andRuml,W.2008.FasterthanweightedA*:Anoptimisticapproachtoboundedsuboptimalsearch.InProceedingsofICAPS-2008.Haslum,P.,andGeffner,H.2001.Heuristicplanningwithtimeandresources.InP