知识的产生式系统表示方法

1、第二章 知识的产生式系统表示法计算机科学与技术学院计算机科学与技术学院 陈峰陈峰第第2 2页页【本章重点本章重点 】知识及知识表示的概念；产生知识及知识表示的概念；产生式表示法；产生式系统的问题求解过程。式表示法；产生式系统的问题求解过程。【本章难点本章难点 】产生式表示事实和规则的方法产生式表示事实和规则的方法；产生式系统的问题求解过程；产生式系统的问题求解过程第第3 3页页知识表示的方法：知识表示的方法：|产生式表示法产生式表示法|一阶谓词逻辑表示法一阶谓词逻辑表示法|语义网络表示法语义网络表示法|框架表示法框架表示法|脚本表示法脚本表示法|过程表示法过程表示法|面向对象表示法面向对象表示

2、法|不确定性知识的表示方法不确定性知识的表示方法第第4 4页页2.1 知识与知识表示的概念知识与知识表示的概念一一 、知识、知识 （一）什么是知识（一）什么是知识 知识知识是人们在改造客观世界的实践中积累起来是人们在改造客观世界的实践中积累起来的认识和经验。的认识和经验。 数据数据是指人们为了描述客观世界中的具体事物是指人们为了描述客观世界中的具体事物而引人的一些数字、字符、文字等符号或符号的组而引人的一些数字、字符、文字等符号或符号的组合。合。 信息信息是指用不同数据组成的一种结构。是指用不同数据组成的一种结构。第第5 5页页数据和信息是两个密切相关的概念。数据是信息的数据和信息是两个密切相

3、关的概念。数据是信息的载体和表示，信息是数据在特定场合下的含义，或载体和表示，信息是数据在特定场合下的含义，或者说信息是数据的语义。同样，同一条信息在不同者说信息是数据的语义。同样，同一条信息在不同场合又可用不向的数据来表示。场合又可用不向的数据来表示。信息仅是对客观事物的一般性描述，它还不是知识信息仅是对客观事物的一般性描述，它还不是知识。只有经过对其进行挑选、加工、整理、和解释，。只有经过对其进行挑选、加工、整理、和解释，形成对客观世界的规律性认识后才能称为知识。形成对客观世界的规律性认识后才能称为知识。2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）第第6 6页页 知识最有代

4、表性的三个定义：知识最有代表性的三个定义： 知识是经过消减、塑造、解释、选择和转换的信息知识是经过消减、塑造、解释、选择和转换的信息 知识是由特定领域的描述、关系和过程组成的。知识是由特定领域的描述、关系和过程组成的。 知识事实十信念十启发式。知识事实十信念十启发式。2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）第第7 7页页（二）（二） 知识的属性知识的属性 1 1、真假性与相对性、真假性与相对性真假性真假性是指可以通过实践或推理来证明知识为真或是指可以通过实践或推理来证明知识为真或为假。为假。相对性相对性是指知识的真与假是相对于某些条件、环境是指知识的真与假是相对于某些条件、

5、环境及时间而言的，即知识一般不是无条件的真或无条及时间而言的，即知识一般不是无条件的真或无条件的假，而是相对于一定环境条件的。件的假，而是相对于一定环境条件的。2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）第第8 8页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）2、不确定性、不确定性 知识的不完备性知识的不完备性是指在解决问题时不具备解决是指在解决问题时不具备解决该问题所需要的全部知识。知识的不完备性又可能该问题所需要的全部知识。知识的不完备性又可能会导致知识的不确定性和模糊性。会导致知识的不确定性和模糊性。 知识的不确定性知识的不确定性是指知识所具有的既不能完

6、全是指知识所具有的既不能完全被确定为真，又不能完全被确定为假的特性。被确定为真，又不能完全被确定为假的特性。 知识的模糊性知识的模糊性是指知识的是指知识的“边界边界”不明确的特不明确的特性。性。第第9 9页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）3、 矛盾性和相容性矛盾性和相容性矛盾性矛盾性是指同一个知识集中的不同知识之间相互对是指同一个知识集中的不同知识之间相互对立或不一致，即从这些知识出发，会推出不一致的立或不一致，即从这些知识出发，会推出不一致的结论。结论。相容性相容性是指同一个知识集中的所有知识之间相互矛是指同一个知识集中的所有知识之间相互矛盾。盾。相容性也称为知

