知识的表示课件.ppt

1、第二章第二章 知识的表达技术知识的表达技术第一节第一节 知识表达的基本概念知识表达的基本概念第二节第二节 状态空间表达法状态空间表达法第三节第三节 与与/或图表达法或图表达法第四节第四节 产生式表达法产生式表达法第五节第五节 语义网络表达法语义网络表达法第六节第六节 谓词逻辑表达法谓词逻辑表达法第一节第一节 知识表达的基本概念知识表达的基本概念一、知识和知识的分类一、知识和知识的分类1、什么是知识、什么是知识F.Bacon：知识就是力量：知识就是力量知识的含义知识的含义人们对客观事物及其规律的认识人们对客观事物及其规律的认识在改造客观世界的实践中积累并总结出来的方法、策略和经验在改造客观世界的

2、实践中积累并总结出来的方法、策略和经验元知识元知识知识知识信息信息数据数据噪声噪声知识具有层次结构知识具有层次结构第一节第一节 知识表达的基本概念知识表达的基本概念知识、信息、数据之间的关联知识、信息、数据之间的关联数据是信息的载体和表示数据是信息的载体和表示信息是对数据的解释信息是对数据的解释将有关信息关联到一起构成知识将有关信息关联到一起构成知识知识知识将有关信息关联在一起，形成的关于客观世界某种规律性将有关信息关联在一起，形成的关于客观世界某种规律性认识的动态信息结构认识的动态信息结构正确知识的形成是一个复杂的智能过程正确知识的形成是一个复杂的智能过程人们获取知识的重要手段人们获取知识的

3、重要手段把各种信息提炼、概括、关联在一起把各种信息提炼、概括、关联在一起第一节第一节 知识表达的基本概念知识表达的基本概念2、知识的特性、知识的特性知识的相对正确性知识的相对正确性知识的确定性与不确定性知识的确定性与不确定性知识的可表示性知识的可表示性知识的可利用性知识的可利用性第一节第一节 知识表达的基本概念知识表达的基本概念3、知识的分类、知识的分类(1)按知识的作用范围按知识的作用范围常识性知识常识性知识领域性知识领域性知识共性知识共性知识领域内专业人员共同同意和接受的领域内专业人员共同同意和接受的个性知识个性知识领域专家的知识领域专家的知识(2)按知识的深度按知识的深度表层知识表层知识

4、有关客观事物的现象以及现象与结论之间关系的知识有关客观事物的现象以及现象与结论之间关系的知识深层知识深层知识有关事物本质、因果关系内涵、基本原理之类的知识有关事物本质、因果关系内涵、基本原理之类的知识第一节第一节 知识表达的基本概念知识表达的基本概念(3)按知识的层次按知识的层次零级知识（共性知识）零级知识（共性知识）有关问题求解的常识性和原理性知识有关问题求解的常识性和原理性知识一级知识（个性知识）一级知识（个性知识）专家特有的个性化的启发性知识专家特有的个性化的启发性知识二级以上知识二级以上知识关于知识的知识，又称元知识关于知识的知识，又称元知识关于我们所知道的知识的知识关于我们所知道的知

5、识的知识如何运用我们所知道的知识的知识如何运用我们所知道的知识的知识(4)按知识的确定性按知识的确定性确定性知识确定性知识不确定性不确定性第一节第一节 知识表达的基本概念知识表达的基本概念(5)按知识的作用上分：按知识的作用上分：叙述性知识叙述性知识叙述关于系统的状态、环境和条件，问题的概念、叙述关于系统的状态、环境和条件，问题的概念、定义和事实的知识定义和事实的知识过程性知识过程性知识有关系统状态变化、问题求解过程的操作、演算和有关系统状态变化、问题求解过程的操作、演算和行动的知识行动的知识控制性知识控制性知识关于如何选择相应的操作、演算以及对行动进行比关于如何选择相应的操作、演算以及对行动

6、进行比较、判断、管理决策的知识较、判断、管理决策的知识例如例如:从北京到上海是乘飞机还是乘火车的问题从北京到上海是乘飞机还是乘火车的问题叙述性知识：北京、上海、飞机、火车、时间、费用叙述性知识：北京、上海、飞机、火车、时间、费用过程性知识：乘飞机、坐火车过程性知识：乘飞机、坐火车控制性知识：乘飞机较快、较贵，乘火车较慢、较便宜控制性知识：乘飞机较快、较贵，乘火车较慢、较便宜第一节第一节 知识表达的基本概念知识表达的基本概念第一节第一节 知识表达的基本概念知识表达的基本概念二、知识表达二、知识表达1、知识表达的概念、知识表达的概念用一组约定的符号把知识编码成一组计算机可以接受的数据结构用一组约定

