人工智能2(北邮课件).ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《人工智能2(北邮课件).ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 课件
- 资源描述:
-
1、1第二章第二章 知识表示方法知识表示方法状态空间法问题归约法谓词逻辑法语义网络法框架表示法剧本表示法过程表示法22.1 状态空间法状态空间法问题状态描述状态图示法状态空间表示举例32.1.1 问题状态描述问题状态描述1、状态(、状态(State)的基本概念)的基本概念状态状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0,q1,qn的有序集合,其矢量形式如下:Q=q0,q1,qnT (2.1)式中每个元素qi(i=0,1,n)为集合的分量,称为状态变量。 给定每个分量的一组值就得到一个具体的状态,如Qk=qk,q1k,,qnkT (2.2)4算符算符:使问题从一种状态变化为
2、另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。5问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图,它包含三种说明的集合,即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此,可把状态空间记为三元状态(S,F,G)。6 2、状态空间的表示法、状态空间的表示法对一个问题的状态描述,必须确定3件事:(1) 该状态描述方式,特别是初始状态描述;(2) 操作符集合及其对状态描述的作用;(3) 目标状态描述的特性。7 14376582八数码问题的状态空间S状态集。八数码的所有的摆法(9!)G指定的某个或某些八数
3、码摆放状态。操作算子数码的移动。4(方向) 8(数码)32个l将空格向上移Upl将空格向左移Leftl将空格向下移Downl将空格向右移 Right82.1 状态空间法状态空间法问题状态描述状态图示法状态空间表示举例92.1.2 状态图示法状态图示法图的基本概念图由节点(不一定是有限的节点)的集合构成。一对节点用弧线连接起来,从一个节点指向另一个节点。这种图叫做有向图(directed graph)。某个节点序列(ni1,ni2,nik)当j=2,3,k时,如果对于每一个ni,j-1都有一个后继节点nij存在,那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(cost)
4、是给各弧线指定数值以表示加在相应算符上的代价。10图的显式说明 是指各节点及其具有代价的弧线由一张表明确给出。图的隐式说明 是指各节点及其具有代价的弧线不能由一张表明确给出。111 4 37 65 8 21 37 4 65 8 21 4 3 7 65 8 21 4 37 8 65 21 4 37 65 8 2 1 37 4 65 8 21 37 4 65 8 21 4 37 65 8 2 4 35 7 6 8 21 4 37 8 6 5 21 4 37 8 65 21 47 6 35 8 21 4 37 6 25 8UpLeftDownRightUpDownDownUpRightLeftLef
5、tRight122.1 状态空间法状态空间法问题状态描述状态图示法状态空间表示举例132.1.3 状态空间表示举例状态空间表示举例1、产生式系统、产生式系统一个产生式系统由下列3部分组成:一个总数据库(global database),它含有与具体任务有关的信息。一套规则,它对数据库进行操作运算。每条规则由左右两部分组成,左部鉴别规则的适用性或先决条件,右部描述规则应用时所完成的动作。应用规则来改变数据库。一个控制策略,它确定应该采用哪一条适用规则,而且当数据库的终止条件满足时,就停止计算。142、状态空间表示举例、状态空间表示举例 猴子与香蕉的问题acb15 状态空间表示 设系统的状态用四元
6、数组描述:S=(w, x, y, z) 其中w:猴子所处水平位置 x:箱子所在水平位置 y:猴子是否在箱子上(y=1,在; y=0,不在) z:猴子是否能拿到香蕉(z=1,拿到; z=0,没有拿到)16可能出现的状态如下:S0=(a,b,0,0)S1=(b,b,0,0)S2=(c,c,0,0)S3=(c,c,1,0)S4=(c,c,1,1)其中S0为初始状态, S4为目标状态。17 算符 F=(f1, f2, f3 , f4 )其中 f1 (u) 为猴子走到u处。(w, x, 0, z) (u, x, 0, z) f2 (u) 为猴子走到v处。(x, x, 0, 0 ) (v, v, 0, 0
7、) f3 为猴子爬上台子。 (x, x, 0, z ) (x, x,1, z) f4 为猴子拿到香蕉。 (c, c, 1, 0) (c, c,1, 1 )18求解过程 S0S4P1:主操作f1P2:主操作f2P3:主操作f3P4:主操作f4S2S3S0S2S3S4S0S1S1S2P31(f1, f2)P32( f3)P33( f4)P312( f2)P311( f1)19旅行商问题(travelling salesman problem,TSP问题) 销售员到几个城市去推销商品,城市之间的距离是已知的,他现在从某一个城市出发,经过每个城市一次,最后又回到出发的城市。要求归划好一条最短路线。77
8、10101013656ABEDC20第二章第二章 知识表示方法知识表示方法状态空间法问题归约法谓词逻辑法语义网络法框架表示法剧本表示法过程表示法212.2 问题归约法问题归约法问题归约描述与或图表示222.2.1 问题归约描述问题归约描述1、问题归约法的概念已知问题的描述,通过一系列变换把此问题最终变为一个子问题集合;这些子问题的解可以直接得到,从而解决了初始问题。该方法也就是从目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题,直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。232、问题归约法的组成部分 (1)一个初始问题描述;(2)一套把问题变换为子问题的
9、操作符;(3)一套本原问题描述。243、示例:梵塔难题问题 有3个柱子(1,2,3)和3个不同尺寸的圆盘(A,B,C)。在每个圆盘的中心有个孔,所以圆盘可以堆叠在柱子上。最初,全部3个圆盘都堆在柱子1上:最大的圆盘C在底部,最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上,每次只许移动一个,而且只能先搬动柱子顶部的圆盘,还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。25132C123ABABC26归约过程:(1)移动圆盘A和B至柱子2的双圆盘难题;(2)移动圆盘C至柱子3的单圆盘难题;(3)移动圆盘A和B至柱子3的双圆盘难题。27132C123ABABC28123ABC123ABC29123A
10、BC123ABC304、归约描述问题归约方法是应用算符来把问题描述变换为子问题描述。可以用状态空间表示的三元组合(S、F、G)来规定与描述问题;对于梵塔问题,子问题(111)(122),(122)(322)以及(322)(333)规定了最后解答路径将要通过的脚踏石状态(122)和(322)。问题归约方法可以应用状态、算符和目标这些表示法来描述问题,这并不意味着问题归约法和状态空间法是一样的。31(1,1,1)(3,3,3)(1,1,1)(1,2,2) (1,2,2)(3,2,2)(3,2,2)(3,3,3)(1,1,1)(1,1,3) (1,2,3)(1,2,2)(1,1,3)(1,2,3)(
11、3,2,2)(3,3,3)(3,2,2)(3,2,1)(3,3,1)(3,3,3)322.2 问题归约法问题归约法问题归约描述与或图表示332.2.2 2.2.2 与或图表示与或图表示1、与或图的概念用一个类似图的结构来表示把问题归约为后继问题的替换集合,画出归约问题图。例如,设想问题A需要由求解问题B、C和D来决定,那么可以用一个与图来表示;同样,一个问题A或者由求解问题B、或者由求解问题C来决定,则可以用一个或图来表示。34352、与或图的有关术语父节点父节点 是一个初始问题或是可分解为子问题的问题节点;子节点子节点 是一个初始问题或是子问题分解的子问题节点;或节点或节点 只要解决某个问题
12、就可解决其父辈问题的节点集合;与节点与节点 只有解决所有子问题,才能解决其父辈问题的节点集合;弧线弧线 是父辈节点指向子节点的圆弧连线;终叶节点终叶节点 是对应于原问题的本原节点。363、与或图的有关定义可解节点可解节点 与或图中一个可解节点的一般定义可以归纳如下:(1) 终叶节点是可解节点(因为它们与本原问题相关连)。(2) 如果某个非终叶节点含有或后继节点,那么只有当其后继节点至少有一个是可解的时,此非终叶节点才是可解的。(3) 如果某个非终叶节点含有与后继节点,那么只要当其后继节点全部为可解时,此非终叶节点才是可解的。37不可解节点不可解节点 不可解节点的一般定义归纳于下:(1) 没有后
13、裔的非终叶节点为不可解节点。(2) 如果某个非终叶节点含有或后继节点,那么只有当其全部后裔为不可解时,此非终叶节点才是不可解的。(3) 如果某个非终叶节点含有与后继节点,那么只要当其后裔至少有一个为不可解时,此非终叶节点才是不可解的。384、与或图构图规则 代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2) 对应于本原问题的节点,叫做终叶节点,它没有后裔。(3)对于把算符应用于问题A的每种可能情况,都把问题变换为一个子问题集合;有向弧线自A指向后继节点,表示所求得的子问题集合。(4) 一般对于代表两个或两个以上子问题集合的每个节点,有向弧线从此节点指向此子问题集合中的各
14、个节点。(5) 在特殊情况下,当只有一个算符可应用于问题A,而且这个算符产生具有一个以上子问题的某个集合时,由上述规则3和规则4所产生的图可以得到简化。39第二章第二章 知识表示方法知识表示方法状态空间法问题归约法谓词逻辑法语义网络法框架表示法剧本表示法过程表示法402.3 谓词逻辑法谓词逻辑法 谓词演算谓词公式置换与合一412.3.1 谓词演算谓词演算1、语法和语义谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号,并用圆括弧、方括弧、花括弧和逗号隔开,以表示论域内的关系。原子公式是由若干谓词符号和项组成,只有当其对应的语句在定义域内为真时,才具有值T(真);而当其对应的语句在定
15、义域内为假时,该原子公式才具有值F(假)。422、连词和量词连词有(与)、(或),全称量词(x),存在量词(x)。原子公式是谓词演算的基本积木块,运用连词能够组合多个原子公式以构成比较复杂的合适公式。433、几个有关定义 用连词把几个公式连接起来而构成的公式叫做合取,而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合适公式。 用连词把几个公式连接起来所构成的公式叫做析取,而此析取式的每一组成部分叫做析取项。由一些合适公式所构成的任一析取也是一个合适公式。 用连词连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项,右式叫做后项。如果前项和后项都是合适公式,那么蕴涵也是合
16、适公式。44 前面具有符号的公式叫做否定。一个合适公式的否定也是合适公式。 量化一个合适公式中的某个变量所得到的表达式也是合适公式。如果一个合适公式中某个变量是经过量化的,就把这个变量叫做约束变量,否则就叫它为自由变量。在合适公式中,感兴趣的主要是所有变量都是受约束的。这样的合适公式叫做句子。452.3 谓词逻辑法谓词逻辑法 谓词演算谓词公式置换与合一462.3.2 2.3.2 谓词公式谓词公式1、谓词合适公式的定义在谓词演算中合适公式的递归定义如下:(1) 原子谓词公式是合适公式。(2) 若A为合适公式,则A也是一个合适公式。(3) 若A和B都是合适公式,则(AB),(AB),(A=B)和(
展开阅读全文