7、识的一致性，即从这些知识出发不相容性也称为知识的一致性，即从这些知识出发不应该推出一个命题和该命题的否定都是真的，也就应该推出一个命题和该命题的否定都是真的，也就是说不能从中推出一对互相予盾的结论。是说不能从中推出一对互相予盾的结论。第第1010页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）4、可表示性与可利用性、可表示性与可利用性可表示性可表示性是指知识可以用适当的形式表示出来。是指知识可以用适当的形式表示出来。可利用性可利用性是指知识可以被用来解决各种各样的问题。是指知识可以被用来解决各种各样的问题。第第1111页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（

8、续）（三）知识的分类（三）知识的分类(1) 按知识的性质按知识的性质 知识可分为概念、命题、公理、定理、规则和方法等。知识可分为概念、命题、公理、定理、规则和方法等。(2) 按知识的作用范围按知识的作用范围 知识可分为常识性知识和领域性知识。知识可分为常识性知识和领域性知识。(3) 按知识的作用按知识的作用 知识可分为事实性知识、过程性知识和控制性知识。知识可分为事实性知识、过程性知识和控制性知识。(4) 按知识的层次按知识的层次 知识可分为表层知识和深层知识。知识可分为表层知识和深层知识。 第第1212页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）(5) 按知识的确定性按知

9、识的确定性 知识可分为确定性知识和不确定性知识。知识可分为确定性知识和不确定性知识。(6) 按知识的等级按知识的等级 知识可分为零级知识、一级知识、二级知识等。知识可分为零级知识、一级知识、二级知识等。(7) 按知识的结构及表现形式按知识的结构及表现形式 知识可分为逻辑性知识和形象性知识。知识可分为逻辑性知识和形象性知识。第第1313页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）二二 、知识的表示、知识的表示（一）什么是知识表示（一）什么是知识表示 知识表示知识表示实际上就是对知识的实际上就是对知识的种描述，即用种描述，即用一些约定的符号把知识编码成一组计算机可以接受一些约定

10、的符号把知识编码成一组计算机可以接受的数据结构。的数据结构。 知识表示过程知识表示过程就是把知识编码成某种数据结构就是把知识编码成某种数据结构的过程。的过程。第第1414页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）（二）知识表示的要求（二）知识表示的要求(1) 表示能力表示能力 知识表示能力是指能否正确、有效地将问题求解所需要知识表示能力是指能否正确、有效地将问题求解所需要的各种知识表示出来。的各种知识表示出来。 知识表示能力包括以下三个方面：一是知识表示范围的知识表示能力包括以下三个方面：一是知识表示范围的广泛性；二是领域知识表示的高效性；三是对非确定性知识广泛性；二是领

11、域知识表示的高效性；三是对非确定性知识表示的支持程度。表示的支持程度。第第1515页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）(2) 可利用性可利用性 知识的利用知识的利用是指使用知识进行推理，以求得问题的解。知是指使用知识进行推理，以求得问题的解。知识的可利用性包括对推理的适应性和对高效算法的支持性。识的可利用性包括对推理的适应性和对高效算法的支持性。 推理推理是指根据问题的已知事实，通过使用存储在计算机中是指根据问题的已知事实，通过使用存储在计算机中的知识推出新的事实的知识推出新的事实(或结论或结论)或执行某个操作的过程。或执行某个操作的过程。(3) 可组织性与可维护性

12、可组织性与可维护性 知识的组织知识的组织是指把有关知识按照某种方式组成一种知识是指把有关知识按照某种方式组成一种知识结构。结构。 知识维护知识维护是指在保证知识的一致性与完整性的前提下对是指在保证知识的一致性与完整性的前提下对知识所进行的增加、删除、修改等操作。知识所进行的增加、删除、修改等操作。第第1616页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）(4) 可实现性可实现性 可实现性可实现性是指知识表示要便于在计算机上实现，便于直是指知识表示要便于在计算机上实现，便于直接由计算机对其进行处理。接由计算机对其进行处理。(5) 自然性与可理解性自然性与可理解性 自然性自然性是