7、的符号把知识编码成一组计算机可以接受的数据结构用知识的规则符号、形式语言和网络图等使知识形式化和模型化用知识的规则符号、形式语言和网络图等使知识形式化和模型化它研究各种存储知识的数据结构的设计，达到以下目的：它研究各种存储知识的数据结构的设计，达到以下目的：便于实现知识的有效存储和管理便于实现知识的有效存储和管理利于进行知识推理利于进行知识推理利于机器获取知识利于机器获取知识利于使用人工智能程序设计语言予以实现利于使用人工智能程序设计语言予以实现陈述表达和过程表达陈述表达和过程表达第一节第一节 知识表达的基本概念知识表达的基本概念2、设计知识表达的基本原则、设计知识表达的基本原则可实现性可实现

8、性便于计算机处理、便于系统的开发和运行便于计算机处理、便于系统的开发和运行可理解性可理解性易读、易懂易读、易懂表示能力表示能力知识表达范围的广泛性、领域知识表达的高效性、不确定知识表达范围的广泛性、领域知识表达的高效性、不确定 性知识表达的支持程度性知识表达的支持程度可维护性可维护性对知识的增、删、改、恢复等操作能力对知识的增、删、改、恢复等操作能力可利用性可利用性对推理的适应性和对高效算法的支持性对推理的适应性和对高效算法的支持性自然性自然性符合人类思维习惯符合人类思维习惯可组织性可组织性将有关知识按某种方式组成一种知识结构的能力将有关知识按某种方式组成一种知识结构的能力第二节第二节 状态空

9、间表达法状态空间表达法一、状态空间表达法的概念一、状态空间表达法的概念气态气态液态液态固态固态降温降温降温降温加热加热加热加热瘪瘪鼓鼓充气充气放气放气第二节第二节 状态空间表达法状态空间表达法1、状态、状态用来描述某一类事物中各事物之间的差异而引入的最少的一组变量的有用来描述某一类事物中各事物之间的差异而引入的最少的一组变量的有序集合序集合可表示为向量形式：可表示为向量形式：Q=q1,q2,qnT也可以表示为多元组的形式：也可以表示为多元组的形式：Q=（q1,q2,qn）qi状态变量，又称分量，取值范围状态变量，又称分量，取值范围ai,bin状态的维数状态的维数如：长方体的状态可表示为如：长方

