南邮自动化人工智能3确定性推理.pptx
《南邮自动化人工智能3确定性推理.pptx》由会员分享,可在线阅读,更多相关《南邮自动化人工智能3确定性推理.pptx(50页珍藏版)》请在咨信网上搜索。
1、3.1 图搜索策略图搜索策略3.2 盲目搜索盲目搜索3.3 启发式搜索启发式搜索3.4 消解原理消解原理3.5 规则演绎系统规则演绎系统1第三章第三章 搜索推理技术搜索推理技术3.6 产生式系统产生式系统3.7非单调推理非单调推理3.8小结小结问题问题:知识表示有那些方法?知识表示的目的是:知识表示有那些方法?知识表示的目的是什么?构建智能系统的关键是什么?什么?构建智能系统的关键是什么?3.1 图搜索策略图搜索策略 思考:状态空间法的基本特点?基本推理方法?其思考:状态空间法的基本特点?基本推理方法?其求解结果是什么?简单回顾实例:猴子与香蕉。求解结果是什么?简单回顾实例:猴子与香蕉。2用一
2、个四元表列用一个四元表列(W,x,Y,z)表示这个问题状态表示这个问题状态W W 猴子的水平位置猴子的水平位置x x 当猴子在箱子顶上时取当猴子在箱子顶上时取 x=1x=1;否则取;否则取 x=0 x=0 Y Y 箱子的水平位置箱子的水平位置z z 当猴子摘到香蕉时取当猴子摘到香蕉时取 z=1z=1;否则取;否则取 z=0z=0算符:算符:Goto(U),),(W,0,Y,z)goto(U)(U,0,Y,z)Pushbox(V),),(W,0,W,z)pushbox(V)(V,0,V,z)Climbbox,(W,0,W,z)climbbox (W,1,W,z)Grasp,(c,1,c,0)gr
3、asp (c,1,c,1)33.1 图搜索策略4(b,1,b,0)(U,0,b,0)(V,0,V,0)(c,1,c,0)(U,0,V,0)(c,1,c,1)(a,0,b,0)U=b,climbbox猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图提问:人工搜索求解的解答?提问:人工搜索求解的解答?目标状态目标状态goto(U)goto(U)goto(U)U=b,pushbox(V)pushbox(V)goto(U)Vc,climbboxV=c,climbbox3.1 图搜索策略5猴子和香蕉问题自动演示:猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!3.1 图搜索策略思考:
4、计算机的搜索策略?思考:计算机的搜索策略?图搜索控制策略图搜索控制策略:一种在图中寻找路径的方法。一种在图中寻找路径的方法。图中每个节点对应一个状态图中每个节点对应一个状态;每条连线对应一个操作符。每条连线对应一个操作符。图搜索过程图搜索过程(GraphSearchGraphSearch)63.1 图搜索策略7开始开始把把S放入放入OPEN表表OPEN表为空表?表为空表?把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗?为目标节点吗?把把n的后继节点放入的后继节点放入OPEN表的表的末端,提供返回节点末端,提供返回节点n的指针的指针修改指针方向修改指针方向重
5、排重排OPEN表表失败失败成功成功图图3.1 图搜索过程框图图搜索过程框图是是是是否否否否3.1 图搜索策略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPEN CLOSED(1)(2)宽度优先图搜索的一般过程如下:图搜索的一般过程如下:1)建立一个只含有起始节点)建立一个只含有起始节点S的搜索图的搜索图G,把,把S放到一放到一个叫做个叫做OPEN 的的未扩展节点表未扩展节点表中。中。2)建立一个叫做)建立一个叫做CLOSED的的已扩展节点已扩展节点表,其初始为表,其初始为空表空表.3)LOOP:若:若OPEN表是空表,则失败退出。表是空表,则失败退出。4)选择)选择OPEN表上的第
6、一个节点,把它从表上的第一个节点,把它从OPEN表移表移出并放进出并放进CLOSED表中。称此节点为节点表中。称此节点为节点n5)若)若n为一目标节点,则有解并成功退出,此解是追为一目标节点,则有解并成功退出,此解是追踪图踪图G中沿着指针从中沿着指针从n到到S这条路径这条路径而得到的而得到的(指针将在指针将在第第7步中设置步中设置)。83.1 图搜索策略6)扩展节点)扩展节点n,同时生成不是,同时生成不是n的祖先的那些后继节点的的祖先的那些后继节点的集合集合M。把。把M的这些成员作为的这些成员作为n的后继节点添入图的后继节点添入图G中。中。7)对那些未曾在)对那些未曾在G中出现过的中出现过的M
7、成员设置一个通向成员设置一个通向n的指的指针。把针。把M的这些成员加进的这些成员加进OPEN表。对已经在表。对已经在OPEN或或CLOSED表上的每一个表上的每一个M成员,确定是否需更改通到成员,确定是否需更改通到n的指的指针方向。对已在针方向。对已在CLOSED表上的每个表上的每个M成员,确定是否需要成员,确定是否需要更改图更改图G中通向它的每个后裔节点的指针方向。中通向它的每个后裔节点的指针方向。8)按某一任意方式或按某个探试值,重排)按某一任意方式或按某个探试值,重排OPEN表。表。9)GO LOOP。93.1 图搜索策略图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子图。图
8、搜索的结果:1,一个完整的搜索图G。2一个解路径,用指针表示的解路径。Procedure Graph Search1 G=G0(G0=s),open=(s)/s:初始状态2 closed=()3Loop:if open=()then exit(fall)4 nfirst(open)remove(n,open),add(n,closed)5 if goal(n)then exit(success)6mj expand(n),/mj不含n的先辈节点7 openadd(open,mj)/mj不在open,closed中2024/9/18 周三10标记mj每个到n节点指针确定是否需要修改已在open,
9、closed中的每个节点到n的指针确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8 按照某种方式排列open表中的节点,go loop2024/9/18 周三112024/9/18 周三122024/9/18 周三13思考:思考:(1)结果路径的形成中,为什么其节点顺序是明确的?)结果路径的形成中,为什么其节点顺序是明确的?(2)OPEN表中的节点具有什么特点?表中的节点具有什么特点?(3)CLOSED表中的节点具有什么特点?表中的节点具有什么特点?(4)对)对OPEN表节点的排序有何意义?表节点的排序有何意义?提出:盲目搜索与启发式搜索。提出:盲目搜索与启发式搜索。143
10、.1 3.1 图搜索策略图搜索策略3.2 3.2 盲目搜索盲目搜索 盲目搜索又叫做盲目搜索又叫做无信息搜索无信息搜索,一般只适用于求解比较,一般只适用于求解比较简单的问题。简单的问题。特点:不需重排特点:不需重排OPENOPEN表;表;种类:宽度优先、深度优先、等代价搜索等。种类:宽度优先、深度优先、等代价搜索等。153.2.1 3.2.1 宽度优先搜索(宽度优先搜索(Breadth-Breadth-firstfirst)v 定义:定义:以接近起始节点的程度逐层扩展节点的搜索方法。以接近起始节点的程度逐层扩展节点的搜索方法。v 特点:特点:一种高代价搜索,但若有解存在,则必能找到它。一种高代价
11、搜索,但若有解存在,则必能找到它。16SLOMFPQNFFF宽度优先搜索示意图1)把起始节点放到)把起始节点放到OPEN表中表中(如果该起始节点为一目标节点,如果该起始节点为一目标节点,则求得一个解答则求得一个解答)。2)如果)如果OPEN是个空表,则没有解,失败退出;否则继续。是个空表,则没有解,失败退出;否则继续。3)把第一个节点)把第一个节点(节点节点n)从从OPEN表移出,并把它放入表移出,并把它放入CLOSED的的扩展节点表中。扩展节点表中。4)扩展节点)扩展节点n。如果没有后继节点,则转向上述第。如果没有后继节点,则转向上述第(2)步。步。5)把)把n的所有后继节点放到的所有后继节
12、点放到OPEN表的末端,并提供从这些后表的末端,并提供从这些后继节点回到继节点回到n的指针。的指针。6)如果)如果n的任一个后继节点是个目标节点,则找到一个解答,的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第成功退出;否则转向第(2)步。步。17宽度优先搜索算法:宽度优先搜索算法:3.2 盲目搜索18开始开始把把S放入放入OPEN表表OPEN表为空表?表为空表?把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点?为目标节点?扩展扩展n,把,把n的后继节点放入的后继节点放入OPEN表的表的末末端,提供返回节点端,提供返
13、回节点n的指针的指针失败失败成功成功图图3.2 宽度优先算法框图宽度优先算法框图是是否否是是否否3.2 盲目搜索思考:与原始算法比较异同,宽度优先的体现?思考:与原始算法比较异同,宽度优先的体现?2024/9/18 周三19宽度优先算法Procedrue breadth-First-Search1 G=G0(G0=s),open=(s),closed=()/s:初始状态2 Loop:if open=()then exit(fall)3 nfirst(open)4 if goal(n)then exit(success)5remove(n,open),add(n,closed)6mj expan
14、d(n),/mj不含n的先辈节点7 openadd(open,mj)/mj不在open,closed中2024/9/18 周三20 标记每个到n节点指针,按照节点深度递增顺序排列open中的节点 8 go loop 理论上可以利用宽度优先搜索能够找到解,如果问题有解的话。讨论:宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息,所以称为无信息搜索策略。2024/9/18 周三21:宽度优先例题:由一张桌子T、三个积木A、B、C组成一个积木世界,初始状态是A在B上,B在桌子上,C在桌子上;目标状态是:A、B、C依次从上到下排列在桌子上。如图2024/9/18 周三22解:1)状
15、态描述(P1,P2,P3)表示按A、B、C顺序依次分别在P1,P2,P3上其中Pi是积木或者桌子。初始状态时(B、T、T),目标状态 可以表示(B、C、T)2)定义操作:move(x,y)表示将积木x移到Y上 ;约束条件:a X顶部必须是空的 b 如果Y是积木,Y的顶部必须是空的 c 同一种状态出现不得多于一次。2024/9/18 周三231)解题过程 2)open表和closed表3)节点样子画出整个图G 和解路径4)程序何时结束 5)改用深度优先如何?例子例子八数码难题(八数码难题(8-puzzle problem)241238456712384567(目标状态)(目标状态)(初始状态(初
16、始状态)规定:规定:将牌移入空格的顺序为:从空格左边将牌移入空格的顺序为:从空格左边开始顺时针旋转。不许斜向移动,也不返回开始顺时针旋转。不许斜向移动,也不返回先辈节点。从图可见,要扩展先辈节点。从图可见,要扩展2626个节点,共个节点,共生成生成4646个节点之后才求得解(目标节点)。个节点之后才求得解(目标节点)。3.2 盲目搜索253.2 盲目搜索3.2.2 深度优先搜索深度优先搜索(Dephth-first)(Dephth-first)26v 定义:定义:首先扩展最新产生的首先扩展最新产生的(即最深的即最深的)节点。节点。v 特点:特点:防防止止搜搜索索过过程程沿沿着着无无益益的的路路
17、径径扩扩展展下下去去,往往往往给给出一个节点扩展的最大深度出一个节点扩展的最大深度深度界限。深度界限。与与宽宽度度优优先先搜搜索索算算法法最最根根本本的的不不同同在在于于:将将扩扩展展的后继节点放在的后继节点放在OPENOPEN表的前端表的前端。3.2 3.2 盲目搜索盲目搜索深度优先搜索示意图27SLOMFPQNFFF3.2 3.2 盲目搜索盲目搜索28开始开始把把S放入放入OPEN表表OPEN表为空表?表为空表?把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点?为目标节点?扩展扩展n,把,把n的后继节点放入的后继节点放入OPEN表
18、的表的前前端,提供返回节点端,提供返回节点n的指针的指针失败失败成功成功图图3.6 深度优先算法框图深度优先算法框图是是否否是是否否3.2 盲目搜索节点节点n的深度等于最大深度?的深度等于最大深度?否否2024/9/18 周三29深度优先算法Procedrue depth-First-Search1 G=G0(G0=s),open=(s),closed=()/s:初始状态2 Loop:if open=()then exit(fall)3 nfirst(open)4 if goal(n)then exit(success)5remove(n,open),add(n,closed)6mj expa
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自动化 人工智能 确定性 推理
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。