13、指知识表示形式要符合人们的日常习惯和思维是指知识表示形式要符合人们的日常习惯和思维方式。方式。第第1717页页2.1 知识与知识表示的概念（续）知识与知识表示的概念（续）（三）（三） 知识表示观点知识表示观点1、陈述性观点、陈述性观点 陈述性知识表示是指以陈述的方式把知识用一定的数据陈述性知识表示是指以陈述的方式把知识用一定的数据结构表示出来，即把知识看作一种特殊的数据结构、知识表结构表示出来，即把知识看作一种特殊的数据结构、知识表示仅说明描述的对象是什么，不涉及如何运用知识的问题。示仅说明描述的对象是什么，不涉及如何运用知识的问题。 2、过程性观点、过程性观点 过程性知识表示是指以程序过程性

14、知识表示是指以程序(亦称为过程亦称为过程)的方式把知识的方式把知识表示出来，即把知识寓于程序之中，把知识表示和运用知识表示出来，即把知识寓于程序之中，把知识表示和运用知识结合起来。结合起来。第第1818页页2.2 产生式知识表示和产生式系统产生式知识表示和产生式系统“产生式产生式”(production system)首先是由波斯特首先是由波斯特(Post)于于1943年提出的产生式规则年提出的产生式规则(production rule)而得名的。而得名的。60年代，成为专家系统的基本结构。年代，成为专家系统的基本结构。形式上很简单，但在一定意义上模仿了人类思考的过程。形式上很简单，但在一定意

15、义上模仿了人类思考的过程。第第1919页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）一、产生式表示的基本方法及特性一、产生式表示的基本方法及特性1. 事实的表示事实的表示 事实可看作是断言一个语言变量的值或断言多个语言变事实可看作是断言一个语言变量的值或断言多个语言变量之间关系的陈述句。量之间关系的陈述句。 在产生式表示法中，事实通常是用三元组或四元组来表在产生式表示法中，事实通常是用三元组或四元组来表示的。示的。对确定性知识，一个事实可用一个三元组对确定性知识，一个事实可用一个三元组 (对象，属性，值对象，属性，值) 或或 (关系，对象关系，对象1，对象，对象2

16、)来表示。来表示。第第2020页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）2. 规则的表示规则的表示 规则描述的是事物间的因果关系。规则的产生式表示形规则描述的是事物间的因果关系。规则的产生式表示形式常称为产生式规则，简称产生式或规则。式常称为产生式规则，简称产生式或规则。 其基本形式为：其基本形式为： IF 条件条件 THEN 结论结论例如例如 ：有规则：有规则 IF（如果）（如果） 动物有犬齿动物有犬齿 AND 有爪有爪 AND 眼盯前方眼盯前方 THEN（那么）（那么） 这种动物为食肉动物这种动物为食肉动物第第2121页页2.2 产生式知识表示和产生式系统

17、（续）产生式知识表示和产生式系统（续）产生式与蕴含式的区别产生式与蕴含式的区别 (1) 蕴含式只能表示确定性知识，其真值只能取真或假，而蕴含式只能表示确定性知识，其真值只能取真或假，而产生式不仅可以表示确定性知识，而且还可以表示不确定性产生式不仅可以表示确定性知识，而且还可以表示不确定性知识。知识。 (2) 在产生式表示中，决定一个产生式是否可用是通过检查在产生式表示中，决定一个产生式是否可用是通过检查已知事实是否与前提中所规定的条件相匹配来实现的，并且已知事实是否与前提中所规定的条件相匹配来实现的，并且匹配可以是精确的，也可以是不精确的。而谓词逻辑中的蕴匹配可以是精确的，也可以是不精确的。而

18、谓词逻辑中的蕴含式，其匹配则要求一定是精确的。也就是说，要满足相应含式，其匹配则要求一定是精确的。也就是说，要满足相应的真值表。的真值表。第第2222页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）二、产生式系统的组成二、产生式系统的组成产生式系统由三部分组成即总数据库产生式系统由三部分组成即总数据库(或全局数据库或全局数据库)、产、产生式规则和控制策略。生式规则和控制策略。第第2323页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）1. 总数据库总数据库 总数据库有时也称为上下文、当前数据库或暂时存储器。总数据库有时也称为上下文、当前数