10、体的状态可表示为Q=(长，宽，高）长，宽，高）问题的状态包括三方面问题的状态包括三方面开始状态、中间状态、目标状态开始状态、中间状态、目标状态第二节第二节 状态空间表达法状态空间表达法2、操作、操作引起状态中某些分量发生改变，使问题从一个具体状态变化到另一个具引起状态中某些分量发生改变，使问题从一个具体状态变化到另一个具体状态的手段体状态的手段操作集合可表示为操作集合可表示为F=f1,f2,fm3、状态空间、状态空间由一个问题的全部状态以及可以使用的全部操作所构成的集合由一个问题的全部状态以及可以使用的全部操作所构成的集合通常由一个三元组表示：通常由一个三元组表示：4、状态空间图、状态空间图状

11、态空间的图形表示状态空间的图形表示表示该问题的全部可能的状态及其相互关系的赋值有向图表示该问题的全部可能的状态及其相互关系的赋值有向图第二节第二节 状态空间表达法状态空间表达法5、问题的解、问题的解如果从初始状态如果从初始状态Qs出发，经过一系列的操作能达到目标状态出发，经过一系列的操作能达到目标状态Qg，则在此通路上所经过的操作序列则在此通路上所经过的操作序列称为问题的一个解称为问题的一个解6、状态空间表达法求解问题的一般步骤、状态空间表达法求解问题的一般步骤确定状态分量确定状态分量表示问题所有可能的状态表示问题所有可能的状态定义一组操作定义一组操作画状态空间图画状态空间图求解问题求解问题找

12、到从初始状态到目标状态所经过的操作序列找到从初始状态到目标状态所经过的操作序列，=fi,fj,fp，Qg=fp(fj(fi(Qs)第二节第二节 状态空间表达法状态空间表达法二、状态空间表达法实例二、状态空间表达法实例例例1、设有三枚钱币，分别处在、设有三枚钱币，分别处在“反反”、“正正”、“反反”状态，允许每次状态，允许每次只能且必须翻一枚钱币，问连翻三次后能否达到三枚全朝上或全朝下的只能且必须翻一枚钱币，问连翻三次后能否达到三枚全朝上或全朝下的状态？状态？解：解：确定状态变量确定状态变量Q=(q1,q2,q3)qi=1表示第表示第i个钱币为反面个钱币为反面qi=0表示第表示第i个钱币为正面个

13、钱币为正面第二节第二节 状态空间表达法状态空间表达法三枚钱币全部可能的状态有三枚钱币全部可能的状态有8种：种：Q1=(0,0,0)=Qg Q2=(0,0,1)Q3=(0,1,0)Q4=(0,1,1)Q5=(1,0,0)Q6=(1,0,1)=Qs Q7=(1,1,0)Q8=(1,1,1)=Qg 引入三元操作算子引入三元操作算子F=a,b,ca将第一枚钱币翻转一次将第一枚钱币翻转一次b将第二枚钱币翻转一次将第二枚钱币翻转一次c将第三枚钱币翻转一次将第三枚钱币翻转一次状态空间三元组状态空间三元组第二节第二节 状态空间表达法状态空间表达法状态空间图状态空间图Qg=Q1=(0,0,0)Q5=(1,0,0

14、)Q7=(1,1,0)Q3=(0,1,0)Q4=(0,1,1)Qg=Q8=(1,1,1)QS=Q6=(1,0,1)Q2=(0,0,1)abacabacccbb第二节第二节 状态空间表达法状态空间表达法结论结论从从Q6不可能经过三次翻转使钱币达到不可能经过三次翻转使钱币达到Q1从从Q6能经过三次翻转使钱币达到能经过三次翻转使钱币达到Q8，共有，共有7种操作方式：种操作方式：(a,b,a)(a,a,b)(b,a,a)(b,b,b)(c,b,c)(b,c,c)(c,c,b)第二节第二节 状态空间表达法状态空间表达法例例2、修道士和野人问题。在河的左岸有、修道士和野人问题。在河的左岸有3个修道士、个修

15、道士、3个野人和一条个野人和一条船，现在要渡到河的右岸，但有如下限制条件：船，现在要渡到河的右岸，但有如下限制条件：（1）船最多坐）船最多坐2人，修道士和野人都会划船人，修道士和野人都会划船（2）在任何岸边，野人人数不能超过修道士人数，否则修道士就会）在任何岸边，野人人数不能超过修道士人数，否则修道士就会被吃掉被吃掉要求：规划出一个安全的渡河方案要求：规划出一个安全的渡河方案解解:确定状态变量确定状态变量 S=(m,c,b)。m是左岸的修道士数，是左岸的修道士数，m：0,1,2,3c是左岸的野人数，是左岸的野人数，c：0,1,2,3b是左岸的船数，是左岸的船数，b：0,1第二节第二节 状态空间

16、表达法状态空间表达法全部可能的状态数：全部可能的状态数：4*4*2=32，其中合理的状态数为，其中合理的状态数为16个（黑色表示）个（黑色表示）状态状态 m,c,b状态状态 m,c,b状态状态 m,c,b状态状态 m,c,bS0（初态）（初态）3,3,1S4 2,3,1S8 1,3,1S12 0,3,1S1 3,2,1S5 2,2,1S9 1,2,1S13 0,2,1S2 3,1,1S6 2,1,1S10 1,1,1S14 0,1,1S3 3,0,1S7 2,0,1S11 1,0,1S15 0,0,1S16 3,3,0S20 2,3,0S24 1,3,0S28 0,3,0S17 3,2,0S2

17、1 2,2,0S25 1,2,0S29 0,3,0S18 3,1,0S22 2,1,0S26 1,1,0S30 0,1,0S19 3,0,0S23 2,0,0S27 1,0,0S31（目标）（目标）0,0,0第二节第二节 状态空间表达法状态空间表达法确定所有可能操作的集合：确定所有可能操作的集合：pmc从左岸渡河过去从左岸渡河过去qmc从右岸渡河过来从右岸渡河过来操作集合操作集合F=p01,p10,p11,p02,p20,q01,q10,q11,q 02,q20第二节第二节 状态空间表达法状态空间表达法状态空间图状态空间图S0:(3,3,1)S17:(3,2,0)S18:(3,1,0)S21:

18、(2,2,0)S1:(3,2,1)S19:(3,0,0)S2:(3,1,1)S26:(1,1,0)p02q02p01q01q11p11q01p01p10q10p02p01p20q02q20q01S31:(0,0,0)S14:(0,1,1)S10:(1,1,1)S13:(0,2,1)S30:(0,1,0)S12:(0,3,1)S29:(0,2,0)S5:(2,2,1)q11p11q01p01p02q02p10q10q01p01q02q01q20p02p20p01p11q11问题的解：最佳路径有问题的解：最佳路径有4条，每种最佳路径要渡河条，每种最佳路径要渡河11次次第三节第三节 与与/或图表达法

19、或图表达法一、与一、与/或图知识表达的概念或图知识表达的概念1、与树（分解的思维方法）、与树（分解的思维方法）pp1p2p3p11p12p21p22p31p32原问题原问题子子问题子子问题子问题子问题第三节第三节 与与/或图表达法或图表达法2、或树（变换的思维方法）、或树（变换的思维方法）pp1p2p3p11p12p21p22p31p32原问题原问题等价问题等价问题等价问题等价问题第三节第三节 与与/或图表达法或图表达法3、与、与/或树（分解与变换的思维方法）或树（分解与变换的思维方法）pp1p2p3p11p12p21p22p31p32p111p112第三节第三节 与与/或图表达法或图表达法二

20、、与二、与/或树知识表达的实例或树知识表达的实例例例1、证明两四边形全等问题，要求用与、证明两四边形全等问题，要求用与/或树表示或树表示ABDCA1B1D1C1第三节第三节 与与/或图表达法或图表达法T1TT2T11T12T14T13T111T112T113T121T122T123T131T132T133T141T142T143T1211T1212T1213解：解：第三节第三节 与与/或图表达法或图表达法例例2、猴子和香蕉问题、猴子和香蕉问题acb第三节第三节 与与/或图表达法或图表达法解：解：设系统的状态用四元变量描述：设系统的状态用四元变量描述：S=(w,x,y,z)w猴子所处的水平位置猴

21、子所处的水平位置X台子所在的水平位置台子所在的水平位置Y猴子是否在台子上。猴子是否在台子上。0不在，不在，1在在Z猴子是否拿到香蕉。猴子是否拿到香蕉。0没有，没有，1拿到拿到所有可能出现的状态所有可能出现的状态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)目标状态目标状态第三节第三节 与与/或图表达法或图表达法定义操作集合：定义操作集合：F=f1,f2,f3,f3 f1(u)猴子走到猴子走到u处处f2(v)猴子推台子到猴子推台子到v处处f3猴子爬上台子猴子爬上台子f4猴子拿到香蕉猴子拿到香蕉问题的状态空间

22、：问题的状态空间：用与用与/或图表达或图表达关键操作法关键操作法第三节第三节 与与/或图表达法或图表达法P:P1:f1为关键操作为关键操作P2:f2为关键操作为关键操作P3:f3为关键操作为关键操作P4:f4为关键操作为关键操作P31:P32:P33:P311:P312:第四节第四节 产生式表达法产生式表达法一、产生式的基本形式一、产生式的基本形式原因原因结果；条件结果；条件结论；前提结论；前提操作；事实操作；事实进展；情况进展；情况行为行为IF P THEN Q 或或 PQP原因、条件或前提（前件）原因、条件或前提（前件）Q结果、结论或操作（后件）结果、结论或操作（后件）第四节第四节 产生式

23、表达法产生式表达法简单前件和后件的产生式简单前件和后件的产生式：天下雨，地上湿。（原因天下雨，地上湿。（原因结果）结果）如果把冰加热到如果把冰加热到0度以上，冰就会融化为水。（条件度以上，冰就会融化为水。（条件结论）结论）“夜来风雨声，花落知多少。夜来风雨声，花落知多少。”（事实（事实进展）进展）若能找一个合适的杠杆，就能撬起那座大山。（前提若能找一个合适的杠杆，就能撬起那座大山。（前提操作）操作）“才饮长江水，又食武昌鱼。才饮长江水，又食武昌鱼。”（事实（事实进展）进展）刚才开机了，意味着发出了捕获目标图像的信号。（情况刚才开机了，意味着发出了捕获目标图像的信号。（情况行为）行为）第四节第四

24、节 产生式表达法产生式表达法多个前件或后件的产生式多个前件或后件的产生式四边形四边形四边相等四边相等有一角是直角有一角是直角正方形正方形甲到太白山旅游甲到太白山旅游山上突然刮起寒风山上突然刮起寒风甲仅仅穿着单衣甲仅仅穿着单衣冰雹雪花纷纷飘落冰雹雪花纷纷飘落气候太寒冷了气候太寒冷了甲浑身打哆嗦甲浑身打哆嗦第四节第四节 产生式表达法产生式表达法用用Backus Normal Form(BNF)描述描述产生式产生式 =前提前提 结论结论前提前提 =简单条件简单条件 复合条件复合条件结论结论 =事实事实 操作操作复合条件复合条件 =简单条件简单条件AND简单条件简单条件（AND简单条简单条件）件）简单

25、条件简单条件OR简单条件简单条件（OR简单条件）简单条件）操作操作 =操作名操作名（变元，（变元，）第四节第四节 产生式表达法产生式表达法二、产生式系统二、产生式系统1、含义、含义以产生式规则作为过程性知识的系统以产生式规则作为过程性知识的系统把一组产生式放在一起，让它们互相配合，协同作用，一个产生式把一组产生式放在一起，让它们互相配合，协同作用，一个产生式生成的结论可以供另一个产生式作为前提使用，以这种方式求得问生成的结论可以供另一个产生式作为前提使用，以这种方式求得问题解的系统题解的系统2、组成、组成推理机推理机全局数据库全局数据库规则库规则库第四节第四节 产生式表达法产生式表达法（1）全

26、局数据库（综合数据库、事实库）全局数据库（综合数据库、事实库）数据是广义的数据是广义的常数、变量、谓词、多元组、表、图形、图像、常数、变量、谓词、多元组、表、图形、图像、复杂知识结构复杂知识结构用来表述问题空间的状态和有关的事实，内容是动态变化的用来表述问题空间的状态和有关的事实，内容是动态变化的对应的是叙述性知识对应的是叙述性知识多元组表示综合数据库多元组表示综合数据库PQ，P=(S1,S2,SK)，Q=(D1,D2,DL)单个对象的表示：（对象名，属性，值）单个对象的表示：（对象名，属性，值）两个对象的表示：（对象两个对象的表示：（对象i，相互关系，对象，相互关系，对象j）多个对象的表示：

27、两两对象用一个三元组表示多个对象的表示：两两对象用一个三元组表示不确定性知识：不确定性知识：（对象名，属性，值，可信度因子）（对象名，属性，值，可信度因子）第四节第四节 产生式表达法产生式表达法多元组表示综合数据库的例子多元组表示综合数据库的例子（梅花，欢喜，大雪）（梅花，欢喜，大雪）（葡萄，味道，酸甜）（葡萄，味道，酸甜）（小王，症状，咳嗽）（小王，症状，咳嗽）（小王，病症，感冒，（小王，病症，感冒，0.8)（大龟，赛跑，兔子）（大龟，赛跑，兔子）（兔子，样子，傲慢地睡着了）（兔子，样子，傲慢地睡着了）（大龟，样子，拼命地爬行）（大龟，样子，拼命地爬行）（大龟，成功地胜过了，兔子）（大龟，成

28、功地胜过了，兔子）第四节第四节 产生式表达法产生式表达法（2）规则库）规则库描述某领域内知识，作用在综合数据库上的产生式规则的集合描述某领域内知识，作用在综合数据库上的产生式规则的集合对应过程性知识对应过程性知识是产生式系统求解问题的基础是产生式系统求解问题的基础规则不一定是严格的规律，只要在其应用范围内有效即可规则不一定是严格的规律，只要在其应用范围内有效即可对规则库进行适当的管理，可提高求解问题的效率对规则库进行适当的管理，可提高求解问题的效率第四节第四节 产生式表达法产生式表达法（3）推理机）推理机控制、协调规则库和综合数据库的运行控制、协调规则库和综合数据库的运行包括：控制策略、推理方

29、式包括：控制策略、推理方式1）控制策略的功能（如何选择和应用规则）控制策略的功能（如何选择和应用规则）匹配匹配按一定的控制策略（不可撤回的、试探性的）将选定规则按一定的控制策略（不可撤回的、试探性的）将选定规则的前提条件与综合数据库中的已知事实进行比较的前提条件与综合数据库中的已知事实进行比较消除冲突消除冲突当两条以上的规则可被匹配时当两条以上的规则可被匹配时最早匹配原则最早匹配原则最强条件优先原则最强条件优先原则最高优先级原则最高优先级原则最大（最小）估计函数原则最大（最小）估计函数原则第四节第四节 产生式表达法产生式表达法操作操作执行启用规则的操作部分（判断是否达到目标）执行启用规则的操作

30、部分（判断是否达到目标）检测系统运行状态检测系统运行状态跟踪问题的求解过程跟踪问题的求解过程2）推理方式）推理方式正向推理正向推理反向推理反向推理双向推理双向推理第四节第四节 产生式表达法产生式表达法三、产生式系统的问题求解过程三、产生式系统的问题求解过程1、正向推理过程、正向推理过程数据驱动方式、自底向上方式数据驱动方式、自底向上方式由已知事实出发，通过规则推导出结论（目标）由已知事实出发，通过规则推导出结论（目标）优点优点简单明了简单明了缺点缺点有一定的盲目性，执行效率较低有一定的盲目性，执行效率较低第四节第四节 产生式表达法产生式表达法将初始事实置入数据库将初始事实置入数据库存在未用规则

31、与数据库匹配存在未用规则与数据库匹配成功成功数据库包含解数据库包含解使用规则，更新数据库使用规则，更新数据库能否提供更多信息能否提供更多信息更新数据库更新数据库YNNY失败失败NY实例：动物识别实例：动物识别R1：有毛：有毛哺乳动物哺乳动物R2：有奶：有奶哺乳动物哺乳动物R3：有羽毛：有羽毛鸟鸟R4：会飞：会飞产蛋产蛋鸟鸟R5：食肉：食肉哺乳动物哺乳动物食肉动物食肉动物R6：哺乳动物：哺乳动物 有犬齿有犬齿 有爪有爪食肉动物食肉动物R7：哺乳动物：哺乳动物 有蹄有蹄蹄类动物蹄类动物R8：哺乳动物：哺乳动物 反刍反刍蹄类动物蹄类动物R9：食肉动物：食肉动物黄褐色黄褐色黑斑点黑斑点金钱豹金钱豹R1

32、0：食肉动物：食肉动物黄褐色黄褐色黑条纹黑条纹虎虎R11：蹄类动物：蹄类动物长颈长颈腿长腿长黄褐色黄褐色黑斑点黑斑点长颈鹿长颈鹿R12：蹄类动物：蹄类动物白色白色黑条纹黑条纹斑马斑马R13：鸟：鸟不会飞不会飞长颈长颈腿长腿长黑白两色黑白两色 鸵鸟鸵鸟R14：鸟：鸟不会飞不会飞会游泳会游泳黑白两色黑白两色 企鹅企鹅R15：鸟：鸟会飞会飞信天翁信天翁设初始事实是：黄褐色、黑斑点，用正向推理说明推理过程和结论设初始事实是：黄褐色、黑斑点，用正向推理说明推理过程和结论长颈鹿黄褐色蹄类动物黑斑点哺乳动物有蹄有毛有奶反刍R11R1R2R7R8长颈腿长第四节第四节 产生式表达法产生式表达法第四节第四节 产生

33、式表达法产生式表达法2、反向推理过程、反向推理过程目标驱动方式、自顶向下方式目标驱动方式、自顶向下方式由目标出发，反向使用规则，求证已知事实由目标出发，反向使用规则，求证已知事实不使用与问题无关的规则，效率高不使用与问题无关的规则，效率高适合目标明确的问题适合目标明确的问题初始事实初始事实目标目标目标链目标链目标链为空目标链为空成功成功YN取第一个目标与事实匹配取第一个目标与事实匹配匹配成功匹配成功YN用各规则的结论与该目标匹配用各规则的结论与该目标匹配匹配成功匹配成功Y第一个匹配成功且未用第一个匹配成功且未用规则的前提规则的前提目标链目标链取代父目标取代父目标N该目标是初始目标该目标是初始目

34、标失败失败Y将该目标的父目标移回目标链将该目标的父目标移回目标链取代该目标及其兄弟目标取代该目标及其兄弟目标N3、双向推理、双向推理即自顶向下又自底向上即自顶向下又自底向上推理从两方面进行，直到某个中间界面上两方向结果相符，则推推理从两方面进行，直到某个中间界面上两方向结果相符，则推理成功理成功优点优点效率高，推理网络小效率高，推理网络小缺点缺点难度大难度大第四节第四节 产生式表达法产生式表达法设初始事实是：黄褐色、黑斑点，有奶、有犬齿、有爪，分别用正设初始事实是：黄褐色、黑斑点，有奶、有犬齿、有爪，分别用正向推理、反向推理（推理效率与多个目标的顺序）、双向推理说明向推理、反向推理（推理效率与

35、多个目标的顺序）、双向推理说明推出动物是否为金钱豹的推理过程推出动物是否为金钱豹的推理过程金钱豹黄褐色食肉动物黑斑点哺乳动物食肉有毛有奶有犬齿有爪R9R1R2R5R6第四节第四节 产生式表达法产生式表达法四、产生式系统的分类四、产生式系统的分类1、按总体控制策略分类、按总体控制策略分类（1）不可撤回的（）不可撤回的（Irrevocable)产生式系统产生式系统搜索过程一直进行下去，规则使用后不允许回过头重新选用其搜索过程一直进行下去，规则使用后不允许回过头重新选用其他规则他规则优点优点控制过程简单控制过程简单缺点缺点问题有多个解时，不一定能找到最优解问题有多个解时，不一定能找到最优解第四节第四

