人工智能导论机工版教学课件第3章.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《人工智能导论机工版教学课件第3章.pptx》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 导论 机工 教学 课件
- 资源描述:
-
1、人工智能导论学习目标学习难点p 利用搜索和推理技术进行问题求解的实现过程学习重点p搜索的概念、意义p状态空间的概念p状态空间盲目搜索p启发式状态空间搜索p遗传算法搜索p推理的概念、方法及基本类型p基于规则的演绎推理p产生式系统推理和不确定性原理面对具体问题,人工智能如何运用知识解决问题(面对具体问题,人工智能如何运用知识解决问题(思维过程)?思维过程)?p思维过程,思维过程,是人类认识客观世界后体现人类的智力功能的工作方式,往往直接体现在一个问题求解的过程中。p搜索与推理搜索与推理,就是人类重要的两个思维过程。p 机器使用知识也是主要采用搜搜索和推理技术索和推理技术【知识目标】【知识目标】p了
2、解搜索和推理的定义和意义了解搜索和推理的定义和意义p掌握状态空间的搜索策略及过程掌握状态空间的搜索策略及过程p了解基于状态空间的盲目搜索分类和特点了解基于状态空间的盲目搜索分类和特点p了解基于状态空间的启发式搜索过程了解基于状态空间的启发式搜索过程p了解正向、逆向、混合和双向等规则演绎推理方法了解正向、逆向、混合和双向等规则演绎推理方法p了解产生式系统推理基本原理了解产生式系统推理基本原理p 掌握基于概率和模糊原理的不确定性推理实现过程掌握基于概率和模糊原理的不确定性推理实现过程【能力目标】【能力目标】p能用状态空间深度优选搜索原理描述出具体问题的求解过程能用状态空间深度优选搜索原理描述出具体
3、问题的求解过程p能用启发式搜索原理描述出具体问题的求解过程能用启发式搜索原理描述出具体问题的求解过程p能用遗传算法原理描述出具体问题的求解过程,形成努力改变自己去适能用遗传算法原理描述出具体问题的求解过程,形成努力改变自己去适 应环境的世界观应环境的世界观p能用产生式推理原理描述出具体问题的求解过程能用产生式推理原理描述出具体问题的求解过程p能用模糊推理原理描述出具体问题的求解过程能用模糊推理原理描述出具体问题的求解过程3 3.1.1 搜索和推理概述搜索和推理概述 在问题求解过程中,人们所面临的大多数现实问题往往去无法获得其一致信息,更没有现成的方法可以直接求解使用,此刻,人类会。p 对于结构
4、性问题采用搜索方法p 对于非结构性问题采用推理方法 3.1.13.1.1 搜索搜索p“搜索”是“寻找隐藏的东西”p 被寻找的东西常常被称为“目标”或者“解”p 处理问题方式:明确目标搜索产生序列的动作输出p 搜索问题一般包括。目标:搜索什么 搜索空间:在哪里搜索1.搜索的含义搜索的含义3.1.13.1.1 搜索搜索p“按图索骥”的意思是按照书上的图或条文去找好马。比喻机械的按老办法办事。也比喻按照线索寻找需要的东西。p 以上寻找好马的过程就是搜索。3.1.13.1.1 搜索搜索p 搜索过程中采用的搜索策略、是否使用启发式信息分为盲目搜索和启发式搜索2.搜索的分类搜索的分类3.1.13.1.1
5、搜索搜索p 救援人员会在河流下游距离沉船点L远的地点进行搜索p 距离L=水流速度v 距离沉船多长时间tp 采用距离L来指引搜索,3.1.13.1.1 搜索搜索p 根据问题的表示方式分为状态空间搜索和与或树搜索 状态空间搜索:八字棋的状态空间,根据此空间图可以搜索得到八字棋游戏的解决路径2.搜索的分类搜索的分类3.1.13.1.1 搜索搜索p 根据问题的表示方式分为状态空间搜索和与或树搜索 与或树搜索:与或树搜索是指用问题规约法表示问题时进行的搜索。状态空间法和问题规约法是人工智能中最基本的两种问题表示和求解方法 基于与或树搜索的原理形成了与/或树的广度优先搜索、与/或树的深度优先、博弈树、-剪
6、枝技术搜索方法2.搜索的分类搜索的分类3.1.13.1.1 搜索搜索p A、B、C、D、E五个城市的连接网络图p 城市间连线上的数字代表它们的距离,如A和C城市的连线上有数字3,代表它们之间的距离为3,表示为LAC=3p 通过与或树可以获取从A城市出发到E城市的最短路程城市交通图城市交通图城市交通图与或树城市交通图与或树3.1.3.1.2 2 推理推理p 图3-8是一个简易的逻辑推理问题,有以下的约束:p 1个空心小球=3个条纹小球p 1个条纹小球=2个黑心小球p 得到结论:1个空心小球=6个黑心小球3.1.3.1.2 2 推理推理推理推理=语言语言+语义语义+推理规则推理规则u 语言:具有一
7、个句法用以规定在这种语言中什么是合法的表达。u 语义:用以把这种语言中的要素和某些主题中的要素联系起来。u 推理规则:用以操作这种语言的语句。3.1.3.1.2 2 推理推理p 按照推理的逻辑基础,常用的推理方法分为演绎推理、归纳推按照推理的逻辑基础,常用的推理方法分为演绎推理、归纳推理和默认推理理和默认推理u 归纳推理:是从足够多的事例中归纳出一般性结论的推理过程。即个别到一般的推理 完全归纳推理 不完全归纳推理3.1.3.1.2 2 推理推理p 按照推理的逻辑基础,常用的推理方法分为演绎推理、归纳推按照推理的逻辑基础,常用的推理方法分为演绎推理、归纳推理和默认推理理和默认推理u 默认推理:
8、在知识不完全的情况下假设某些条件已经具备所进行的推理3.1.3.1.2 2 推理推理p 按所用知识的确定性分类按所用知识的确定性分类u 确定性推理(精确推理)确定性推理(精确推理):是指推理时所用的知识与证据都是确定的,退出的结论也是确定的,其真值或者为真或者为假,没有第三种情况出现。u 不确定性推理(不精确推理)不确定性推理(不精确推理):是指推理时所用的知识与证据不都是确定的,推出的结论也是不确定的。3.1.3.1.2 2 推理推理p 推理过程的单调性分类推理过程的单调性分类u 单调推理:是指在推理过程中随着推理向前推进及新知识的加入,推出的结论越来越接近最终目标。u 非单调推理:是指在推
9、理过程中由于新知识的加入,不仅没有加强已推出的结论,反而要否定它,使推理退回到前面的某一步,然后重新开始。3.1.3.1.2 2 推理推理3.1.3.1.2 2 推理推理p 按推理中是否运用与推理有关的启发性知识来划分按推理中是否运用与推理有关的启发性知识来划分u 启发性推理启发性推理:是指在推理过程中运用与推理有关的启发性知识。u 非启发性推理非启发性推理:是指在推理过程中未运用与推理有关的启发性知识。3.1.3.1.2 2 推理推理推理的控制策略及其分类推理的控制策略及其分类推理过程不仅依赖于所用的推理方法,同时也依赖于推理的控制推理过程不仅依赖于所用的推理方法,同时也依赖于推理的控制策略
10、。策略。推理的控制策略是指如何使用领域知识使推理过程尽快达到目标推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略的策略。推理的控制策略可分为:推理的控制策略可分为:p搜索策略搜索策略p推理策略推理策略3.1.3.1.2 2 推理推理推理的控制策略及其分类推理的控制策略及其分类搜索策略:搜索策略:在知识库中寻找可利用的知识,从而构造一条在知识库中寻找可利用的知识,从而构造一条代价较代价较小小的推理路线。主要解决推理线路、推理效果、推理效率等问题。的推理路线。主要解决推理线路、推理效果、推理效率等问题。按是否使用启发式信息可分为:按是否使用启发式信息可分为:p盲目搜索盲目搜索p启发式
11、搜索启发式搜索按问题的表示方式可分为:按问题的表示方式可分为:p状态空间搜索状态空间搜索p与或树搜索与或树搜索3.1.3.1.2 2 推理推理推理的控制策略及其分类推理的控制策略及其分类推理策略:推理策略:包括推理方向控制策略、求解策略、限制策略、冲突包括推理方向控制策略、求解策略、限制策略、冲突消解策略等消解策略等p推理方向控制策略:推理方向控制策略:用于确定推理的控制方向,可分为用于确定推理的控制方向,可分为正向推理正向推理逆向推理逆向推理混合推理混合推理双向推理双向推理3.23.2状态空间的搜索策略状态空间的搜索策略3.23.2.1 1 状态空间搜索的基本思想状态空间搜索的基本思想先把问
12、题的初始状态作为当前先把问题的初始状态作为当前扩展节点扩展节点对其进行对其进行扩展扩展,生成一组,生成一组子节点。子节点。然后检查问题的目标状态是否出现在这些子节点中。若出现,则然后检查问题的目标状态是否出现在这些子节点中。若出现,则搜索成功,找到了问题的解;若没出现,则再搜索成功,找到了问题的解;若没出现,则再按照某种搜索策略按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程,直到目标状态出现在子节点中或者没有可供操作重复上述过程,直到目标状态出现在子节点中或者没有可供操作的节点为止。的节点为止。所谓对一个节点进行所谓对
13、一个节点进行“扩展扩展”是指对该节点用某个可用操作进行是指对该节点用某个可用操作进行作用,生成该节点的一组子节点作用,生成该节点的一组子节点。“扩展扩展”节点节点3.23.2.1 1 状态空间搜索的基本思想状态空间搜索的基本思想v状态空间搜索算法的数据结构和符号约定状态空间搜索算法的数据结构和符号约定OPEN表:表:未扩展节点表,用于存放刚生成节点未扩展节点表,用于存放刚生成节点CLOSED表:表:已扩展节点表,用于存放已经扩展或将要扩展节点的已扩展节点表,用于存放已经扩展或将要扩展节点的S:用表示问题的初始状态用表示问题的初始状态G:表示搜索过程所得到的搜索图表示搜索过程所得到的搜索图M:表
14、示当前扩展节点新生成的且不为自己先辈的子节点集表示当前扩展节点新生成的且不为自己先辈的子节点集3.23.2.1 1 状态空间搜索的基本思想状态空间搜索的基本思想3.2.2 3.2.2 图搜索的一般过程图搜索的一般过程图搜索策略可看作一种在图中寻找路径的方法。图搜索策略可看作一种在图中寻找路径的方法。3.2.2 3.2.2 图搜索的一般过程图搜索的一般过程图搜索策略图搜索策略的流程图的流程图3.3 3.3 状态空间的盲目搜索状态空间的盲目搜索盲目搜索又叫做无信息搜索,一般只适用于求解比较简单的问题盲目搜索又叫做无信息搜索,一般只适用于求解比较简单的问题。p 宽度优先搜索宽度优先搜索p 深度优先搜
15、索深度优先搜索p 代价树搜索代价树搜索3.33.3.1.1 宽度优先搜索宽度优先搜索p宽度优先搜索宽度优先搜索:从节点S开始,对他后继节点按从左至右搜索,然后再对下一级的后继节点按从左至右搜索,依此下去。p宽度优先搜索的特点宽度优先搜索的特点:以接近起始节点的程度依次扩展节点的3.33.3.1.1 宽度优先搜索宽度优先搜索1.宽度优先搜索的基本过程宽度优先搜索的基本过程3.33.3.1.1 宽度优先搜索宽度优先搜索2.宽度优先搜索的例子宽度优先搜索的例子:八数码难题八数码难题在在33的方格棋盘上,分别放置了表有数字的方格棋盘上,分别放置了表有数字1、2、3、4、5、6、7、8的八张牌,初始状态
16、的八张牌,初始状态S0,目标状态,目标状态Sg,如下图所示。要求应用广度优先,如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径搜索策略寻找从初始状态到目标状态的解路径。1238476528314765S0Sg3.33.3.1.1 宽度优先搜索宽度优先搜索八八数数码码难难题题的的宽宽度度优优先先搜搜索索树树3.33.3.1.1 宽度优先搜索宽度优先搜索v在上述广度优先算法中需要注意两个问题:在上述广度优先算法中需要注意两个问题:对于任意一个可扩展的节点,总是按照固定的操作符的顺序对其进对于任意一个可扩展的节点,总是按照固定的操作符的顺序对其进行扩展(行扩展(空格左移、上移、右
17、移、下移空格左移、上移、右移、下移)。)。在对任一节点进行扩展的时候,在对任一节点进行扩展的时候,如果所得的某个子节点(状态)前如果所得的某个子节点(状态)前面已经出现过,则立即将其放弃,不再重复画出(不送入面已经出现过,则立即将其放弃,不再重复画出(不送入OPEN表)表)。因此,广度优先搜索的本质是,以初始节点为根节点,在状态空间因此,广度优先搜索的本质是,以初始节点为根节点,在状态空间图中按照广度优先的原则,生成一棵搜索树。图中按照广度优先的原则,生成一棵搜索树。3.33.3.2.2 深深度优先搜索度优先搜索v状态空间的深度优先搜索状态空间的深度优先搜索深度优先搜索的基本思想:深度优先搜索
18、的基本思想:p从初始节点从初始节点S开始,在其子节点中选择一个最新开始,在其子节点中选择一个最新生成的节点进行考察。生成的节点进行考察。p如果该子节点不是目标节点且可以扩展,则扩如果该子节点不是目标节点且可以扩展,则扩展该子节点,然后再在此子节点的子节点中选展该子节点,然后再在此子节点的子节点中选择一个最新生成的节点进行考察。择一个最新生成的节点进行考察。p依此向下搜索,直到某个子节点既不是目标节依此向下搜索,直到某个子节点既不是目标节点,又不能继续扩展时,才选择其兄弟节点进点,又不能继续扩展时,才选择其兄弟节点进行考察。行考察。3.33.3.2.2 深深度优先搜索度优先搜索v状态空间的深度优
19、先搜索状态空间的深度优先搜索深度优先搜索的深度优先搜索的算法流程算法流程:3.33.3.2.2 深深度优先搜索度优先搜索2.深深度优先搜索的例子度优先搜索的例子:八数码难题八数码难题在在33的方格棋盘上,分别放置了表有数字的方格棋盘上,分别放置了表有数字1、2、3、4、5、6、7、8的八张牌,初始状态的八张牌,初始状态S0,目标状态,目标状态Sg,如下图所示。要求应用广度优先,如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径搜索策略寻找从初始状态到目标状态的解路径。1238476528314765S0Sg3.33.3.2.2 深深度优先搜索度优先搜索v深度优先搜索:深度优先
20、搜索:八数码难题八数码难题八数码难题的深度优八数码难题的深度优先搜索如右图先搜索如右图首先扩展最新产生的首先扩展最新产生的(最深的最深的)节点节点如果目标节点不在当如果目标节点不在当前搜索的分支上?前搜索的分支上?3.33.3.2.2 深深度优先搜索度优先搜索v有界深度优先搜索:有界深度优先搜索:动机:动机:为了防止搜索过程沿着无益的路径扩展下去,往往给为了防止搜索过程沿着无益的路径扩展下去,往往给出一个节点扩展的最大深度,即深度界限。出一个节点扩展的最大深度,即深度界限。思想:思想:对状态空间的深度优先搜索引入搜索深度界限,设为对状态空间的深度优先搜索引入搜索深度界限,设为dm,当搜索深度达
21、到了深度界限而仍未出现目标节点时,就,当搜索深度达到了深度界限而仍未出现目标节点时,就换一个分支进行搜索。换一个分支进行搜索。3.33.3.2.2 深深度优先搜索度优先搜索v有界深度优先搜索:有界深度优先搜索:3.33.3.2.2 深深度优先搜索度优先搜索八数码难题:八数码难题:dm=43.33.3.2.2 深深度优先搜索度优先搜索v有界深度优先搜索:有界深度优先搜索:问题:问题:如果问题有解,且其路径长度如果问题有解,且其路径长度 dm,则上述搜索过,则上述搜索过程一定能求得解。但是,若解的路径长度程一定能求得解。但是,若解的路径长度 dm,则上述搜索则上述搜索过程就得不到解。这说明在有界深
22、度优先搜索中,深度界过程就得不到解。这说明在有界深度优先搜索中,深度界限的选择是很重要的。限的选择是很重要的。要恰当地给出要恰当地给出dm的值是比较困难的。即使能求出解,它也的值是比较困难的。即使能求出解,它也不一定是最优解。不一定是最优解。3.33.3.3.3 代价树搜索代价树搜索v代价树:代价树:边上标有代价边上标有代价(或费用或费用)的树称为代价树的树称为代价树v 在代价树中,若用在代价树中,若用g(x)表示从初始节点表示从初始节点S到节点到节点x的代价,用的代价,用c(x1,x2)表示从父表示从父节点节点x1到子节点到子节点x2的代价,则有:的代价,则有:g(x2)=g(x1)+c(x
23、1,x2)v代价树搜索:代价树搜索:考虑边的代价的搜索方法,代价树搜索的目的是为了找到考虑边的代价的搜索方法,代价树搜索的目的是为了找到一条代价最小的解路径。代价树搜索方法包括:一条代价最小的解路径。代价树搜索方法包括:代价树的宽度优先搜索代价树的宽度优先搜索代价树的深度优先搜索代价树的深度优先搜索3.33.3.3.3 代价树搜索代价树搜索v 代价树的宽度优先搜索算法流程:代价树的宽度优先搜索算法流程:(1)把初始节点把初始节点S放入放入OPEN表中,置表中,置S的代价的代价g(S)=0;(2)如果如果OPEN表为空,则问题无解表为空,则问题无解,失败退出;,失败退出;(3)把把OPEN表的第
24、一个节点取出放入表的第一个节点取出放入CLOSED表,并记该节点为表,并记该节点为n;(4)考察节点考察节点n是否为目标。若是,则找到了问题的解,成功退出;是否为目标。若是,则找到了问题的解,成功退出;(5)若节点若节点n不可扩展,则转第不可扩展,则转第(2)步;否则转第步;否则转第(6)步;步;(6)扩展节点扩展节点n,为每一个子节点都配置指向父节点的指针,计算各子节点的,为每一个子节点都配置指向父节点的指针,计算各子节点的代价,并将各子节点放入代价,并将各子节点放入OPEN表中。表中。并根据各子结点的代价对并根据各子结点的代价对OPEN表中的表中的全部结点全部结点按由小到大的顺序排序按由小
25、到大的顺序排序。然后转第。然后转第(2)步。步。3.33.3.3.3 代价树搜索代价树搜索v 代价树的宽度优先搜索算法流程:代价树的宽度优先搜索算法流程:3.33.3.3.3 代价树搜索代价树搜索v 代价树的宽度优先搜索例子:代价树的宽度优先搜索例子:v例子:例子:城市交通问题。设有城市交通问题。设有5个城市,它们之间的交通线路如下方左图所个城市,它们之间的交通线路如下方左图所示,图中的数字表示两个城市之间的交通费用,即代价。用代价树的广度示,图中的数字表示两个城市之间的交通费用,即代价。用代价树的广度优先搜索,求从优先搜索,求从A市出发到市出发到E市,费用最小的交通路线。市,费用最小的交通路
展开阅读全文