19、据库或暂时存储器。总数据库是产生式规则的注意中心。产生式规则的左边表示总数据库是产生式规则的注意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。在启用这一规则之前总数据库内必须准备好的条件。第第2424页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）（二）（二） 控制策略控制策略1、 控制策略的任务控制策略的任务 控制策略为一个推理机构，由一组程序组成，用来控制产控制策略为一个推理机构，由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路，实现对问生式系统的运行，决定问题求解过程的推理线路，实现对问题的求解。其主要任务如下：题

20、的求解。其主要任务如下： 按一定策略从规则库中选择与总数据库中的已知事实按一定策略从规则库中选择与总数据库中的已知事实相匹配的规则。即把所选规则的前提与总数据库中的已知事相匹配的规则。即把所选规则的前提与总数据库中的已知事实进行比较，若事实与所选规则前提一致，则匹配成功，该实进行比较，若事实与所选规则前提一致，则匹配成功，该规则激活被使用；否则，匹配失败，该规则不可用于当前推规则激活被使用；否则，匹配失败，该规则不可用于当前推理。理。第第2525页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续） 当存在多条匹配成功的规则时，控制策略能够按照某种当存在多条匹配成功的规则

21、时，控制策略能够按照某种策略从中选出一条合适的规则去执行。策略从中选出一条合适的规则去执行。 如果要执行规则的右部不是问题的目标，且为一个或多如果要执行规则的右部不是问题的目标，且为一个或多个结论时，则把这些结论加入到总数据库中；当其为一个或个结论时，则把这些结论加入到总数据库中；当其为一个或多个操作时，执行这些操作。多个操作时，执行这些操作。 如果要执行规则的右部满足问题的结束条件，则停止推如果要执行规则的右部满足问题的结束条件，则停止推理。理。 记住问题求解过程应用过的规则序列，以便求解结束时记住问题求解过程应用过的规则序列，以便求解结束时能够给出问题的解题路径。能够给出问题的解题路径。

22、第第2626页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）2、控制策略的实施过程、控制策略的实施过程控制策略的作用是说明下一步应该选用什么规则，也就是说控制策略的作用是说明下一步应该选用什么规则，也就是说如何应用规则。通常从选择规则到执行操作分三步：匹配、如何应用规则。通常从选择规则到执行操作分三步：匹配、冲突解决和操作。冲突解决和操作。第第2727页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）匹配匹配在这一步，把当前数据库与规则的条件部分相匹配。如果两在这一步，把当前数据库与规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触

23、发规则。当按规则的操作者完全匹配，则把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规则。被触发的规则不一部分去执行时，称这条规则为启用规则。被触发的规则不一定总是启用规则，因为可能同时有几条规则的条件部分被满定总是启用规则，因为可能同时有几条规则的条件部分被满足，这就要在解决冲突步骤中来解决这个问题。在复杂情况足，这就要在解决冲突步骤中来解决这个问题。在复杂情况下，在数据库和规则的条件部分之间可能要进行近似匹配。下，在数据库和规则的条件部分之间可能要进行近似匹配。第第2828页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）冲突解决冲突解决 当有

24、一条以上规则的条件部分和当前数据库相匹配时，就当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪些规则，这称为冲突解决。需要决定首先使用哪些规则，这称为冲突解决。例如，设在美式足球例如，设在美式足球(即橄榄球即橄榄球)比赛中有以下两条规则：比赛中有以下两条规则： 规则规则 R1 IF fourth dawn Short yardage THEN punt 规则规则 R2 IF fourth dawn Short yardage within 30 yards (from the goal line) THEN field goal 第第2929页页2.2 产生式知识表示和产生

25、式系统（续）产生式知识表示和产生式系统（续）操作操作操作就是执行规则的操作部分，经过操作后，当前数据库将操作就是执行规则的操作部分，经过操作后，当前数据库将被修改。然后，有可能使用其它规则。被修改。然后，有可能使用其它规则。第第3030页页第第3131页页第第3232页页第第3333页页第第3434页页第第3535页页第第3636页页(1)(1)综合数据库综合数据库: :用三元组表示用三元组表示, , 即即(ML, CL, BL), (ML, CL, BL), 其其中中0ML, CL3, BL0, 1 0ML, CL3, BL0, 1 此时问题述简化为此时问题述简化为N=3N=3的的M-CM-