36、节 产生式表达法产生式表达法（2）试探式（）试探式（Tentative)产生式系统产生式系统回溯（回溯（Backtracking）产生式系统（可恢复的产生式系统）产生式系统（可恢复的产生式系统）碰壁回头的方式碰壁回头的方式先试用一条规则，如果不合适，允许退回先试用一条规则，如果不合适，允许退回原来状态，再选用另一条规则试用原来状态，再选用另一条规则试用全局数据库即可增加新内容，又可删、改全局数据库即可增加新内容，又可删、改如何确定回溯条件，如何减少回溯次数如何确定回溯条件，如何减少回溯次数对于搜索量小的问题，完备有效对于搜索量小的问题，完备有效第四节第四节 产生式表达法产生式表达法实例：四皇后

37、问题。在实例：四皇后问题。在4*4棋盘上放四个皇后，要求任何两个皇后都棋盘上放四个皇后，要求任何两个皇后都不能在同一行、同一列、同一对角线上不能在同一行、同一列、同一对角线上解：解：用用Aij表示皇后出现在位置表示皇后出现在位置(i,j)上，上，i表示列，表示列，j表示行表示行用已经出现的皇后序列表示综合数据库用已经出现的皇后序列表示综合数据库规则集规则集Rij，其作用的结果是在数据库中增加皇后，其作用的结果是在数据库中增加皇后Aij（棋盘上无皇（棋盘上无皇后时，后时，i=1)第四节第四节 产生式表达法产生式表达法()A11A13A11,A23A11,A24A11,A23,A42A11,A24

