人工智能读书报告-.doc

人工智能读书报告-.doc:..2013年秋季学期研究生课程考核(读书报告、研究报告)考核科目:人工智能院学与技术学生所在院(系):计算机学学生所在学科:计算机科学生姓名:学号:学生类别:学术考核结果阅卷人人工智能读书报告基干动态加权的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的解的实际耗散。常用的启发算法有:蚁群算法,遗传算法、模拟退火算法等。GridLifeFour-way35%ObstaclesProblemSizeGreedysearchondoutperformssearchonh90,000-,其主要目的是调整搜索中深度优先与宽度优先的比值,以提高搜索效率。通常有两种加权技术,即常数加权与动态加权技术。由于在常数加权中,同样的加权量毫无区别地施用在每一个节点上,加权的作用取决于各单一节点。而在动态加权中,则会动态地对不同层上的节点施以不冋的加权量。故一般地,采用动态加权技术的启发式搜索效率要比静态(即常数)加权好。£可采纳的,如果该算法总能找到一条求解路径,其耗散值至少为⑴。这里A*⑴表示从初始节点S出发至目标节点的最佳路径的耗散值,se(o,i)。根据加权技术的基木思想,启发式评价函数的动态加权应达到这样的效果:在搜索树的浅层,搜索应呈现深度优先搜索的特性;而随着搜索树的层次越来越深,应逐步呈现出宽度优先搜索的特性。据此,我们可以定义动态加权的启发式评价函数>9:fT\n)=T(g/(/7),£•(1+J(/7)/N).hr(n))其中6/⑻表示节点n在搜索树屮的深度,N表示预期的目标节点在搜索树中的深度;\且则称算法RAe为算法/M/。若模T满足T(,eb)=(a,b),这里£6(0,1),属于最佳路径上的且在OPEN表中属•丁•最浅层的任意节点n,仍然有g/(n)=g/(zi),最后经过推导可以得到://⑻=T(g/("),r•(1+