26、C问题问题, , 状态空间的总状态数状态空间的总状态数为为4 44 42=32, 2=32, 根据约束条件的要求根据约束条件的要求, , 可以看出只有可以看出只有2020个合个合法状态。再进一步分析后法状态。再进一步分析后, , 又发现有又发现有4 4个合法状态实际上是不个合法状态实际上是不可能达到的。因此实际的问题空间仅由可能达到的。因此实际的问题空间仅由1616个状态构成。下表个状态构成。下表列出分析的结果列出分析的结果: : 第第3737页页 (ML, CL, BL) (ML, CL, BL) (ML, CL, BL) (ML, CL, BL) (0 0 1) (0 0 1)达不到达不到

27、 (0 0 0) (0 0 0) (0 1 1) (0 1 0) (0 1 1) (0 1 0) (0 2 1) (0 2 0) (0 2 1) (0 2 0) (0 3 1) (0 3 0) (0 3 1) (0 3 0)达不到达不到 (1 0 1)(1 0 1)不合法不合法 (1 0 0)(1 0 0)不合法不合法 (1 1 1) (1 1 0) (1 1 1) (1 1 0) (1 2 1) (1 2 1)不合法不合法 (1 2 0)(1 2 0)不合法不合法 (1 3 1)(1 3 1)不合法不合法 (1 3 0)(1 3 0)不合法不合法 (2 0 1)(2 0 1)不合法不合法 (

28、2 0 0)(2 0 0)不合法不合法 (2 1 1)(2 1 1)不合法不合法 (2 1 0)(2 1 0)不合法不合法 (2 2 1) (2 2 0) (2 2 1) (2 2 0) 第第3838页页 (2 3 1) (2 3 1)不合法不合法 (2 3 0)(2 3 0)不合法不合法 (3 0 1)(3 0 1)达不到达不到 (3 0 0) (3 0 0) (3 1 1) (3 1 0) (3 1 1) (3 1 0) (3 2 1) (3 2 0) (3 2 1) (3 2 0) (3 3 1) (3 3 0) (3 3 1) (3 3 0)达不到达不到(2)(2)规则集合规则集合:

29、: 由摆渡操作组成。该问题主要有两种操作由摆渡操作组成。该问题主要有两种操作: pmc: pmc操作操作( (规定为从左岸划向右岸规定为从左岸划向右岸) )和和qmcqmc操作操作( (从右岸划向左岸从右岸划向左岸) )。每次摆渡操作每次摆渡操作, , 船上人数有五种组合船上人数有五种组合, , 因而组成有因而组成有1010条规则条规则的集合。下面定义的规则前的集合。下面定义的规则前5 5条为条为pmcpmc操作操作( (从左岸划向右岸从左岸划向右岸), ), 后后5 5条为条为qmcqmc操作操作( (从右岸划向左岸从右岸划向左岸) )。 第第3939页页if (ML, CL, BL=1)

30、then (ML-1, CL, BL-1); (p10操作操作) if (ML, CL, BL=1) then (ML, CL-1, BL-1); (p01操作操作) if (ML, CL, BL=1) then (ML-1, CL-1, BL-1); (p11操操作作) if (ML, CL, BL=1) then (ML-2, CL, BL-1); (p20操作操作) if (ML, CL, BL=1) then (ML, CL-2, BL-1); (p02操作操作) if (ML, CL, BL=0) then (ML+1, CL, BL+1); (q10操操作作) if (ML, CL

31、, BL=0) then (ML, CL+1, BL+1); (q01操操作作) if (ML, CL, BL=0) then (ML+1, CL+1, BL+1); (q11操操作作) if (ML, CL, BL=0) then (ML+2, CL, BL+1); (q20操操作作) if (ML, CL, BL=0) then (ML, CL+2, BL+1); (q02操操作作) 第第4040页页(3)(3)初始和目标状态初始和目标状态: : 即即(3, 3, 1)(3, 3, 1)和和(0, 0, 0)(0, 0, 0)。和八数码游戏的问题一样和八数码游戏的问题一样, , 建立了产生