38、,A32A13,A21A13,A21,A34A13,A21,A34,A42R11R13R23R24R32R42R21R34R42#图搜索图搜索(Graph-search)产生式系统产生式系统记忆全部求解过程记忆全部求解过程便于选取最优路径便于选取最优路径与回溯式的主要区别与回溯式的主要区别回溯式抹去了所有引起失败的试探路回溯式抹去了所有引起失败的试探路径，图搜索式记住了所有的试探路径径，图搜索式记住了所有的试探路径第四节第四节 产生式表达法产生式表达法第四节第四节 产生式表达法产生式表达法2、按规则库的性质和结构分类、按规则库的性质和结构分类（1）可交换产生式系统）可交换产生式系统设设DB是全

39、局数据库，是全局数据库，RB是规则库，是规则库，DBi是第是第i次使用规则后得到次使用规则后得到的新的全局数据库，的新的全局数据库，RS RB是一个可作用于是一个可作用于DBi的规则集合。的规则集合。一个产生式系统是可交换的，是指其一个产生式系统是可交换的，是指其RB和每一个和每一个DBi具有以下具有以下性质：性质：对任一规则对任一规则Rj RS，它作用于，它作用于DBi得到新的全局数据库得到新的全局数据库DBi+1，RS仍然是仍然是DBi+1的可用规则集的可用规则集如果如果DBi满足目标条件，则用满足目标条件，则用RS中任一规则中任一规则Rj作用于作用于DBi，得到的得到的DBi+1仍满足目

