欢迎来到工友文库! | 帮助中心 工友共享,造福你我!
工友文库
全部分类
  • 行业文库 >
    行业文库
    行业标准 农林牧渔 能源矿业 电力热力 水利环境 材料技术 地理测绘 建筑工程 机械工程 制造加工 交通物流 网络计算 电气机电 信息通讯 汽车行业 航空航天 船舶工程 光电工程 住宿餐饮 财会金融 房地产业 城建规划 装饰装修 家电维修 电商行业 租赁商务 批发零售 居民服务 教育服务 医药卫生 体育行业 公共管理 图书管理 外语翻译 休闲旅游 文艺传媒 其他行业
  • 商业文档 >
    商业文档
    企业计划 工程管理 广告经营 财务报表 物业管理 质控管理 企业文化 绩效管理 商务礼仪 创业孵化 市场营销 经营企划 销售管理 营销创新 资本运营 招商加盟 合同协议 信息管理 励志材料 人事档案 员工关系 薪酬管理 招聘面试 其它文档
  • 办公文书 >
    办公文书
    统计图表 总结报告 演讲致辞 心得体会 述职报告 工作计划 解决方案 调研报告 事务文书 经验事迹 往来文书 规章制度 申请范文 求职简历 活动策划 会议纪要 党建材料 软件教程 其他文书
  • PPT模板库 >
    PPT模板库
    扁平风格 创意新颖 动画效果 动态模板 简约风格 静态模板 环保绿色 卡通风格 立体风格 欧洲风格 手绘风格 创意黑板 相册风格 星空风格 炫酷科技 中国风格 医疗风格 高端商务 工作常用 总结报告 毕业答辩 节日庆典 公益风格 化妆美容 婚礼策划 餐饮美食 培训课件 融资路演 商业策划 英文模板 党政机关 述职竞聘
  • 小学初中 >
    小学初中
    幼儿教育 小学语文 小学数学 小学英语 初中语文 初中数学 初中英语 初中物理 初中化学 初中地理 初中生物 初中政治 初中历史 思想品德 小学竞赛 初中竞赛 其他学科
  • 高中教育 >
    高中教育
    高中语文 高中数学 高中英语 高中物理 高中化学 高中生物 高中地理 高中政治 高中历史 高考资料 高中竞赛 其他学科
  • 高等教育 >
    高等教育
    基础课 艺术类 哲学类 体育类 水利类 测绘类 法学类 历史学 社会学 心理学 教育学 政治学 统计学 房地产 语言文化 生物科学 医药卫生 天文气象 地理科学 环境科学 系统科学 材料科学 机械仪表 图书档案 土建工程 海洋工程 轻工纺织 工程力学 能源动力 光电工程 电力技术 市政工程 财会金融 工商管理 语言文学 广播影视 公安司法 汽车汽修 交通运输 水产加工 植物生产 森林资源 动物科学 食品加工 餐饮旅游 公共事业 新闻传播学 农林业工程 城镇规划管理 水文与水资源 地矿及资源勘查 航空航天与武器 管理科学与工程 农林业经济管理 机电设备及自动化 计算机与信息科学 大学生竞赛资料
  • 执业资格考试 >
    执业资格考试
    财会类考试 建筑类考试 外贸类考试 外语类考试 医药类考试 管理类考试 公务员类考试 司法法律考试 教师资格考试 计算机类考试 公共服务类考试 其他资格证考试
  • 一线采风 >
    一线采风
    一线新闻 事迹宣传 工友作品
  • 教育视频 >
    教育视频
    幼儿教育视频 小学教育视频 初中教育视频 高中教育视频 大学教育视频 C#自学视频教程 软件视频教程 英语视频教学 其他教学视频
  • 换一换
    首页 工友文库 > 资源分类 > PPTX文档下载
     

    人工智能第三章教学课件.pptx

    • 资源ID:20115       资源大小:526.35KB        全文页数:87页
    • 资源格式: PPTX        下载权限:注册会员/VIP会员    下载费用:0金币 【人民币0元】
    下载资源需要0金币 【人民币0元】
    已注册用户请登录:
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

    人工智能第三章教学课件.pptx

    8/17/2019,1,第三章 产生式系统的搜索策略 回溯策略 图搜索策略无信息的图搜索 启发式的图搜索,8/17/2019,2,,产生式系统的费用,控制费用,规则应用费用,产生式系统费用,8/17/2019,3,,3.1 回溯策略,8/17/2019,4,一、回溯算法BACKTRACK,算法中用到的部分变量、常量、谓词、函数 变量 DATA,RDATA状态变量 RULES, PATH 表变量 常量 NIL 空表 ----LISP语言中的常量,也可用() 谓词 TERMDATA DATA满足结束条件时,为真 DEADENDDATADATA不在解路上,为真(往下到达目标的可能性来定义这个谓词若从 DATA当前状态往下走到达目标的可能性很小时,则放弃这个状态 ) NULLX 表X为空表时,为真 函数 APPRULESDATA 将DATA所有可用规则进行排序所得到的表 FIRSTX 取表X的头 TAILX 取表X的尾 CONSE, X将E加入表X前,8/17/2019,5,BACKTRACK过程,Recursive Procedure BACKTRACK(DATA) 1.if TERM(DATA),return NIL; 2.if DEADEND(DATA),return FAIL; 3.RULES←APPRULES(DATA); 4. LOOPif NULL(RULES),return FAIL; 5. R←FIRST(RULES); 6. RULES←TAIL(RULES); 7. RDATA←R(DATA); 8. PATH←BACKTRACK(RDATA); 9. if PATH=FAIL,go LOOP; 10. return CONS(R,PATH).,8/17/2019,6,带来的问题及解决方案,⑴若DEADEND定义不好,则无限产生新的非终止的状态描述。 (既不成功又不失败的节点) 解决方案设置门槛数,即搜索深度BOUND,当递归调用超过这个深度时return FAIL,引起回溯。 ⑵ 程序中只有DATA和RDATA,回溯过程中将生成的状态都丢弃了,有可能陷入循环,重复地产生一系列非终止状态。 (实质属于情况1) 解决方案 在过程中保存一个状态描述表DATALIST记录从初始状态到当前状态路径上的所有状态----递归变量变成DATALIST,取表头为DATA 。 加比较当产生新状态RDATA时,比较是否为DATALIST中的一个状态(在这个表中),若是,则return FAIL,引起回溯,选择其它的Rule。,8/17/2019,7,四皇后问题4枚皇后放在44的国际象棋棋盘上,如何放置使得它们不能相互俘获。 俘获同行;同列;同对角线,二、回溯策略例四皇后问题,其中a,b满足目标条件, c,d,e为不可能构成满足目标条件的中间状态。,8/17/2019,8,,综合数据库以状态为节点的有向图 状态44矩阵 初始状态 空矩阵 规则Rijif i1时,矩阵中无皇后标志,或4  i 1时,矩阵的i-1行有一个皇后标志,then在矩阵的第i行第j列放一个皇后标记 结束条件TERM为真矩阵中有4个皇后标志,且不能相互俘获 控制策略回溯 DEADENDDATA DATA中存在1对皇后相互俘获,为真 APPRULESRULES Rij排在Rik之前jk,8/17/2019,9,,1,2,4,3,,,,5,,6,7,8,9,,,,,,10,,11,,12,,13,14,,,15,,16,,17,,18,,19,,20,,21,,22,,23,,24,,25,,26,,27,,28,NIL,,,,,,8/17/2019,10,四皇后问题,存在的问题回溯的次数很多,22次回溯。 原因没有关于问题的探索性信息指导规则排序。 解决方法之一在规则排序过程中使用一些探索性信息,减少回溯次数,提高算法效率. 例使用函数 diagi, j来修改APPRULESRULES diagi, j通过单元(i,j)的最长对角线的长度. 修改后的 APPRULESRULES if diag(i,j)<diag(i,k),then Rij排在Rik前. if diag(i,j) diag(i,k),then与以前相同,Rij排在Rik之前jk,8/17/2019,11,课堂练习,请用回溯搜索策略BACKTRACK求解四皇后问题,要求规则排序使用对角函数diagi, j。如果diagi, j<diagi, k,则在排序中把Rij放在Rik的前面;如果diagi, jdiagi, k,jk,则把Rij放在Rik的前面。其中diagi, j定义为通过单元i, j的最长对角线的长度.,8/17/2019,12,三、BACKTRACK算法的修改与补充,Recursive Procedure BACKTRACK(DATA) s1. if TERM(DATA),return NIL; s2.if DEADEND(DATA),return FAIL; s3.RULES←APPRULES(DATA); s4. LOOPif NULL(RULES);return FAIL; s5. R←FIRST(RULES); s6. RULES←TAIL(RULES); s7. RDATA←R(DATA) s8. PATH←BACKTRACK(RDATA); s9. if PATH=FAIL,go LOOP; s10. return CONS(R,PATH),DATA 换成DATALIST,s0 DATA←FIRSTDATALIST; s0’ if MEMBERDATA,TAILDATALIST return FAIL;,s2’ if LENGTHDATALISTBOUND, return FAIL;,s7’ RDATALIST←CONSRDATA,DATALIST); s8 PATH←BACKTRACK1(RDATALIST),8/17/2019,13,两层以上的回溯,,8/17/2019,14,,3.2 图搜索策略,8/17/2019,15,一、相关概念,有向图 GP,A,P点集 A弧集 弧两点间有方向的线。 如果有一条弧从节点ni出发指向nj;则节点nj称为节点ni的子节点,节点ni称为节点nj的父亲节点. 对于产生式系统, 节点用状态描述标记 弧用规则标记 假定图中的每一个节点只有有限个子节点。,8/17/2019,16,,路节点序列ni0, ni1,,nik称为从节点ni0到节点nik的一条长度为k的路径,其中,对于j1,,k,每一个nij都是nij-1的子节点。 如果存在一条从节点ni到节点nj的路径,则节点nj称做是从节点ni出发可达到的,节点nj称做节点ni的后裔,节点ni称做是节点nj的祖先。 解路径 从初始节点到一个满足终止条件节点的路径。 图搜索策略把寻找从初始状态描述到目标描述的规则序列问题转化成寻找有向图的解路径问题.,8/17/2019,17,,有向树每一个节点最多只有一个父亲的有向图. 根节点有向树中没有父节点的节点 叶节点有向树中没有子节点的节点 有向树中节点的深度 1 根节点的深度是0, 2其它节点的深度等于它父节点的深度加1。,8/17/2019,18,,加权有向图(权图) 每条弧线上都有使用费用(正数)的图。 例从节点ni到节点nj的有向孤的费用Cni, nj 路径的费用路径上所有弧费用的和. 两节点间具有最小费用的路径是此两节点间所有弧费用的费用总和最小的一条路。 最佳解路径费用最小的解路径。,8/17/2019,19,,隐含图由部分节点和一组其它节点生成规则所确定的图. 图搜索控制策略的目标从隐含图出发生成一个部分明确的图,使该明确图中含有目标节点. 图搜索非形式定义 假定所有隐含图中有向弧的费用大于某一个小的正数ε 问题求隐含图中初始节点s到目标节点集{ti}中任意成员的一条具有最小费用的解路径。,8/17/2019,20,二、一般的图搜索过程GRAPHSEARCH,OPEN表未扩展的节点 CLOSED表已扩展或正在扩展的节点 G搜索图,动态变化,部分明确的图,8/17/2019,21,,1.G←{s}, OPEN ←(s). 2.CLOSED ←NIL. 3.LOOPIF OPENNIL,THEN FAIL. 4. n ← FIRSTOPEN,OPEN ←TAILOPEN,CONSn, CLOSED . 5. IF TERMn,THEN 成功结束 (解路径可通过追溯G中从n到s的指针获得)。 6. 扩展节点n, 令M{m︱ m是n的子节点,且m不是n的祖先} , G ←G ∪M 7. (设置指针,调整指针)对于mM, 1若mCLOSED, mOPEN, 建立m到n的指针,并CONSm, OPEN. 2amOPEN, 考虑是否修改m的指针. bmCLOSED,考虑是否修改m及在G中后裔的指针。 8. 重排OPEN表中的节点(按某一任意确定的方式或者根据探索信息)。 9. GO LOOP,Procedure GRAPHSEARCH,8/17/2019,22,,Note1算法结束时, OPEN树的叶节点 CLOSED1非叶节点 2被选来扩展但无后裔的叶节点 Note2如果搜索的隐含图是一棵树, 步骤6和步骤7得以简化 step 6扩展节点n, 令M{m︱ m是n的子节点} , G ←G ∪M step 7建立m到n的指针,并CONSm, OPEN. Note3如果搜索的隐含图不是树,则需确定是否需要指针修改。,8/17/2019,23,3.3 无信息的图搜索过程,若在GRAPHSEARCH的步骤8中对OPEN表中节点的排序不使用关于问题的探索性信息,则必须任意规定一种排序方式,所得到的搜索过程叫作无信息的。 一般有两种无信息的图搜索过程深度优先搜索与宽度优先搜索. 在人工智能中,一般说来人们对无信息的过程不感兴趣.,8/17/2019,24,无信息的图搜索过程,深度优先搜索排列OPEN表中的节点时按它们在搜索树中的深度递减排序 。深度最大的节点放在表的前面,深度相等的节点以任意方式排序。 宽度优先搜索在排列OPEN表中节点时按它们在搜索图中的深度递增顺序,深度最小的节点放在表的前面 。 8-数码问题例子,8/17/2019,25,8/17/2019,26,一个简单二叉树的宽度优先搜索过程,在每一个阶段,下一个要扩展的节点由箭头指示出来。,8/17/2019,27,3.4 启发式图搜索过程,无信息的搜索方式需要产生大量的节点才能找到解路径。这些节点都需要在内存中保存起来。由此可见无信息搜索方式所需存储空间是相当大的。而实际上计算机所能提供的存储总是有限的,因此我们必须寻找效率更高的搜索方法。,8/17/2019,28,启发式搜索,启发式信息用于帮助减少搜索量的与问题有关的信息或知识。 启发式信息用在GRAPHSEARCH的步骤8中对OPEN表中的节点进行排序,把最有希望的节点排在最前面,使搜索图沿着有利于获得解的方向扩展。 启发式搜索使用启发信息指导的搜索过程叫做启发式搜索。,8/17/2019,29,,启发信息强,可以降低搜索的工作量,但可能导致找不到最优解; 启发信息弱,一般会导致搜索的工作量加大,极端情况下演变为盲目搜索,但有可能找到最优解。 我们希望,通过引入启发知识,在保证找到最佳解的情况下,尽可能减少搜索范围,提高搜索效率。,8/17/2019,30,估价函数,使用启发信息的一种重要方法是采用估价函数。 估价函数例任意节点与目标节点的距离度量;棋盘上对局势的度量;一个节点处在最佳路径上的概率等等。 估价函数定义在状态空间上的实值函数。 用fn表示节点n的估价函数 1. fn表示从起点到目标,经由节点n最小费用路径上 费用的估计。 (在搜索图中,接近解路径的节点有较低的函数值) 2. 以估价函数f的递增次序排列OPEN表中的节点 估价函数低的排在前; 具有相等函数值的节点以任意次序排序。,8/17/2019,31,例八码难题,估价函数fndnWn 其中 dn节点n在搜索树中的深度 Wn与n对应的状态描述中偏离目标的棋子的个数。 例利用估价函数fndnWn正向搜索八数码难题 初始状态 目标状态,8/17/2019,32,练习,利用估价函数fndnWn反向搜索上例八数码难题。指出反向搜索和正向搜索在什么地方相遇。 左优先、浅层的优先,8/17/2019,33,估价函数的选择对搜索结果起着重要作用,如果估价函数没能识别出真正有希望的节点,则可能延长搜索过程,扩展较多的节点。 如果估价函数过高地估计了所有点的希望值,则也同样导致扩展大量的节点. 例如在八数码问题题例中,如果让fndn,则得到宽度优先搜索。,8/17/2019,34,一些概念,Kni, nj 隐含图中节点ni到nj最小费用路径的实际费用。 若ni到nj无路,则函数Kni, nj 无定义。 h*n设{ti} 是目标节点集合,定义 h*nmini{ Kn, ti } 表示隐含图中从n到目标节点的最小费用路径的费用。 对不能到达目标节点的节点n,h*n无定义。 最佳解路径从n到目标节点的任何费用为h*n的路径。 g*n g*nKs,n 表示隐含图中从初始节点s到n的最佳解路径的费用。 f*nf*ng*nh*n 表示隐含图中,通过节点n,从s到目标节点的最佳解路径的费用。 当n是从初始节点到目标节点t的最佳解路径上的节点时, f*n f*sf*th*s。,8/17/2019,35,A算法和A*算法,A算法 使用估价函数fngnhn 排列OPEN表中节点顺序的 GRAPHSEARCH算法。 其中, gn对g*n的一个估计 是当前的搜索图G中s到n的最优路径费用 gn≥g*n hn对h*n的估计,称为启发函数。 Note若hn0,gnd,则 fnd,为宽度优先。 A*算法对任何节点n都有hn≤h*n的A算法。,8/17/2019,36,3.5 A*算法的可采纳性,定义如果一个搜索算法对于任何具有解路径的图都能找到一条最佳路径,则称此算法为可采纳的。 可以证明A*算法是可采纳的(如果解路径存在,A*一定由于找到最佳解路径而结束),8/17/2019,37,定理1 GRAPHSEARCH对有限图必然终止。 证明GRAPHSEARCH算法将在第3步将OPEN表中的节点用光而结束;或在第5步,找到目标节点而结束。 在算法的每一次循环中,都要从OPEN表中删除一个节点,若是目标节点,则再第5步算法结束,否则将该节点的某些后继加到OPEN表中。 对有限图来说, OPEN表中节点个数是有限的,因此,若算法不在第5步成功终止,则一定在第3步因OPEN表中的所有节点全部取光而终止。,A*算法的可采纳性,8/17/2019,38,引理1 若A*不终止,OPEN表中节点的估价函数值可以 无限变大。 证明设n是OPEN表中的任意节点,d*n是隐含图中从s到n的最短路的长度,因为图中每条弧的费用都大于某一个小的正数e, 于是有 g*n≥d*n e, 又gn≥g*n≥d*n e , fn gnhn ,且hn ≥0 因此 fn≥ gn≥ d*n e 若A*不终止,OPEN表中节点的d*值会不断增大,因此f值也会不断增大。,A*算法的可采纳性,8/17/2019,39,定理2 若存在s到目标的解路径,则算法A*终止前的任何 时刻,OPEN表中总存在一个节点n’, n’在从s到 目标的最佳解路径上,且满足fn’ ≤f*s 证明设Pn0,n1,,nk是一条最佳解路径,其中, nk是目标点,n0s. 在A*结束之前,从左向右扫描序列P,令n’是P中第一个在OPEN表中的节点。 这样的n’是存在的因为开始n0在OPEN表中,算法结束前,若扩展ni,ni≠ nk,则ni1在OPEN表中。,A*算法的可采纳性,8/17/2019,40,因n’的所有祖先都在CLOSED表中,所以n0,n1,, n’是已被搜索出的从s到n’的最佳路,故 gn’ g*n’ 又由A*算法定义知hn’≤h*n’, 故 fn’ gn’ hn’≤g*n’h*n’ f*n’ 而对最佳路上任意一点n’,有f*n’ f*s 因此,fn’≤f*s 证毕。,A*算法的可采纳性定理2,8/17/2019,41,定理3 若存在解路径,则A*算法必终止。 证明反证。若算法A*不终止, 由引理1知,OPEN表中任意节点的f值随着算法A*的运行可以任意增大。 由定理2知,算法A*终止前的任何时刻,OPEN表中总存在一个节点n’, 使得fn’ ≤f*s 。 矛盾。,A*算法的可采纳性,8/17/2019,42,推论 OPEN表中的任一满足fnf*s的 节点n,最终将被算法A*选作扩展节点。 证明 若A*算法停在第3步,则OPEN表中的任一节点都被扩展; 若A*算法停在第5步,即找到目标t而结束,下面用反证法。假设存在OPEN表中满足fn f*n的节点n,而未选n为扩展点,因对目标t,有ft ≥ f*s,而fn f*s,故fn ft,因此A*一定选n扩展而不选t,与A*结束在点t矛盾。 证毕。,A*算法的可采纳性,8/17/2019,43,定理4 算法A*是可采纳的。 (若解路径存在,A*一定找到最佳解路径而终止). 证明由定理3知,算法A*必终止。 由定理2知,算法A*终止前的任何时刻,OPEN表中总存在一个节点n’, 使得fn’ ≤f*s,故算法A*不会终止在第3步,因此必终止在第5步,因找到一个目标节点而结束。 设t是算法A*找到的目标点, (下面用反证法证明t 在最佳解路上),A*算法的可采纳性,8/17/2019,44,若t 不在最佳解路径上,则 ft gthtgt >f*s 由定理2,A*算法终止前,OPEN表中总有一点n’,使 fn’≤f*s,因此 fn’ft;在OPEN表的排序中,节点n’应排在节点t的前面。 因此,算法A*算法终止前应选n’去扩展,而不会选t,与算法A*终止于t矛盾。 故原假设不对,s到t是最佳路。 证毕,A*算法的可采纳性定理4,8/17/2019,45,定理5 算法A*选择的任意扩展点n都有fn≤f*s 证明 若n是目标点,由定理4,fnf*s 。 若n不是目标点,由定理2 ,A*算法终止前,OPEN表中总有点n’,使 fn’≤f*s。 若nn’,则fn fn’≤f*s。 否则,根据OPEN表按f值递增排序,此时,算法A*选择n而没有选择n’,必有 fn≤ fn’,故fn ≤f*s 证毕。,A*算法的可采纳性,8/17/2019,46,定义 设A1和A2是两个 A*算法,分别使用如下两个估价函数 f1ng1nh1n f2ng2nh2n 其中,h1n和h2n是h*n的两个下界.若对于所有的非目标节点n,都有h2n>h1n,则称算法A2比算法A1有较多的信息.,3.6 A*算法的比较,8/17/2019,47,讨论启发函数的启发能力在于它所具有的启发性信息。 1. 当hn≡0时,反映了启发函数完全没有启发信息,要扩展较多的节点. 2. 在具有可采纳性的前提下, 0≤h≤h*,h*定出了h的上界,当h越接近h*时,它的启发能力就越大.,A*算法的比较,8/17/2019,48,例 八码难题的A*算法的比较. 图3.7的估价函数f1ndn,h1n≡0,采用宽度优先搜索 ; 图3.8的估价函数f2ndnwn,h2n≡wn. 对于所有非目标节点,有h2n>h1n,因此,图3.7所用算法不但比图3.8所用算法有较多的信息,而且扩展的节点数要少。,A*算法的比较,8/17/2019,49,定理6 如果A1和A2是两个A*算法,算法A2比A1有较多的信息,且它们搜索同一个隐含图。若该图存在解路径,当这两个算法终止时,A2所扩展的每一节点也必被A1所扩展,即 A2扩展的节点数≤A1扩展的节点数 证明设n是A2所扩展的任一节点, 往证n也被A1扩展。 用dn记n在A2搜索树中的深度,对dn使用数学归纳法。,A*算法的比较 定理6,8/17/2019,50,当dn0时,则n=s。命题显然成立若s不是目标节点,这两个算法都必将扩展s ;若s是目标节点,这两个算法都不必扩展s. 假设dn ≤k时成立,即A2搜索树中深度≤k的所有节点都被算法A1扩展. 设dn =k+1,往证A2扩展的深度为k1的节点也被A1扩展。 因节点n被A2扩展,由于n的祖先点被A2扩展,根据归纳假设,节点n的在A2搜索树中的所有祖先都被算法A1所扩展.,A*算法的比较定理6,8/17/2019,51,因此,节点n在A1的搜索树中,且在A1的搜索树中存在一条从s到n的路。由于A2搜索树中点n之前的树是A1搜索中点n之前的树的子树,因此有 g1n ≤ g2n 又因为h1n h2n,所以f1n f2n. 由于n被A2扩展,由定理5知 f2n ≤ f*s 故f1n f2n ≤ f*s . 由推论知,点n必被A1选去扩展,归纳完成。,A*算法的比较 定理6,8/17/2019,52,3.7 单调限制,GRAPHSEARCH每当扩展一个节点n时,n的某些后继可能已经在OPEN表中或CLOSED表中,因此算法需要调整这些节点以及它们的后裔的指针。这种调整涉及到通向一个节点的路径的费用的比较,增加了程序的计算费用.测试一个节点是否以前曾经产生过的计算费用更高.如果我们对启发函数增加某种限制,使得算法A*选出一个节点扩展时,就已经发现了通向这个节点的最佳路径,这样对节点是否已经产生过的测试和指针的调整都不必进行了,这种限制当然是提高算法A*效率的有效方法.,8/17/2019,53,定义 如果启发函数h对任何节点ni和nj,只要nj是ni的后继,都有 hni-hnj≤cni, nj ht0 (t是目标节点) 则称启发函数h满足单调限制.,3.7 单调限制,8/17/2019,54,定理7 如果A*算法的启发函数h满足单调限制,则当算法A*选择节点n扩展时,就已经发现了通向节点n的最佳路径,即gng*n. 证明设n是算法A*选出扩展的任一节点。 若ns,则gng*n0,算法A*已发现通向s的最佳路径. 若n≠s,设序列Psn0,n1,,nkn是隐含图中从s到n的一条最佳路径不知道是否在A*的搜索树中。,单调限制的性质定理7,8/17/2019,55,若P在当前树中,则得证。 否则,当算法A*选择n进行扩展时 设P中从n0开始,串n0,,nj都在CLOSED表中,即nj是P中从左向右CLOSED表中的最后一个节点,且 nj ≠n. 此时,nj的后继节点nj1在OPEN表中.,单调限制的性质定理7,8/17/2019,56,由已知hn满足单调限制,对任意i0,,k-1,有 g*nihni ≤g*nicni, ni1 hni1 而ni和ni1都在最佳路径上,故 g*ni1 g*nicni, ni1 因此 g*nihni ≤g*ni1hni1,单调限制的性质定理7,8/17/2019,57,因为j≤k-1,所以jk 利用传递性,我们得到 g*nj1hnj1 ≤ g*nj2hnj2 ≤ . ≤ g*nkhnk 由P是从s到nk的最佳路, n0,n1,,nj1是最佳路,且已被搜索出,所以gnj1 g*nj1 所以 fnj1 ≤g*nkhnk= g*nhn,单调限制的性质定理7,8/17/2019,58,即,fnj1 ≤g*nhn 因A*算法选择n扩展时,OPEN表中有nj1,故fn ≤ fnj1 。 因此, g nhnfn ≤ g*nhn 所以gn ≤ g*n. 再由g*n ≤ gn ,知gn g*n 。 证毕。,单调限制的性质定理7,8/17/2019,59,定理8 如果A*算法启发式函数h满足单调限制, 则A*所扩展的节点序列的估价函数值是非递减的. 证明设ni和ni1是A*扩展的节点序列中任意二相邻节点, ni在前 。 若扩展ni时, ni1在OPEN表中,显然 fni ≤ fni1,单调限制的性质定理8,8/17/2019,60,若扩展ni时, ni1不在OPEN表中,而A*扩展完ni后,立刻扩展ni1 ,故一定是ni1为ni的后继,继而加到OPEN表中。于是,扩展ni1时有 fni1gni1hni1 g*ni1 hni1 由定理7) g*nicni,ni1hni1 gnicni,ni1hni1 由定理7) 由单调性, cni,ni1hni1 ≥ hni 所以 fni1 ≥ gnihni fni 证毕。,单调限制的性质定理8,8/17/2019,61,A*算法的小结,1. A*算法搜索隐含图时,有解必停,且必停在最佳解路上; 2. 在满足h n ≤h*n的前提下,启发函数越大,其所包含的启发信息越多,所扩展的节点越少; 3. 若启发函数满足单调限制,则每走一步都在最佳解路上,且估价函数不减,简化了算法的第7步(调整指针).,8/17/2019,62,3.8 算法A的启发能力,定义 设A1和A2是两个启发式算法,它们分别使用估价函数f1和f2,如果在寻找解路径的过程中,A1所用的计算费用比A2少,则称A1比A2有较强的启发能力,也可以称估价函数f1比f2有较强的启发能力.,8/17/2019,63,算法A的启发能力,影响算法A启发能力的三个重要因素 (1)算法A所找到的解路径的费用。 (2)算法A在寻找这条解路径的过程中所需要 扩展的节点数。 (3)计算启发函数所需要的计算量。,8/17/2019,64,hn ≤ h*n 保证了A*的可采纳性,可采纳性可能意味着算法需要扩展更多的节点,使总的费用提高。 Note1若能保证高效(增强算法的启发能力), 则牺牲可采纳性是可取的。 例八码难题 a hnWn不在位数码的个数 问题每个数码离开目标的距离不一致, 说明不了复位困难程度。,算法A的启发能力,8/17/2019,65,,b hnPn每个数码离“家”距离的和。 问题不能说明离“家”近,但离空格远的数码复 位的难易。,初始状态,目标状态,8/17/2019,66,,初始状态,目标状态,下面给出该八数码问题取不同启发函数,应用A*算法求得最佳解时所扩展和生成的节点数。,,8/17/2019,67,,8/17/2019,68,,c hnPn3Sn Pn每个数码离“家”距离的和。 Sn记分函数,8/17/2019,69,,对于中心方格,若有数码,记1分,否则记0分。 对非中心的外围上的数码,沿顺时针方向依次检查每个数码若此数码与其后面的数码与目标中顺序不同(若此数码后面的数码不是它在目标状态的后继),则记2分,否则记0分。 Pn1+l+ 2+l+1+3+0+2 11 Sn2+2+2+2+2+2+2+l15 所以hn Pn+ 3Sn11+31556,八数码难题的初始状态与目标状态,8/17/2019,70,8/17/2019,71,该例子给了一个不满足A*条件的h函数。从图上可以看出,启发效果非常的好,对于需要18步才能完成的8数码问题,几乎没有扩展什么多余的节点,就找到了解路径。 这里所用的方法一是组合两个不同的启发函数;二是采取加权的方法(这里对Sn加权为3),来加大Sn的作用。 这样得到的启发函数由于不满足A*条件,因此不能保证找到问题的最佳解,但往往可以提高搜索效率,加快找到解的速度。由于这样的启发函数还是反映了被评估节点到目标节点路径耗散值的多少,算法虽然不能一定找到最优解,但一般来说,找到的也是一个可以被接受的满意解。很多情况下,满意解就足够了,最优解并没有什么特殊的意义,二者可能相差很少,但却使得问题简单了很多。值得指出的是,该例子所得到的解,刚好是一个最优解。,,8/17/2019,72,Note2可控制g和h在搜索中所起的作用 有时,把估价函数写成fgwhw 为正数的形式 w很小时,强调宽度优先 w很大时,强调启发分量 经验表明,让w的值与搜索树中节点的深度成相反方向 变化时,搜索效率往往会有所提高.在深度较小时,搜 索主要依靠启发部分,随着深度的增加,宽度优先部分 的作用逐渐增大,以保证最终能找到一条解路径.一般w 与深度成反比。,算法A的启发能力,8/17/2019,73,正向搜索从初始节点到目标的搜索 反向搜索从目标节点到初始节点的搜索 双向搜索正向和反向搜索的结合 搜索需要产生的节点数 宽度优先搜索,使用双向搜索要优越许多 对于启发式搜索,评价单向搜索和双向搜索的优劣 很复杂,双向搜索使用不当可能是单向搜索量的二倍.,3.9 有关算法,Kaindl, Hermann and Gerhard Kainz. Bidirectional Heuristic Search Reconsidered, Journal of Artificial Intelligence Research, 7283-317, 1997,8/17/2019,74,分阶段搜索为了完成搜索过程,可对搜索图进行修剪,释放出一部分存储空间。 把OPEN表具有最小f值的一些节点打上标记,记住这些节点和通向这些点的最佳路径,删去搜索图其余部分。 然后恢复节点和路径,重新开始搜索。 分阶段搜索并不能保证找到一条解路径。,3.9 有关算法,Kaindl, Hermann and Gerhard Kainz. Bidirectional Heuristic Search Reconsidered, Journal of Artificial Intelligence Research, 7283-317, 1997,8/17/2019,75,迭代加深A*搜索依赖一系列逐渐扩展的有限制的深度优先搜索。,3.9 有关算法,Korf, Richard E. Depth-First Interative-Deepenning An Optimal Asmissible Tree Search, Artificial Intelligence, 2797-109, 1985,8/17/2019,76,算法技术手册影印版 作 者海涅曼 波利切 塞克欧 出版社 东南大学出版社 2009,第7章 人工智能中的寻路,8/17/2019,77,搜索方法的启发能力主要依赖于给定问题的具体因素。 判断启发能力的强弱主要是凭经验而不是凭计算。 某些实现上的度量是可计算的。这些度量不能完全决定一个算法的启发能力,在比较各种搜索算法的优劣时是很有用的。,3.10 启发能力的度量,8/17/2019,78,渗透度是对一个搜索算法的搜索性能的度量,表 示搜索集中指向某个目标的程度,而不是在无关 的方向上徘徊。 定义为 P L / T 其中,L是算法发现的解路径的长度, T是算法在寻找这条解路径期间所产生的节点数(不包括初始节点,包括目标节点),启发能力的度量渗透度,8/17/2019,79,例 图3.9的八数码问题,L18,T43, 渗透度P L / T = 18 / 43 0.42 若一个算法每次选取的节点都在解路径上,则 L= T ,P=1; 一般搜索的渗透度P1 ; 无信息的搜索P1; 渗透度大,所产生的搜索树向纵深发展; 渗透度小,所产生的搜索树沿水平方向发展。,启发能力的度量渗透度,8/17/2019,80,搜索算法的渗透度取决于问题的难度和算法的效率。 当最佳解路短时,可能有较高的渗透度; 当最佳解路长时,算法产生节点的数目将以更快的速度增加,可能有较低的渗透度。 渗透度有时并不能很好地反映搜索向目标方向发展的集中程度。,启发能力的度量渗透度,8/17/2019,81,启发能力的度量有效分枝系数,有效分枝系数就是一棵搜索树的平均分枝数. 设搜索树的深度是L,算法所产生的总节点数为T,有效分枝系数是B,则有 B+B2十+BLT 或 B(BL-1)/(B-1)T,8/17/2019,82,启发能力的度量有效分枝系数,图3.12给出了不同L值B与T的关系 当L18,T43时, 搜索树的有效分枝系数B大约为 1.08.,8/17/2019,83,启发能力的度量有效分枝系数,有效分枝系数与路径的长度无关,可以利用这一 事实预测不同深度的搜索所需产生的节点个数。 例 若用估价函数fgp3s去解决一个复杂的八数码问题. 设解路径长度L30, 有效分枝系数 B1.08. 则由图3.12知,所需产生节点的个数大约为l20,8/17/2019,84,启发能力的度量有效分枝系数,图3.13给出了在不同的B值下渗透度随路径长度的变化曲线. 由图中可以看出,同样的有效分枝系数,渗透度随路径的深度下降.,8/17/2019,85,本章小结,回溯算法BACKTRACK 图搜索算法GRAPHSEARCH 启发式图搜索过程 A*算法的可采纳性,8/17/2019,86,小结,A*算法的比较 单调限制及性质 算法A的启发能力 启发能力的度量,8/17/2019,87,度量问题求解的性能,完备性当问题有解时,这个算法是否能保证找到一个解,空间复杂度执行搜索的过程中需要多少内存,时间复杂度找到一个解需要花费多少长时间,最优性该搜索策略是否能找到最优解,

    注意事项

    本文(人工智能第三章教学课件.pptx)为本站会员(小旋风)主动上传,工友文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知工友文库(发送邮件至gydoc@qq.com或直接QQ联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    copyright@ 2019-2022 工友文库网站版权所有
    经营许可证编号:鲁ICP备19032292号-1


    1
    收起
    展开