32、式系统描述之后建立了产生式系统描述之后, , 就就可以通过控制策略可以通过控制策略, , 对状态空间进行搜索对状态空间进行搜索, , 求得一个摆渡操求得一个摆渡操作序列作序列, ,使其实现目标状态。使其实现目标状态。 在讨论用产生式系统求解问题时在讨论用产生式系统求解问题时, , 有时引入状态空间有时引入状态空间图的概念很有帮助。状态空间图是一个有向图图的概念很有帮助。状态空间图是一个有向图, , 其节点可表其节点可表示问题的各种状态示问题的各种状态( (综合数据库综合数据库), ), 节点之间的弧线代表一些节点之间的弧线代表一些操作操作( (产生式规则产生式规则), ), 它们可把一种状态导

33、向另一种状态。这它们可把一种状态导向另一种状态。这样建立起来的状态空间图样建立起来的状态空间图, , 描述了问题所有可能出现的状态描述了问题所有可能出现的状态及状态和操作之间的关系及状态和操作之间的关系, , 因而可以较直观地看出问题的解因而可以较直观地看出问题的解路径及其性质。实际上只有问题空间规模较小的问题才可能路径及其性质。实际上只有问题空间规模较小的问题才可能作出状态空间图作出状态空间图, , 例如例如N=3N=3的的M-CM-C问题问题, ,的其状态空间图如下的其状态空间图如下图所示图所示, , 此时采用的控制策略为顺序选取规则。由于每个摆此时采用的控制策略为顺序选取规则。由于每个摆

34、渡操作都有对应的逆操作渡操作都有对应的逆操作, , 即即pmcpmc对应对应qmcqmc, , 所以该图也可表所以该图也可表示成具有双向弧的形式。示成具有双向弧的形式。 第第4141页页（3 3 1）（2 2 0）（3 2 0）（3 1 0）（3 2 1）（3 0 0）（3 1 1）（1 1 0）（2 2 1）（0 2 0）（0 3 1）（0 1 0）（0 2 1）（0 1 0）（1 1 0）（0 0 0）第第4242页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）控制策略的分类控制策略的分类(1)不可撤回方式不可撤回方式 这种方式是利用问题给定的局部知识来决定选用

35、规则的这种方式是利用问题给定的局部知识来决定选用规则的，即根据当前已知的局部知识选取一条规则作用于当前综合，即根据当前已知的局部知识选取一条规则作用于当前综合数据库，接着再根据新状态继续选取规则，搜索过程一直进数据库，接着再根据新状态继续选取规则，搜索过程一直进行下去。不必考虑撤回用过的规则。在这一过程中，一条不行下去。不必考虑撤回用过的规则。在这一过程中，一条不理想规则的应用不会影响下一步的工作，更不会影响是否能理想规则的应用不会影响下一步的工作，更不会影响是否能找到解，最多是在求解过程中多用了一些规则。找到解，最多是在求解过程中多用了一些规则。主要优点是控制过程简单。主要优点是控制过程简单

36、。主要缺点是当问题有多个解时不一定能找到最优解。主要缺点是当问题有多个解时不一定能找到最优解。第第4343页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）第第4444页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）第第4545页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）如何运用爬山过程的思想：如何运用爬山过程的思想： 首先要建立一个描述综合数据库变化的函数，如果这个首先要建立一个描述综合数据库变化的函数，如果这个函数具有单极值，并且这个极值对应的状态就是目标，则不函数具有单极值，并且这个极值对应的状态就是目

37、标，则不可撤回的控制策略就是选择使函数值发生最大增长变化的那可撤回的控制策略就是选择使函数值发生最大增长变化的那条规则作用于综合数据库，如此循环下去直到没有规则使函条规则作用于综合数据库，如此循环下去直到没有规则使函数值继续增长，这时函数值取最大值，满足结束条件。数值继续增长，这时函数值取最大值，满足结束条件。第第4646页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）例：八数码问题例：八数码问题在在33的方格棋盘上放置八张牌，初始状态和目标状态如图：的方格棋盘上放置八张牌，初始状态和目标状态如图：空格可以上下左右移动空格可以上下左右移动第第4747页页2.2 产生