40、标条件仍满足目标条件若对若对DBi使用某一规则序列使用某一规则序列R1，R2，Rk得到一个全得到一个全新数据库新数据库DBk，则当改变这些规则的使用次序后，仍然可，则当改变这些规则的使用次序后，仍然可得到得到DBk实例：设给定一个整数集合实例：设给定一个整数集合a,b,c，通过将集合中任意一对元素的，通过将集合中任意一对元素的乘积作为新元素添加到集合中扩大该整数集，要求通过若干次操作乘积作为新元素添加到集合中扩大该整数集，要求通过若干次操作能生成所需的整数集合能生成所需的整数集合a,b,c,ab,bc,ac 全局数据库全局数据库DB初始状态初始状态a,b,c目标状态目标状态a,b,c,ab,b

41、c,ac 规则集规则集RB：R1：IF a,b,c THEN a,b,c,ab R2：IF a,b,c THEN a,b,c,bc R3：IF a,b,c THEN a,b,c,ac 第四节第四节 产生式表达法产生式表达法规则可任意交换次序不影响对问题的求解规则可任意交换次序不影响对问题的求解全局数据库的内容是递增的（规则的结论部分总是包含新的内容）全局数据库的内容是递增的（规则的结论部分总是包含新的内容）求解出任一路径，就能达到目标，不必回溯，可采用不可撤回的控求解出任一路径，就能达到目标，不必回溯，可采用不可撤回的控制方式制方式不必记录规则的作用序列，可提高求解效率不必记录规则的作用序列，

