高级人工智能课件2.ppt

1、人工智能人工智能Artificial Intelligence第二章第二章 知识表示与推理知识表示与推理2.1 知识表示的一般方法2.2 图搜索策略2.3 一般搜索与推理技术2.4 A*算法2.5 消解原理2.6 规则演义系统2.7 产生式系统2.8 系统组织技术2022-12-5安徽大学 计算机科学与技术学院32.1 n 一般计算机科学n数据结构+算法n 人工智能n(知识表示+搜索)+推理2022-12-5安徽大学 计算机科学与技术学院42.1 n 问题求解技术主要是两个方面：n问题的表示n求解的方法n 状态空间法n状态（state）n算符（operator）n状态空间方法2022-12-5

2、安徽大学 计算机科学与技术学院52.1 n 问题规约法n大问题化为若干小问题n本原问题n 谓词逻辑法n合式公式n消解算法(归结)2022-12-5安徽大学 计算机科学与技术学院62.1 n 语义网络法n结点表示概念n弧表示关系n 框架法n槽、侧面层次结构n框架可以嵌套框架2022-12-5安徽大学 计算机科学与技术学院72.1 n 剧本n场景n角色n事件n 过程n问题求解的算法2022-12-5安徽大学 计算机科学与技术学院82.2 图搜索策略图搜索策略n图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统

3、的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。n图搜索过程图2022-12-5安徽大学 计算机科学与技术学院92.2 图图搜搜索索策策略略开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表表中中，提供返回节点提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功是是是是否否否否2022-12-5安徽大学 计算机科学与技术学院102.3 一般搜索与推理技术一

4、般搜索与推理技术盲目搜索n特点：不需重排OPEN表n种类：宽度优先、深度优先、等代价搜索等。启发式搜索n特点：重排OPEN表，选择最有希望的节点加以扩展；估价函数n种类：有序搜索、A*算法、AO*算法等2022-12-5安徽大学 计算机科学与技术学院112.4 A*算法1、为什么需要启发式搜索、为什么需要启发式搜索 盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。2、定义、定义 进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。2022-12-5安徽大学 计算机科学与技术学院122.4 A*算法3、启发

5、式搜索策略、启发式搜索策略 有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。2022-12-5安徽大学 计算机科学与技术学院132.4 A*算法4、估价函数、估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 建立估价函数的

6、一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。2022-12-5安徽大学 计算机科学与技术学院142.4 A*算法n估价函数的定义：对节点n定义f*(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n)g是g*的估计，h是h*的估计nA*算法的定义：定义定义1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行

7、的，则称该过程为A算法。定义定义2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当g=0时，A*算法就变为有序搜索算法；h=0时，A*算法就变为等代价搜索算法。2022-12-5安徽大学 计算机科学与技术学院152.4 A*算法开始开始把把S放入放入OPEN表，估价函数表，估价函数 f=hOPEN=NIL？选取选取OPEN表中未设置过的、表中未设置过的、f值最小的节值最小的节点点BESTNODE放入放入CLOSED表表BESTNODE为目标节点吗？为目标节点

8、吗？计算计算g(SUC)=g(BES)+k(BES,SUC)失败失败成功成功是是否否是是否否扩展扩展BESTNODE，产生后继节点，产生后继节点SUCCESSOR建立从建立从SUCCESSOR返回返回BESTNODE的指针的指针AB 2022-12-5安徽大学 计算机科学与技术学院162.4 A*算法SUC OPEN？SUC是是OLD的复本的复本,把把OLD添加添加到到BESTNODE的后继节点表中的后继节点表中g(SUC)g(OLD)？计算计算f值值是是否否是是否否重新确定重新确定OLD的父辈节点为的父辈节点为BESTNODE，并修正父辈节点的并修正父辈节点的g值和值和f值，记下值，记下g(

9、OLD)把把SUCCESSOR放入放入OPEN表，表，并加入并加入BESTNODE的后裔表的后裔表ABSUC=CLOSED=CLOSED？A否否是是2022-12-5安徽大学 计算机科学与技术学院17实验实验1 A*算法实验算法实验 例子:八数码难题（8-puzzle problem）1238456712384567（目标状态）规定：牌可以移入邻近的空格，不许斜向移动，也不返回先辈节点。12384567（初始状态）2022-12-5安徽大学 计算机科学与技术学院18实验实验1 A*算法实验算法实验 n实验内容：实验内容：n用A*算法求解8数码和15数码难题n实验报考要求实验报考要求n画出A*算