38、式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）用用“不在位不在位”将牌个数并取其负值作为状态描述的将牌个数并取其负值作为状态描述的函数函数W W（n n）（）（“不在位不在位”将牌个数是指当前状态将牌个数是指当前状态与目标状态对应位置逐一比较后有差异的将牌总个与目标状态对应位置逐一比较后有差异的将牌总个数，用数，用W W（n n）表示，其中）表示，其中n n表示任一状态），这实际表示任一状态），这实际上是一种启发式函数。上是一种启发式函数。第第4848页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）（2）试探性方式）试探性方式 试探性方式又分为回溯（试

39、探性方式又分为回溯（BacktrackingBacktracking）方式）方式和图搜索（和图搜索（Graph-searchGraph-search）方式）方式 。 回溯方式是回溯方式是种碰壁回头的方式。即在问题求种碰壁回头的方式。即在问题求解过程中，允许先试用某条规则，如果以后发现这解过程中，允许先试用某条规则，如果以后发现这条规则不合适，则允许退回去，再另选一条规则来条规则不合适，则允许退回去，再另选一条规则来试。试。 使用回溯策略需要解决两个重要问题：一是如使用回溯策略需要解决两个重要问题：一是如何确定回溯条件，二是如何减少回溯次数。何确定回溯条件，二是如何减少回溯次数。第第4949页页

40、2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）对八数码游戏，回溯应发生在以下三种情况：对八数码游戏，回溯应发生在以下三种情况：（1）新生成的状态在通向初始状态的路径上已出现过；）新生成的状态在通向初始状态的路径上已出现过；（2）从初始状态开始，应用的规则数目达到所规定的数目之后）从初始状态开始，应用的规则数目达到所规定的数目之后还未找到目标状态（这一组规则的数目实际上就是搜索深度还未找到目标状态（这一组规则的数目实际上就是搜索深度范围所规定的）；范围所规定的）；（3）对当前状态，再没有可应用的规则。）对当前状态，再没有可应用的规则。第第5050页页2.2 产生式知识表

41、示和产生式系统（续）产生式知识表示和产生式系统（续）图搜索方式是一种用图或树把全部求解过程记录下来的方式图搜索方式是一种用图或树把全部求解过程记录下来的方式。由于它记录了已试过的所有路径，因此便于从中选取最优。由于它记录了已试过的所有路径，因此便于从中选取最优路径。图搜索方式与回溯方式的主要区别在于，回溯方式抹路径。图搜索方式与回溯方式的主要区别在于，回溯方式抹去了所有引起失败的试探路径，而图搜索方式则记住了已试去了所有引起失败的试探路径，而图搜索方式则记住了已试过的所有路径。过的所有路径。如果把问题求解过程用图或树的这种结构来描述，即图中的如果把问题求解过程用图或树的这种结构来描述，即图中的

42、每一个节点代表问题的状态，节点间的弧代表应用的规则，每一个节点代表问题的状态，节点间的弧代表应用的规则，那么问题的求解空间就可由隐含图来描述。图搜索方式就是那么问题的求解空间就可由隐含图来描述。图搜索方式就是用某种策略选择应用规则，并把状态变化过程用图结构记录用某种策略选择应用规则，并把状态变化过程用图结构记录下来，一直到得出解为止，也就是从隐含图中搜索出含有解下来，一直到得出解为止，也就是从隐含图中搜索出含有解路径的子图来。路径的子图来。第第5151页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）三、产生式系统的推理三、产生式系统的推理 产生式系统的问题求解过程即

43、为对解空间的搜产生式系统的问题求解过程即为对解空间的搜索过程，也就是推理过程。索过程，也就是推理过程。 按照搜索方向可把产生式系统分为正向推理、按照搜索方向可把产生式系统分为正向推理、逆向推理和双向推理，正向推理又称为事实逆向推理和双向推理，正向推理又称为事实(或数据或数据)驱动推理、前向链接推理；逆向推理又称为目标驱驱动推理、前向链接推理；逆向推理又称为目标驱动推理、逆向链接推理。动推理、逆向链接推理。第第5252页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）1. 正向推理正向推理正向推理从一组表示事实的谓词或命题出发，使用一组产生正向推理从一组表示事实的谓词或