42、可提高求解效率第四节第四节 产生式表达法产生式表达法（2）可分解的产生式系统）可分解的产生式系统把一个整体问题或初始数据库分解为若干个相互独立的子部分，通把一个整体问题或初始数据库分解为若干个相互独立的子部分，通过对子部分的解求得整体问题的解过对子部分的解求得整体问题的解求解问题的过程可用与求解问题的过程可用与/或树表示或树表示实例：设全局数据库的初试状态为实例：设全局数据库的初试状态为C,B,Z，目标状态为，目标状态为M,M,M，求问题求解过程。，求问题求解过程。规则库包括规则库包括:R1：C D，LR2：C B，MR3：B M，MR4：Z B，B，M第四节第四节 产生式表达法产生式表达法C

43、,B,ZCBZD,LB,MM,MB,B,MDLBMM,MMMMMBBMM,MM,MMMMMR2R1R3R4R3R3R3五、产生式系统的特点和应用五、产生式系统的特点和应用1、优点、优点模块性模块性自然性自然性有效性有效性一致性一致性容易排除故障容易排除故障2、缺点、缺点效率不高效率不高非透明性非透明性解释能力的局限性解释能力的局限性第四节第四节 产生式表达法产生式表达法3、应用、应用专门领域中经验性及不确定性的知识专门领域中经验性及不确定性的知识用于由许多相对独立的知识元组成的领域中用于由许多相对独立的知识元组成的领域中问题可被表示为一系列相互独立的操作步骤，每个步骤又可表问题可被表示为一系列

