您所在位置：网站首页 > 办公文档 > PPT模板库 > PPT素材/模板湖南大学人工智能幻灯片3-2

湖南大学人工智能幻灯片3-2

27页

卖家[上传人]：F****n

文档编号：88158277

上传时间：2019-04-20

文档格式：PPTX

文档大小：819.11KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

25 金贝

/ 27 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第三章 PartII 有信息的搜索策略,内容提要,最佳优先搜索贪婪最佳优先搜索 A* 搜索启发式函数松弛问题,回顾：树搜索,一种搜索策略实际上就是根据树结点扩张的顺序来决定的,最佳优先搜索,基本思路：通过对每一个结点设置一个评价函数f(n),找到一个代价最低的未扩散的结点实现：根据结点的评价函数值从低到高在队列中对结点进行排序大多数评价函数由启发函数h构成 h(n):结点到目标结点的最小代价路径的代价估计值,最佳优先搜索,最佳优先搜索 vs.一致代价搜索？代价函数的定义不同算法实例贪婪最佳优先搜索 A*树,Romania问题,贪婪最佳优先搜索,评价函数f(n)=h(n) 从结点n到目标结点的代价估测值罗马尼亚问题：贪婪最佳优先搜索首先扩展与目标结点估测距离最近的结点罗马尼亚问题中使用直线距离为估测距离,贪婪最佳优先搜索,贪婪最佳优先搜索,完备性？最优性？时间复杂度：O(bm) 空间复杂度: O(bm),A* 搜索,评价函数 f(n) = g(n) + h(n) g(n)=到达结点n已经花费的代价 h(n)=结点n到目标节点的评估代价 f(n)=通过结点n到

2、达目标结点的总评估代价,A* 搜索,A* 搜索,可采纳的启发函数,启发函数h(n)是可采纳的条件：如果对于每个结点n, h(n)h*(n)，其中h*(n) 是到达目标结点的真实代价可采纳启发函数绝不会高估到达目标结点的代价，因此它是最优的,A*算法的最优化证明,定理：如果启发函数h(n)是可采纳的，那么A*使用树搜索是最优的证明：假定存在一个局部最优目标G2和一个全局最优目标G,设n是一个未扩散的结点且n在到达G的最短路径上，n,G2都位于算法的fringe队列之中如下图所示,A*算法的最优化证明,一致性启发,一个启发函数是一致的条件：对于任意一个结点n，以及n的行为a产生的后继结点n,满足如下公式： h(n) c(n,a,n) + h(n) 如果h(n)是一致的，我们得到,A*算法的最优化证明,定理：如果h(n)是一致的，A*使用图搜索是最优的证明：A*根据f值从小到大扩展结点;A*选择扩散结点n时，就已经找到了达到结点n的最优路径,A*算法的属性, Environment: Patient, hospital, staff Actuators: Screen displa

3、y (questions, tests, diagnoses, treatments, referrals) Sensors: Keyboard (entry of symptoms, findings, patients answers),完备性每步的代价都大于某个常数e，并且分支数b是有限的最优性时间复杂度O(b) 空间复杂度O(b),启发式函数,19,例子：八数码问题平均解的深度？ 22 平均分支因数？ 3,启发式函数,20,例子：八数码问题 h1(n):不在位的棋子数 h2(n):所有棋子到其目标位置的距离和 h1(n)=8 , h2(n):=3+1+2+2+2+3+3+2 = 18,启发式搜索性能分析,21,有效分支因子：对于某一问题，如果A*算法生成的总结点数为N,解的深度为d,那么b*就是深度为d的标准搜索树为了能够包括N+1个结点所必需的分支因子 N+1=1+b*+(b*)2+(b*)d 有效分支因子越小，算法性能越好,启发式搜索性能分析,22,优势,23,对于所有的结点n, h1(n)=h2(n) (两个函数都是可采纳的)，我们说h2(n)比h1(n)有优势。典型的搜索代价(平均结点扩展数)： d=12 IDS = 3,644,035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes,松弛问题,减少了行动限制的问题称为松弛问题。松弛问题增加了状态空间的边原有问题的任一最优解同样也是松弛问题的最优解，但松弛问题可能存在更好的解。,松弛问题,八数码问题行动描述棋子可以从方格A移动到方格B如果A与B水平或者垂直相邻并且B是空的三个松弛问题：去掉条件B的空的： h2将给出最短解的确切步数去掉条件AB相邻上述两者都去掉： h1将给出最短解的确切步数,总结,最佳优先搜索贪婪最佳优先搜索 A* 搜索启发式函数松弛问题,Qa？,

《湖南大学人工智能幻灯片3-2》由会员F****n分享，可在线阅读，更多相关《湖南大学人工智能幻灯片3-2》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源