第二章 知识表达技术,课程的基本内容 知识的概念与含义，知识类型和知识模型的变换； 重点介绍几种常用的知识表达法状态空间表示法、与/或图表示法、产生式系统、知识的逻辑表达方法、语义网络、框架表达法、特征表表达法和面向对象的表达法。 课程的基本要求 掌握知识表达的基本概念，学会划分知识的类型和理解知识模型变换在解决人工智能问题的过程中的作用与意义； 学会如何将一个具体的问题，用所介绍的知识表达方法来表示； 初步体会在各种知识表达方法中，其知识机构是如何随知识的运用而变化的。,2020/7/30,1,第二章 知识表达技术21 知识的概念与含义,智能行为即拥有知识 即对知识的获取、表达、搜索、分析、解答等智能能力 人的智能的核心也在于“知识” 感性知识与理性知识，经验知识与理论知识 智能表现在： 知识的获取能力通过感知器官获取感性知识 知识的处理能力将感性知识上升为理性知识 知识的运用能力采取行动，发挥知识的效用 知识：是人们对自然现象的认识和从中总结出来的规律、经验,2020/7/30,2,第二章 知识表达技术21 知识的概念与含义,知识模式 K = F+R+C K表示知识项(Knowledge items) F表示事实(Facts)人类对客观世界、客观事物的状态、属性、特征的描述，以及对事物之间关系的描述 R表示规则(Rules)能表达在前提与结论之间的因果关系的一种形式 C表示概念(Concepts)事实的含义规则语义说明等,2020/7/30,3,第二章 知识表达技术 22 知识表达技术,知识类型 叙述型知识有关系统状态、环境和条件，问题的概念、定义和事实的知识。 过程型知识有关系统状态变化、问题求解过程的操作、演算和行动的知识。 控制型知识有关如何选择相应的操作、演算和行动的比较、判断、管理和决策的知识。 例：对于从北京到上海，是乘飞机还是坐火车的问题。 叙述型知识：北京、上海、飞机、火车、时间、费用。 过程型知识：乘飞机、坐火车。 控制型知识：乘飞机较快、较贵；坐火车较慢、较便宜。,2020/7/30,4,知识的表达技术,2020/7/30,5,第二章 知识表达技术 (一) 状态空间表达,状态用来表示系统状态,事实等叙述型知识的一组变量或数组Q=q1,q2,qnt 操作是用来表示引起状态变化的过程型知识的一组关系或函数F:f1,f2,fm 状态空间(State Space)是利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组（S，O，S0，G）： S状态集合;O操作算子集合;S0初始状态,S0S;G目的状态,GS,(G可若干具体状态，也可满足某些性质的路径信息描述) 从S0结点到G结点的路径被称为求解路径。 状态空间一解是一有限操作算子序列，它使初始状态转换为目标状态： O1 O2 O3 Ok S0S1S2G 其中O1，Ok即为状态空间的一个解(解往往不是唯一的),2020/7/30,6,第二章 知识表达技术 23 状态空间表达,【例22】八数码问题的状态空间 在一33方格盘，放1到8八个数码，另一格为空。空格四周上下左右数码可移到空格。一布局： 2 3 1 5 8 4 6 7 八数码任何一种摆法就是一个状态，所有的摆法为状态集S，构成了一个状态空间，其大小为9！ 相应操作算子是数码移动，其操作算子共有4（方向）8（数码）=32个。可简化为4个：Up，Left，Down，Right,2020/7/30,7,状态图,这种描述问题的有向图被称为状态空间图，简称状态图； 许多智力问题都可以归结为在某一状态中寻找目标或路径的问题。,2020/7/30,8,例 3.8八数码难题的状态图表示。 我们将棋局,用向量,A(X0, X1, X2, X3, X4, X5, X6, X7, X8),表示,Xi为变量,Xi的值就是方格Xi内的数字。于是,向量A就是该问题的状态空间表达式。,2020/7/30,9,设初始状态和目标状态分别为 So(0, 2, 8, 3, 4, 5, 6, 7, 1) Sg(0, 1, 2, 3, 4, 5, 6, 7, 8) 易见,数码的移动规则就是该问题的状态变换规则,即操作。经分析, 该问题共有24条移码规则, 可分为9组。,2020/7/30,10,0组规则:,1组规则:,2020/7/30,11,2组规则:,8组规则:,于是, 八数码问题的状态空间（状态图）可表示为,(So, r1, r2, , r24, Sg),2020/7/30,12,当然,上述24条规则也可以简化为4条: 即空格上移（UP）、 下移（DOWN）、左移（LEFT）、右移（RIGHT）。不过,这时状态(即棋局)就需要用矩阵来表示。 可以看出,这个状态图中仅给出了初始节点和目标节点, 并未给出其余节点。而其余节点需用状态转换规则来产生。 类似于这样表示的状态图称为隐式状态图, 或者说状态图的隐式表示。,2020/7/30,13,状 态 空 间 表 示,例2 走迷宫是人们熟悉的一种游戏, 如图31就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点, 把通道作为边, 则该迷宫可以由一个有向图表示(如图3-2所示)。 那么, 走迷宫其实就是从该有向图的初始节点(入口)出发, 寻找目标节点(出口)的问题, 或者是寻找通向目标节点(出口)的路径的问题。,2020/7/30,14,图 3-1 迷宫图,2020/7/30,15,图 3-2 迷宫的有向图表示,2020/7/30,16,第二章 知识表达技术 （二） 与/或图表达法,超图 树图 与/或树 基于人们在求解问题时的两种思维方法： 分解：将复杂大问题分解为一组简单小问题 若所有子问题都解决了，则总问题也解决了，这是“与”的逻辑关系“与”树 变换：将较难问题变换为较易等价/等效问题 若一难问题可以等价变换为几个容易问题，则任何一个容易问题解决了，也就解决了原有难问题，这是“或”的逻辑关系“或”树 兼用“分解”和“变换”方法“与/或”树,2020/7/30,17,与 或 图 搜 索,与或图 我们仍用例子引入与或图的概念。 例 如图所示,设有四边形ABCD和ABCD, 要求证明它们全等。 分析：分别连接B、D和B、D, 则原问题可分解为两个子问题： Q1：证明ABDABD Q2：证明BCDBCD,2020/7/30,18,图3-12 四边形ABCD和ABCD,2020/7/30,19,于是, 原问题的解决可归结为这两个子问题的解决。 换句话说,原问题被解决当且仅当这两个子问题都被解决。 进一步,问题Q1还可再被分解为 Q11：证明ABAB Q12：证明ADAD Q13：证明AA 或 Q11： 证明ABAB Q12： 证明ADAD Q13： 证明 BDBD,2020/7/30,20,问题Q2还可再被分解为 Q21：证明 BCBC Q22：证明 CDCD Q23：证明 CC 或 Q21：证明 BCBC Q22：证明 CDCD Q23：证明 BDBD,2020/7/30,21,现在考虑原问题与这两组子问题的关系, 我们便得到图3-13。图中的弧线表示所连边为“与”关系,不带弧线的边为或关系。这个图中既有与关系又有或关系,因此被称为与或图。但这个与或图是一种特殊的与或图, 称为与或树。,2020/7/30,22,图 3-13 问题的分解与变换,2020/7/30,23,第二章 知识表达技术 24 状态图、与/或图表达法,【例23】猴子和香蕉问题（两种方法都试试） 设机器人“猴子”位于a处，目的物“香蕉”挂在c处上方，猴子想吃香蕉，但高度不够，拿不着。在b处有可移动的台子，若猴子站在台子上，就可以拿到香蕉。 问题是制定机器人的行动计划，使猴子能拿到香蕉。 香蕉 a猴子 c b台子,2020/7/30,24,第二章 知识表达技术 1.状态空间法,【例23】猴子和香蕉问题 状态空间法:四元数组描述：S=(w,x,y,z) 其中： w：猴子所处水平位置 x：台子所在水平位置 y：猴子是否在台子上（y=1:在;y=0:不在） z：猴子是否能拿到香蕉（z=1:拿到;z=0:没拿到） 可能出现的状态如下： 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为目标状态,2020/7/30,25,第二章 知识表达技术 24 与/或图表达法,【例23】猴子和香蕉问题 允许的操作集为： F=f1,f2,f3,f4 其中： f1(u)为猴子走到u处 (w,x,0,z)(u,x,0,z) f2(v)为猴子推台子到v处 (x,x,0,0)(v,v,0,0) f3为猴子爬上台子 (x,x,0,z)(x,x,1,z) f4为猴子拿到香蕉 (c,c,1,0)(c,c,1,1),2020/7/30,26,第二章 知识表达技术 24 与/或图表达法,【例23】猴子和香蕉问题 允许的操作集为： F=f1,f2,f3,f4 比较目标状态（S4）与初始状态（S0）的差异，来选择主操作。由于S0与S4中的四个状态量都有差异，相应的操作为f1,f2,f3和f4，都可选为主操作。因此，可将原问题变换为四个新问题，而新问题又可分为几个子问题及子子问题。这一过程与/或树图,2020/7/30,27,第二章 知识表达技术 24 与/或图表达法,【例23】猴子和香蕉问题 与/或树图,2020/7/30,28,第二章 知识表达技术 习题练习 （一）,例 2.1 梵塔问题（状态空间法）。 设有三根宝石杆,在1号杆上穿有A、B两个金盘, A小于B，并且 A位于B的上面。 要求：把这两个金盘全部移到另一根杆上,而且规定每次只能移动一个盘子,任何时刻都不能使B位于A的上面（小盘永远在大盘上面）。,2020/7/30,29,图 2.1 二阶梵塔的全部状态,2020/7/30,30,第二章 知识表达技术 习题练习 （一）,例 2.1 梵塔问题（状态空间法）。 设用二元组(SA,SB)表示问题的状态, SA表示小盘A所在的杆号, SB表示大盘B所在的杆号, 这样, 全部可能的状态有9种, 可表示如下：,s0(1, 1), s1(1, 2), s2(1, 3) s3(2, 1), s4(2, 2), s5(2, 3) S6(3, 1), S7(3, 2), S8(3, 3),2020/7/30,31,这里的操作算子就是盘子的搬动规则，分别用A(i,j)及B(i,j)表示：A(i,j)表示把A盘（小盘）从第i号杆移到第j号杆上;B(i,j)表示把B盘（大盘）从第i号杆移到第j号杆上。经分析，共有12个操作，它们分别是：,A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2) B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2),2020/7/30,32,这样由题意,问题的初始状态为(1, 1),目标状态为(3, 3), 则二阶梵塔问题可用状态图表示为,(1, 1), A(1, 2), , B(3, 2), (3, 3),从初始节点到目标节点的任何一跳通路都是一个解，其中的最短路径长度是3，它有三个算子组成：A（1，3）、B（1，2）、A（3，2）。,2020/7/30,33,由本题可以得出结论,（1）首先必须定义状态的描述形式，通过使用这种描述形式可把问题的全部状态都表示出来。 （2）其次还要有一组算子，通过使用算子可把问题的一种状态转换为另一种状态。 （3）状态图就是通过一组算子将问题的初始状态转换为目标状态。,2020/7/30,34,作 业（一）-传教士与野人,三个传教士和三个野人来到一条河边。河边只有一只每次最多