44、相互独立的操作步骤，每个步骤又可表示为产生式规则时示为产生式规则时求解问题可视为问题空间中一个状态到另一个状态的变换序列求解问题可视为问题空间中一个状态到另一个状态的变换序列第四节第四节 产生式表达法产生式表达法第五节第五节 语义网络表达法语义网络表达法一、语义网络的概念一、语义网络的概念语义语义指语言结构（词、短语、句子、段落）及其意义上的联系指语言结构（词、短语、句子、段落）及其意义上的联系语义网络语义网络由一组结点和若干条有向弧构成的，用概念和语义关由一组结点和若干条有向弧构成的，用概念和语义关系表达知识的有向图系表达知识的有向图结点结点表示事物的名称、概念、属性、情况、动作、状态表示事

45、物的名称、概念、属性、情况、动作、状态弧弧表示结点间的语义联系表示结点间的语义联系指针指针对结点、弧线、语义关系作补充说明对结点、弧线、语义关系作补充说明语义基元语义基元构成语义网络的基本单元，（结点构成语义网络的基本单元，（结点1，弧，结点，弧，结点2）ABR语义网络的多层嵌套结构语义网络的多层嵌套结构每个结点可以是一个语义子网络每个结点可以是一个语义子网络二、语义网络知识表达二、语义网络知识表达1、基本语义关系、基本语义关系（1）属性关系（）属性关系（Have、Can、Is、Owner）企鹅企鹅翅膀翅膀游泳游泳HaveCanIs黑白两色黑白两色第五节第五节 语义网络表达法语义网络表达法（2

46、）包含关系（聚类关系）包含关系（聚类关系）APOA Part OfCOComposed Of教学教学课程课程教师教师APO学生学生APOAPO信息学院信息学院通信系通信系信息系信息系CO计算机系计算机系COCO第五节第五节 语义网络表达法语义网络表达法（3）从属关系（分类关系）从属关系（分类关系）ISAis-aAKOA Kind OfAMOA Member Of有继承性有继承性植物植物海堂花海堂花AKO研究生研究生王明王明AMO著名古都著名古都西安西安ISA分类关系分类关系成员关系成员关系实例关系实例关系第五节第五节 语义网络表达法语义网络表达法（4）因果关系（推论关系）因果关系（推论关系）I

47、f-thenFetchGetBOBecause OfFor室内上体育课室内上体育课天下雨天下雨If-then（5）时间关系（）时间关系（After、Before）开放开放阅览阅览After国家昌盛国家昌盛人民安康人民安康Get第五节第五节 语义网络表达法语义网络表达法（6）位置关系）位置关系 Located-on Located-atLocated-under Located-insideLocated-outside）钟山脚下校园 Located-under西安城中心钟搂Located-at 第五节第五节 语义网络表达法语义网络表达法（7）相近关系）相近关系Similar-to Near-t

48、o公园公园校园校园 Similar-to大理堂大理堂图书馆图书馆Near-to 第五节第五节 语义网络表达法语义网络表达法第五节第五节 语义网络表达法语义网络表达法2、实例、实例钟山校园建筑物图书馆大礼堂理工大学单位海福港阅览室开放学会张三读者浏览公园风景美丽讲英语Located-underLocated-insideSimilar-toFetchA-Kind-ofOwnerLocated-atIs-aNear-toA-Part-ofAfterHaveCanA-Member-ofIs-aCanCanLocated-under（“校园校园”，“钟山钟山”）Located-inside（“建筑物建

49、筑物”，“校园校园”）Located-at（“理工大学理工大学”，“海福港海福港”）Similar-to（“校园校园”，“公园公园”）Fetch（“校园校园”，“风景美丽风景美丽”）A-Member-of（“张三张三”，“学会学会”）A-kind-of（“图书馆图书馆”，“建筑物建筑物”）A-part-of（“阅览室阅览室”，“图书馆图书馆”）Is-a（“理工大学理工大学”，“单位单位”）Is-a（“张三张三”，“读者读者”）Owner（“图书馆图书馆”，“理工大学理工大学”）Near-to（“图书馆图书馆”，“大礼堂大礼堂”）Have（“阅览室阅览室”，“读者读者”）After（“阅览阅览”

50、，“开放开放”）Can（“张三张三”，“讲英语讲英语”）Can（“阅览室阅览室”，“开放开放”）Can（“读者读者”，“阅览阅览”）用用Prolog语言表示：语言表示：三、语义网络的推理三、语义网络的推理1、匹配、匹配阅览室阅览室图书馆图书馆 A-part-of读者读者?Have Can第五节第五节 语义网络表达法语义网络表达法信息学院信息学院张山张山 学习学习计算机系计算机系健祥桥健祥桥 Located-at湖南湖南通信系通信系信息系信息系与与 籍贯籍贯 Composed-ofx张山张山 学习学习y Located-at湖南湖南 籍贯籍贯第五节第五节 语义网络表达法语义网络表达法2、继承、继