10、法求解流程图，给出核心程序。n画出8数码求解图n分析估价函数对搜索算法的影响。n分析A*算法的特点。2022-12-5安徽大学 计算机科学与技术学院192.5 消解原理消解原理回顾：原子公式原子公式（atomic formulas）P(x),Q(x,y)文字文字一个原子公式及其否定。P(x),R(x,y,z)子句子句由文字的析取组成的合适公式。P(x)Q(x,y)消解消解对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。2.5.1 子句集的求取v 步骤：共9步。2022-12-5安徽大学 计算机科学与技术学院20v 例子:将下列谓词演算公式化为一个子句集(x)P(x)(y)P(y)P

11、(f(x,y)(y)Q(x,y)P(y)开始：(1)消去蕴涵符号 只应用和符号，以AB替换A AB B。(1)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)2022-12-5安徽大学 计算机科学与技术学院21(2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3)对变量标准化 对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。(2)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(3)(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)2022-12-5安徽大学 计算机科学与技术学院22

12、(4)消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词(5)化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀 母式 全称量词串 无量词公式(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，式中，w=g(x)w=g(x)为一为一SkolemSkolem函数。函数。(5)(5)(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)2022-12-5安徽大学 计算机科学与技术学院23(6)把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取

13、的有限集组成的合取。(7)消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。(6)(6)(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)2022-12-5安徽大学 计算机科学与技术学院24(8)消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。(8)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(

14、g(x)(9)P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3)2022-12-5安徽大学 计算机科学与技术学院252.5.2 消解推理规则消解推理规则n消解式的定义令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。v 消解式求法取两个子句，进行析取，然后消去互补对。2022-12-5安徽大学 计算机科学与技术学院262.5.2 消解推理规则消解推理规则PP QQ1、假言推理2、合并P Q P QQ3、

15、重言式P Q P QTP P QQ5、三段论 P Q Q RP R4、矛盾PP F2022-12-5安徽大学 计算机科学与技术学院272.5.3 含有变量的消解式 要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。v 含有变量的子句之消解式v 例2.1 B(x)B(x)C(x)C(x)2022-12-5安徽大学 计算机科学与技术学院282.5.3 含有变量的消解式v 例2.3Px,f(y)Q(x)Rf(a),y Pf(f(a),zR(z,w)Q f(f(a)R(f(a),y)R(f(y),w)=f(f(a)/x,f(y)/zv 例2.2 P(x)Q

16、(x)Qf(y)P f(y)=f(y)/x2022-12-5安徽大学 计算机科学与技术学院292.5.4 消解反演求解过程n消解反演 给出S，Ln否定L，得L；n把L添加到S中去；n把新产生的集合L，S化成子句集；n应用消解原理，力图推导出一个表示矛盾的空子句v 例子储蓄问题 前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱2022-12-5安徽大学 计算机科学与技术学院302.5.4 消解反演求解过程(1）规定原子公式：S(x,y)S(x,y)表示“x储蓄y”M(x)M(x)表示“x是钱”I(x)I(x)表示“x是利息”E(xE(x，y)y)表示“x获得y”(2）用谓

17、词公式表示前提和结论：前提：前提：(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)结论：结论：(x)I(x)(x)(y)M(y)S(x,y)(3)化为子句形证明证明：2022-12-5安徽大学 计算机科学与技术学院31把前提化为子句形：1)S(x,y)M(y)I(f(x)2)S(x,y)M(y)E(x,f(x)把结论化为子句形：3)I(z)4)S(a,b)5)M(b)(4)消解反演求NIL图3.12 储蓄问题反演树子句（1）子句（3）f(x)/zM(b)NIL子句（5）子句（7）子句（4）a/x,b/yS(x,y)M(y)子句子句（6）(x)I(x)(x)(y)M(y)S(x,y

18、)(x)I(x)(x)(y)M(y)S(x,y)否定：(x)I(x)(x)(y)S(x,y)(x)I(x)(x)(y)M(y)S(x,y)2022-12-5安徽大学 计算机科学与技术学院32n反演求解过程反演求解过程n从反演树求取答案步骤从反演树求取答案步骤n把由目标公式的否定产生的每个子句添加到目把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。标公式否定之否定的子句中去。n按照反演树，执行和以前相同的消解，直至在按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。根部得到某个子句止。n用根部的子句作为一个回答语句。用根部的子句作为一个回答语句。n 实质实质n把一棵

19、根部有把一棵根部有NILNIL的反演树变换为根部带有回的反演树变换为根部带有回 答语答语句的一棵证明树。句的一棵证明树。2022-12-5安徽大学 计算机科学与技术学院33应用消解反演求解如下问题：应用消解反演求解如下问题：无论约翰无论约翰(John)到哪里去，菲多到哪里去，菲多(Fido)也就去那里，也就去那里，那么如果约翰在学校里，菲多在哪里呢那么如果约翰在学校里，菲多在哪里呢?x在在y:AT(x,y)用谓词公式表示前提和结论用谓词公式表示前提和结论：前提：前提：(x)AT(JOHN,x)AT(FIDO,x)AT(JOHN,SCHOOL)结论：结论：(x)AT(FIDO,x)结论的否定结论

20、的否定：AT(FIDO,x)2022-12-5安徽大学 计算机科学与技术学院34化为子句集：化为子句集：AT(JOHN,x)AT(FIDO,x)AT(JOHN,SCHOOL)AT(FIDO,x)AT(JOHN,y)AT(FIDO,y)AT(FIDO,x)AT(JOHN,x)x/yAT(JOHN,SCHOOL)NILSCHOOL/xAT(JOHN,y)AT(FIDO,y)AT(FIDO,x)AT(FIDO,x)AT(JOHN,x)AT(FIDO,x)x/yAT(JOHN,SCHOOL)AT(FIDO,SCHOOL)SCHOOL/x2022-12-5安徽大学 计算机科学与技术学院35 猴子和香蕉问

21、题猴子和香蕉问题2022-12-5安徽大学 计算机科学与技术学院36 ONBOX(S0)，AT(box,b,S0)，AT(monkey,a,S0)，HB(S0)pushbox(x,S)：在状态：在状态S下，下，猴子把箱子推到水平位置猴子把箱子推到水平位置xclimbbox(S)：在状态：在状态S下，下，猴子爬上箱顶猴子爬上箱顶grasp(S)：在状态：在状态S下，下，猴子摘到香蕉猴子摘到香蕉2022-12-5安徽大学 计算机科学与技术学院37(1)(x)(S)ONBOX(S)AT(box,x,pushbox(x,S)(2)(S)ONBOX(climbbox(S)(3)(S)ONBOX(S)AT

22、(box,c,S)HB(grasp(S)(4)(x)(S)AT(box,x,S)AT(box,x,climbbox(S)(5)ONBOX(S0)(6)(S)HB(S)要证的结论要证的结论2022-12-5安徽大学 计算机科学与技术学院38(1)ONBOX(S)AT(box,x,pushbox(x,S)(2)ONBOX(climbbox(S)(3)ONBOX(S)AT(box,c,S)HB(grasp(S)(4)AT(box,x,S)AT(box,x,climbbox(S)(5)ONBOX(S0)(6)目标的非：目标的非：HB(S)2022-12-5安徽大学 计算机科学与技术学院39(1)ONB

23、OX(S1)AT(box,x,pushbox(x,S1)(2)ONBOX(climbbox(S2)(3)ONBOX(S3)AT(box,c,S3)HB(grasp(S3)(4)AT(box,x,S4)AT(box,x,climbbox(S4)(5)ONBOX(S0)(6)目标的非：目标的非：HB(S5)2022-12-5安徽大学 计算机科学与技术学院40HB(S5)ONBOX(S3)AT(box,c,S3)HB(grasp(S3)ONBOX(S3)AT(box,c,S3)grasp(S3)/S5ONBOX(climbbox(S2)climbbox(S2)/S3AT(box,c,climbbox

24、(S2)AT(box,x,S4)AT(box,x,climbbox(S4)S4/S2,c/xONBOX(S0)AT(box,c,S4)ONBOX(S1)AT(box,x,pushbox(x,S1)pushbox(x,S1)/S4,c/xONBOX(S1)S0/S1NIL2022-12-5安徽大学 计算机科学与技术学院41HB(S5)HB(S5)ONBOX(S3)AT(box,c,S3)HB(grasp(S3)HB(grasp(S3)ONBOX(S3)AT(box,c,S3)grasp(S3)/S5ONBOX(climbbox(S2)climbbox(S2)/S3HB(grasp(climbbo

25、x(S2)AT(box,c,climbbox(S2)AT(box,x,S4)AT(box,x,climbbox(S4)S4/S2,c/xONBOX(S0)HB(grasp(climbbox(S4)AT(box,c,S4)ONBOX(S1)AT(box,x,pushbox(x,S1)pushbox(x,S1)/S4,c/xHB(grasp(climbbox(pushbox(c,S1)ONBOX(S1)S0/S12022-12-5安徽大学 计算机科学与技术学院42实验实验2 子句消解实验子句消解实验 一、实验目的：一、实验目的：理解含有变量的子句如何使用消解规则，掌握子句消解的原理和规则，能熟练进

26、行任意两个子句的消解，了解消解推理的某些常用规则。二、实验原理：二、实验原理：对子句集进行消解推理，得到相应的结论。为了对含有变量的子句使用消解规则，我们必须找到一个置换，作用于父辈子句使其含有互补文字。消解两个子句时，可能有一个以上的消解式。三、实验条件三、实验条件 硬件：微型计算机。任选一种流行语言。2022-12-5安徽大学 计算机科学与技术学院43实验实验2 子句消解实验子句消解实验 四、实验内容：四、实验内容：编写消解程序。输入子句，检查消解结果。根据消解过程理解消解原理和常用规则。五、实验步骤五、实验步骤(2-3人一组人一组)：1.语法分析程序，产生文字集合；2.两个文字集合进行消

27、解，结果为新的文字集合；3.用户界面设计；4.分析消解过程，写消解实验报告。（每人）2022-12-5安徽大学 计算机科学与技术学院442.6 n 定义定义 基 于 规 则 的 问 题 求 解 系 统 运 用基 于 规 则 的 问 题 求 解 系 统 运 用IfThen规则来建立，每个规则来建立，每个if可能与某断言可能与某断言(assertion)集中的一个或多个断言匹配。有时集中的一个或多个断言匹配。有时把该断言集称为工作内存把该断言集称为工作内存(黑板黑板)，then部分用部分用于规定放入工作内存的新断言。这种基于规则于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种

28、系统中，通的系统叫做规则演绎系统。在这种系统中，通常称每个常称每个if部分为前项，称每个部分为前项，称每个then部分为后部分为后项。项。2022-12-5安徽大学 计算机科学与技术学院452.6.1 规则正向演绎系统n定义 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。n求解过程n事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。2022-12-5安徽大学 计算机科学与技术学院461.事实表达式的与或形变换事实表达式的与或形变换例如：例如：(u)(v)Q(v,u)(R(

29、v)P(v)S(A,v)表示为非蕴涵形式的与或形：A/uQ(v,A)R(v)P(v)S(A,v)2.6.1 规则正向演绎系统2022-12-5安徽大学 计算机科学与技术学院472.事实表达式的与或图表示Q(v,A)R(v)P(v)S(A,v)Q(v,A)R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)图2.8 一个事实表达式的与或树表示子句集：子句集：Q(v,A)R(v)S(A,v)P(v)S(A,v)换名：换名：Q(w,A)R(v)S(A,v)P(x)S(A,x)2022-12-5安徽大学 计算机科学与技术学院48与或图的F规则变换 这些规则是建立在某个问题辖域中普通

30、陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：L W 式中：L是单文字；W为与或形的唯一公式。下面的证明限定：目标是可以证明的，目标是析取关系下面的证明限定：目标是可以证明的，目标是析取关系2.6.1 规则正向演绎系统2022-12-5安徽大学 计算机科学与技术学院49例如：例如：(x)(y)(z)P(x,y,z)(u)Q(x,u)1)暂时消去蕴涵符号暂时消去蕴涵符号：(x)(y)(z)P(x,y,z)(u)Q(x,u)2)减小否定符号的辖域减小否定符号的辖域：(x)(y)(z)P(x,y,z)(u)Q(x,u)3)进行进行Skolem标准化标准化：(x)(y)P(

31、x,y,f(x,y)(u)Q(x,u)4)换名并消去全称量词换名并消去全称量词：P(x,y,f(x,y)Q(x,u)5)恢复蕴涵式恢复蕴涵式：P(x,y,f(x,y)Q(x,u)2022-12-5安徽大学 计算机科学与技术学院50(PQ)R S(TU)PQ(PQ)RTUPQRS(TU)STU图图2.9 不含变量的与或图不含变量的与或图2022-12-5安徽大学 计算机科学与技术学院51(PQ)R S(TU)PQ(PQ)RTUPQRS(TU)STU图图2.10 应用应用L W规则得到的与或图规则得到的与或图SXYZXYP Q X ZP Q Y ZR X ZR Y Z2022-12-5安徽大学 计

32、算机科学与技术学院52(AB)事实事实:AB 规则规则:A CD,B EG 目标目标:CG(析取析取)CDCAABBEGGAC CG BGABABBNIL结论：以目标节点作为终止解图时，系统成功终止。结论：以目标节点作为终止解图时，系统成功终止。2022-12-5安徽大学 计算机科学与技术学院532.6.2 规则逆向演绎系统n定义 逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。n求解过程n目标表达式的与或形式n与或图的B规则变换,WL,L是单文字；W为与或形的公式n作为终止条件的事实节点的一致解图2022-12-5安徽大学 计算机科学与技术学院542.

33、6.2 2.6.2 规则逆向演绎系统规则逆向演绎系统例如：(y)(x)P(x)Q(x,y)P(x)S(y)化成与或形：P(f(y)Q(f(y),y)P(f(y)S(y)P(f(y)Q(f(y),y)P(f(y)S(y)Q(f(y),y)P(f(y)S(y)P(f(y)P(f(y)S(y)Q(f(y),y)S(y)P(f(y)目标子句是文字的目标子句是文字的合取合取：P(f(z)Q(f(y),y)P(f(y)Q(f(x),x)S(x)2022-12-5安徽大学 计算机科学与技术学院55例：F1:DOG(FIDO)；狗的名字叫狗的名字叫FidoF2:BARKS(FIDO)；Fido不叫的不叫的F3

34、:WAGS-TAIL(FIDO)；Fido摇尾巴摇尾巴F4:MEOWS(MYRTLE)；猫咪的名字叫猫咪的名字叫MyrtleR1:WAGS-TAIL(x1)DOG(x1)FRIENDLY(x1)；摇尾巴的狗是温顺的狗摇尾巴的狗是温顺的狗R2:FRIENDLY(x2)BARKS(x2)AFRAID(y2,x2)；温顺而不叫的东西是不值得害怕的温顺而不叫的东西是不值得害怕的R3:DOG(x3)ANIMAL(x3)；狗是动物狗是动物R4:CAT(x4)ANIMAL(x4)；猫是动物猫是动物R5:MEOWS(x5)CAT(x5)；猫咪是猫猫咪是猫问题：问题：是否是否存在存在一只猫和一条狗，使得这只猫不

35、怕这条狗（一只猫和一条狗，使得这只猫不怕这条狗（找到找到一只不怕狗的猫）？一只不怕狗的猫）？(x)(y)CAT(x)DOG(y)AFRAID(x,y)2022-12-5安徽大学 计算机科学与技术学院56CAT(x)DOG(y)AFRAID(x,y)CAT(x)DOG(y)AFRAID(x,y)WAGS-TAIL(FIDO)DOG(FIDO)DOG(y)AFRAID(y2,x2)FRIENDLY(y)AFRAID(x,y)WAGS-TAIL(y)FIDO/yFIDO/yBARKS(FIDO)MEOWS(MYRTLE)y/x1FIDO/yMYRTLE/xR1DOG(FIDO)FIDO/yBARKS

36、(y)x/y2,y/x2R2MEOWS(x)CAT(x5)x/x5R52022-12-5安徽大学 计算机科学与技术学院57 正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。2.6.3 规则双向演绎系统2022-12-5安徽大学 计算机科学与技术学院582.7 产生式系统n定义定义：用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。n实质：实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它

37、们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。2022-12-5安徽大学 计算机科学与技术学院592.7.1 产生式系统的组成控制策略图3.22 产生式系统的主要组成总数据库产生式规则一个产生式系统由下列一个产生式系统由下列3 3部分组成：部分组成：一个总数据库一个总数据库(global database)，它含有与具体任务有关的信息。，它含有与具体任务有关的信息。一套规则一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述

38、规则应用时所完成的左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。动作。应用规则来改变数据库。一个控制策略一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。终止条件满足时，就停止计算。2022-12-5安徽大学 计算机科学与技术学院60n选择规则到执行操作的步骤 1 匹配 把当前数据库与规则的条件部分相匹配。2 冲突 当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。3 操作 操作就是执行规则的操作部分。2022-12-5安徽大学

39、计算机科学与技术学院612.7.2 产生式系统的推理 n正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。n逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。n双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。2022-12-5安徽大学 计算机科学与技术学院62实验实验3 产生式系统实验产生式系统实验 一、实验目的：一、实验目的：熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。二、实验原理：二、实验原理：产生式系统用来描述若干个不同的以一个基本概念为基础的系统，这个基本概念就是产生式规则或产生式条件和操作对。在产生式系统中，论域的知识分为两部分：用事实表示静态知识；用产生式规则表示推理过程和行为。三、实验条件三、实验条件 硬件：微型计算机。任选一种流行语言。