44、命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。设有下列规式规则，用以证明该谓词公式或命题是否成立。设有下列规则集合则集合R1R3： R1： P1 P2 R2： P2 P3 R3： P3 P4 其中，其中，P1 、P2 、P3和和P4为谓词公式或命题。设总数据为谓词公式或命题。设总数据库中已存在事实库中已存在事实P1，则应用规则，则应用规则R1，R2，R3进行正向推理进行正向推理，其过程如图，其过程如图第第5353页页2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）实现正向推理的一般策略是：先提供一批事实实现正向推理的一般策略是：先提供一批事实(数据数据

45、)送入到送入到总数据库中，系统利用这些事实与规则的前提相匹配，触发总数据库中，系统利用这些事实与规则的前提相匹配，触发匹配成功的规则，把其结论作为新的事实添加到总数据库中匹配成功的规则，把其结论作为新的事实添加到总数据库中。继续上述过程，用更新过的总数据库的所有事实再与规则。继续上述过程，用更新过的总数据库的所有事实再与规则库中另一条规则匹配，用其结论再次修改总数据库的内存，库中另一条规则匹配，用其结论再次修改总数据库的内存，直到没有可匹配的新规则，不再有新的事实加到总数据库中直到没有可匹配的新规则，不再有新的事实加到总数据库中为止。为止。第第5454页页2.2 产生式知识表示和产生式系统（续

46、）产生式知识表示和产生式系统（续）2、逆向推理、逆向推理逆向推理从表示目标的谓词或命题出发，使用一组产生式规逆向推理从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立。即首先提出一批假设目标，然则证明事实谓词或命题成立。即首先提出一批假设目标，然后逐一验证这些假设。如果使用前述后逐一验证这些假设。如果使用前述3条规则条规则R1R3，则逆，则逆向推理过程如图向推理过程如图第第5555页页要实现逆向推理，其策略如下：首先假设一个可能的目标，要实现逆向推理，其策略如下：首先假设一个可能的目标，然后由产生式系统试图证明此假设目标是否在总数据库中。然后由产生式系统试图证明此假设目标是否

47、在总数据库中。若在总数据库中，则该假设目标成立；否则，若该假设为终若在总数据库中，则该假设目标成立；否则，若该假设为终止止(证据证据)节点，则询问用户，若不是，则再假定另一个目标节点，则询问用户，若不是，则再假定另一个目标。即寻找结论部分包含该假设的那些规则，把它们的前提作。即寻找结论部分包含该假设的那些规则，把它们的前提作为新的假设，并力图证明其成立。这样反复进行推理，直到为新的假设，并力图证明其成立。这样反复进行推理，直到所有目标均获证明或者所有路径都得到测试为止。所有目标均获证明或者所有路径都得到测试为止。2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）第第565

48、6页页3双向推理系统双向推理系统双向推理又称为正、反向混合推理，它综合了正向推理和逆双向推理又称为正、反向混合推理，它综合了正向推理和逆向推理的长处，又克服了两者的缺点。双向推理的推理策略向推理的长处，又克服了两者的缺点。双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实和目标的匹配。程中的某个步骤，实现事实和目标的匹配。2.2 产生式知识表示和产生式系统（续）产生式知识表示和产生式系统（续）第第5757页页产生式系统的分类产生式系统的分类1. 按推理方向分类按推理方向分类（1）正向推理产生式系统）正向推理产生式系统 它是从初始状态出发，朝着目标状态前进，正向使用规它是从初始状态出发，朝着目标状态前进，正向使用规则的一种推理方法。则的一种推理方法。（2）逆向推理产生式系统）逆向推理产生式系统 它是从目标它是从目标(作为假设作为假设)状态出发，朝着初始状态前进，状态出发，朝着初始状态前进，逆向使用规则的一种推理方法。逆向使用规则的一种推理方法。（3）双向推理产生式系统）双向推理产生式系统 双向推理是把正向推理和逆向推理结合起来使用的一种双向推理是把正向推理和逆向推理结合起来使用的一种推理方式。推理方式。2.2 产生式知