人工智能5第6章N

1、第第6章章 基于产生式规则的机器推理基于产生式规则的机器推理产生式规则是一种十分普遍的知识表示产生式规则是一种十分普遍的知识表示形式，产生式系统是一种应用广泛的问题求形式，产生式系统是一种应用广泛的问题求解系统模型。解系统模型。本章介绍基于产生式（规则）的知识表本章介绍基于产生式（规则）的知识表示及其推理。示及其推理。6.1 产生式规则产生式规则 6.2 产生式系统产生式系统 第第6章章 基于产生式规则的机器推理基于产生式规则的机器推理6.1 产生式规则产生式规则主要介绍主要介绍：产生式规则及基于产生式的推理模式。产生式规则及基于产生式的推理模式。6.1.1 产生式规则产生式规则产生式（产生式

2、（PRODUCTION）一词，首先是由美国数学家波）一词，首先是由美国数学家波斯特（斯特（E. POST）提出来的。波斯特根据替代规则提出了一种）提出来的。波斯特根据替代规则提出了一种称为波斯特机的计算模型。模型中的每条规则当时被称为一个称为波斯特机的计算模型。模型中的每条规则当时被称为一个产生式。后来，这一术语几经修改扩充被应用到许多领域。产生式。后来，这一术语几经修改扩充被应用到许多领域。产生式也称为产生式也称为产生式规则产生式规则，或简称规则。，或简称规则。产生式的一般形式为：产生式的一般形式为：（前件）（前件） （后件）（后件）其中，前件就是前提其中，前件就是前提(条件，前提条件条件，

3、前提条件)，后件是结论或动，后件是结论或动作作(操作操作)。前件和后件可以由逻辑运算符。前件和后件可以由逻辑运算符AND、OR、NOT组组成的表达式。成的表达式。6.1 产生式规则产生式规则6.1.1 产生式规则产生式规则产生式的一般形式为：产生式的一般形式为：（前件）（前件） （后件）（后件）产生式规则的语义是：如果前提满足，则可得结论或者执产生式规则的语义是：如果前提满足，则可得结论或者执行相应的动作，即后件由前件来触发。所以，前件是规则的执行相应的动作，即后件由前件来触发。所以，前件是规则的执行条件，后件是规则体。行条件，后件是规则体。例如，以下是几个产生式规则：例如，以下是几个产生式规

4、则：(1)如果银行存款利率下调，那么股票价格上涨。如果银行存款利率下调，那么股票价格上涨。(2)如果炉温超过上限，则立即关闭风门。如果炉温超过上限，则立即关闭风门。(3)如果键盘突然失灵，且屏幕上出现奇怪字符，则是病毒如果键盘突然失灵，且屏幕上出现奇怪字符，则是病毒发作。发作。(4)如果胶卷感光度为如果胶卷感光度为200，光线条件为晴天，目标距离不，光线条件为晴天，目标距离不超过超过5米，则快门速度取米，则快门速度取250，光圈大小取，光圈大小取f16。 6.1 产生式规则产生式规则6.1.1 产生式规则产生式规则产生式的一般形式为：产生式的一般形式为：（前件）（前件） （后件）（后件）可以看

5、出，可以看出，产生式与逻辑蕴涵式非常相似产生式与逻辑蕴涵式非常相似。逻辑蕴涵式就是。逻辑蕴涵式就是产生式，但它只是一种产生式（是产生式的一种特殊情况）。产生式，但它只是一种产生式（是产生式的一种特殊情况）。除逻辑蕴含式以外，产生式还包含各种操作、规则、变换、除逻辑蕴含式以外，产生式还包含各种操作、规则、变换、算子、函数等等。如例算子、函数等等。如例(2)【如果炉温超过上限，则立即关闭风【如果炉温超过上限，则立即关闭风门。】门。】是一个产生是一个产生式，但不是一个式，但不是一个逻辑蕴涵式。逻辑蕴涵式。概括来讲，概括来讲，产生式描述了事物之间的一种对应关系，产生式描述了事物之间的一种对应关系，其外

6、延其外延十分的广泛。十分的广泛。例如，例如，图搜索中的状态转换规则和问题变换规则都图搜索中的状态转换规则和问题变换规则都是产生式是产生式规则，规则，另外还有另外还有程序设计语言的文法规则、逻辑中的逻程序设计语言的文法规则、逻辑中的逻辑蕴含式和等价式、数学中的微分和积分公式、化学中分子结构辑蕴含式和等价式、数学中的微分和积分公式、化学中分子结构式的分解变换规则等等，也都是产生式规则；式的分解变换规则等等，也都是产生式规则；甚至甚至体育比赛中的体育比赛中的规则、国家的法律条文、单位的规章制度等等，也都可以表示成规则、国家的法律条文、单位的规章制度等等，也都可以表示成产生式规则。产生式规则。6.1

7、产生式规则产生式规则6.1.1 产生式规则产生式规则产生式的一般形式为：产生式的一般形式为：（前件）（前件） （后件）（后件）一个产生式规则就是一条知识。用产生式不仅可以进行推一个产生式规则就是一条知识。用产生式不仅可以进行推理，而且还可以实现操作。一般都把产生式规则作为一种知识理，而且还可以实现操作。一般都把产生式规则作为一种知识表达的形式或方法。表达的形式或方法。说明：逻辑蕴涵式只能表示精确知识，其值或真或假；而说明：逻辑蕴涵式只能表示精确知识，其值或真或假；而产生式不仅可以表示精确知识，也可以表示不精确的知识。产生式不仅可以表示精确知识，也可以表示不精确的知识。如果：头痛发烧，则患感冒如

8、果：头痛发烧，则患感冒(0.8)，这里的这里的0.8就是对应规则的信度就是对应规则的信度(CF CERTAINTY FACTOR，看书看书P.152)。6.1 产生式规则产生式规则6.1.1 产生式规则产生式规则6.1.2 基于产生式规则的推理模式基于产生式规则的推理模式利用产生式规则，利用产生式规则，可以实现可以实现有前提条件的指令性操作，有前提条件的指令性操作，也也可以实现可以实现有前提条件的逻辑推理。有前提条件的逻辑推理。实现操作的方法是，当测试到一条规则的前提条件满足时，实现操作的方法是，当测试到一条规则的前提条件满足时，就执行其后部的动作。这称为规则被触发或点燃。就执行其后部的动作。

9、这称为规则被触发或点燃。利用产生式规则实现逻辑推理的方法是，当有事实能与某利用产生式规则实现逻辑推理的方法是，当有事实能与某规则的前提匹配（即规则的前提成立）时，就得到该规则后部规则的前提匹配（即规则的前提成立）时，就得到该规则后部的结论（即结论成立）。的结论（即结论成立）。6.1 产生式规则产生式规则6.2 产生式系统产生式系统机器机器中运用产生式规则进行推理是用所谓的中运用产生式规则进行推理是用所谓的产生式系统产生式系统来来实现的。实现的。把一组产生式（规则）放在一起，并让他们互相配合，协把一组产生式（规则）放在一起，并让他们互相配合，协同作用；同作用；一个产生式规则生成的结论可以供另一个

10、产生式规则一个产生式规则生成的结论可以供另一个产生式规则作为已知事实使用作为已知事实使用，以求得问题得解决，这样的系统称为产生，以求得问题得解决，这样的系统称为产生式系统。式系统。本节主要介绍本节主要介绍：(1)系统结构系统结构 ；(2)运行过程运行过程 ；(3)控制策略与常用算法控制策略与常用算法 ；(4)程序实现（略）；程序实现（略）； (5)产生式系统与问题求解（简介）。产生式系统与问题求解（简介）。6.2 产生式系统产生式系统6.2.1 系统结构系统结构产生式系统由三部分组成：产生式系统由三部分组成：产生式规则库产生式规则库，推理机推理机和和动态动态数据库数据库。其结构如图。其结构如图

11、61所示。所示。 产生式规则库产生式规则库推理机推理机动态数据库动态数据库图图61 产生式系统的结构产生式系统的结构6.2 产生式系统产生式系统6.2.1 系统结构系统结构产生式规则库产生式规则库推理机推理机动态数据库动态数据库图图61 产生式系统的结构产生式系统的结构产生式规则库产生式规则库又称为又称为产生式规则产生式规则集集，由相应的领域内知识的产生式规，由相应的领域内知识的产生式规则组成。则组成。规则库是产生式系统进行问题求解的基础，规则库是产生式系统进行问题求解的基础，其中知识是否其中知识是否完整、一致，表达是否准确，对知识的组成是否合理等，不仅完整、一致，表达是否准确，对知识的组成是

12、否合理等，不仅将直接影响到系统的性能，而且还会影响到系统的运行效率。将直接影响到系统的性能，而且还会影响到系统的运行效率。一般来说，在建立规则库时应注意以下问题：一般来说，在建立规则库时应注意以下问题：（1）有效地表达领域内的过程性知识。）有效地表达领域内的过程性知识。（2）对知识进行合理的组织与管理。）对知识进行合理的组织与管理。由产生式系统组成的专家系统，它的核心是利用产生式规由产生式系统组成的专家系统，它的核心是利用产生式规则表达的专家经验，规则的多少是系统能力的关键因素，系统则表达的专家经验，规则的多少是系统能力的关键因素，系统问题求解的能力随着规则的增加而增加。如何获得更多的知识问题

13、求解的能力随着规则的增加而增加。如何获得更多的知识或专家经验来组成规则库？就提出了系统知识获取的问题。或专家经验来组成规则库？就提出了系统知识获取的问题。6.2 产生式系统产生式系统6.2.1 系统结构系统结构推理机推理机又称控制执行机构，由一组程序组成。又称控制执行机构，由一组程序组成。推理机实现对问题的推理求解，推理机实现对问题的推理求解，负责产生式规则的前提条负责产生式规则的前提条件测试或匹配，规则的调度与选取，规则体的解释和执行。件测试或匹配，规则的调度与选取，规则体的解释和执行。推推理机既要实施推理，又要对推理进行控制，同时推理机又是规理机既要实施推理，又要对推理进行控制，同时推理机

14、又是规则的解释程序。则的解释程序。产生式规则库产生式规则库推理机推理机动态数据库动态数据库6.2 产生式系统产生式系统6.2.1 系统结构系统结构推理机推理机又称控制执行机构，由一组程序组成。又称控制执行机构，由一组程序组成。推理机实现对问题的推理求解，推理机实现对问题的推理求解，负责产生式规则的前提条负责产生式规则的前提条件测试或匹配，规则的调度与选取，规则体的解释和执行。件测试或匹配，规则的调度与选取，规则体的解释和执行。推推理机既要实施推理，又要对推理进行控制，同时推理机又是规理机既要实施推理，又要对推理进行控制，同时推理机又是规则的解释程序。则的解释程序。动态数据库动态数据库又称又称全

15、局数据库、综合数据库、工作存储器、全局数据库、综合数据库、工作存储器、上下文、黑板上下文、黑板等，它是一个动态数据结构。等，它是一个动态数据结构。动态数据库用于动态数据库用于存储问题求解过程中的各种当前信息，例存储问题求解过程中的各种当前信息，例如问题的初始事实、原始证据、推理中得到的中间结果如问题的初始事实、原始证据、推理中得到的中间结果(中间中间结论结论)、和最后结果。、和最后结果。可见，动态数据库的内容随着推理的进可见，动态数据库的内容随着推理的进行是不断动态变化的。行是不断动态变化的。产生式规则库产生式规则库推理机推理机动态数据库动态数据库6.2 产生式系统产生式系统6.2.1 系统结

16、构系统结构6.2.2 运行过程运行过程产生式系统的产生式系统的运行过程运行过程，就是推理机不断运用规则库中的，就是推理机不断运用规则库中的规则，作用于动态数据库，不断进行推理，并不断规则，作用于动态数据库，不断进行推理，并不断检测目标条检测目标条件是否满足的过程件是否满足的过程。当推理到某一步，目标条件被满足，则当推理到某一步，目标条件被满足，则推理成功推理成功，于是系，于是系统运行结束；或者无规则可用，而目标条件仍未满足，则统运行结束；或者无规则可用，而目标条件仍未满足，则推理推理失败失败，系统运行结束。，系统运行结束。一个实际的产生式系统，其目标条件一般不会只经一步推一个实际的产生式系统，

17、其目标条件一般不会只经一步推理就可满足，往往要经过多步推理才能满足或者证明问题无解。理就可满足，往往要经过多步推理才能满足或者证明问题无解。产生式规则库产生式规则库推理机推理机动态数据库动态数据库6.2 产生式系统产生式系统6.2.2 运行过程运行过程产生式系统的运行时，除需要规则库外，还需产生式系统的运行时，除需要规则库外，还需要初始事实（或数据）和目标条件。要初始事实（或数据）和目标条件。推理机的一次推理的过程可如图推理机的一次推理的过程可如图6-2所示。所示。产生式规则库产生式规则库推理机推理机动态数据库动态数据库从规则库中取一条规则，将其前从规则库中取一条规则，将其前提同当前动态数据库

18、中的事实提同当前动态数据库中的事实/数据数据进行模式匹配。进行模式匹配。把该规则的结论放入当前动态数把该规则的结论放入当前动态数据库；或执行规则所规定的动作。据库；或执行规则所规定的动作。匹配成功否？匹配成功否？NY6.2 产生式系统产生式系统6.2.2 运行过程运行过程产生式系统的运行过程是从初始事实（或数据）产生式系统的运行过程是从初始事实（或数据）出发，寻求到达目标条件的通路过程。所以，产生式出发，寻求到达目标条件的通路过程。所以，产生式系统的运行过程也是一个搜索的过程，但一般也把产系统的运行过程也是一个搜索的过程，但一般也把产生式系统的整个运行过程也称为推理。生式系统的整个运行过程也称

19、为推理。那么，一个产生式系统启动后，从哪里开始推理？那么，一个产生式系统启动后，从哪里开始推理？产生式规则库产生式规则库推理机推理机动态数据库动态数据库6.2 产生式系统产生式系统6.2.2 运行过程运行过程6.2.3 控制策略与常用算法控制策略与常用算法产生式系统的推理可分为产生式系统的推理可分为正向推理和反向推理两正向推理和反向推理两种基本方式种基本方式。正向推理正向推理就是从初始事实出发，正向使用规则进就是从初始事实出发，正向使用规则进行推理（用规则前提与动态数据库中的事实匹配，或行推理（用规则前提与动态数据库中的事实匹配，或用动态数据库中的数据测试规则的前提条件，然后产用动态数据库中的

20、数据测试规则的前提条件，然后产生结论或执行动作），朝目标方向前进；生结论或执行动作），朝目标方向前进；反向推理反向推理就是从目标出发，反向使用规则进行推就是从目标出发，反向使用规则进行推理（用规则结论与目标匹配，又产生新的目标，然后理（用规则结论与目标匹配，又产生新的目标，然后对新的目标再作同样的处理），朝初始事实数据方向对新的目标再作同样的处理），朝初始事实数据方向前进。前进。产生式规则库产生式规则库推理机推理机动态数据库动态数据库6.2 产生式系统产生式系统6.2.3 控制策略与常用算法控制策略与常用算法1. 正向推理正向推理正向推理算法一：正向推理算法一：步步1 将初始事实将初始事实/数

21、据置入动态数据库；数据置入动态数据库；步步2 用动态数据库中的事实用动态数据库中的事实/数据，匹配数据，匹配/测试目测试目标条件，若目标条件满足，则推理成功，结束；标条件，若目标条件满足，则推理成功，结束；步步3 用规则库中各规则的前提匹配动态数据库中用规则库中各规则的前提匹配动态数据库中的事实的事实/数据，将匹配成功的规则组成待用规则集；数据，将匹配成功的规则组成待用规则集；步步4 若待用规则集为空，则运行失败，退出；若待用规则集为空，则运行失败，退出；步步5 将待用规则集中各规则的结论加入动态数据将待用规则集中各规则的结论加入动态数据库，或者执行动作，转步库，或者执行动作，转步2；可以看出

22、，随着推理的进行，动态数据库的内容或者状态可以看出，随着推理的进行，动态数据库的内容或者状态在不断变化。在不断变化。6.2 产生式系统产生式系统6.2.3 控制策略与常用算法控制策略与常用算法1. 正向推理正向推理例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 建立一个动物识别系统的规则库，用以识别老虎、金钱豹、建立一个动物识别系统的规则库，用以识别老虎、金钱豹、斑马、长颈鹿、企鹅、海燕斑马、长颈鹿、企鹅、海燕7种动物。种动物。设由下列动物识别规则组成一个规则库（设由下列动物识别规则组成一个规则库（总共有总共有15条规条规则则），推理机采用上述的正

23、向推理算法，建立一个产生式系统。），推理机采用上述的正向推理算法，建立一个产生式系统。该产生式系统就是一个小型动物分类知识库系统。该产生式系统就是一个小型动物分类知识库系统。规则集（规则集（ 15条条）：）：R1：若某动物有奶，则它是哺乳动物。：若某动物有奶，则它是哺乳动物。R2：若某动物有毛发，则它是哺乳动物。：若某动物有毛发，则它是哺乳动物。R3：若某动物有羽毛，则它是鸟。：若某动物有羽毛，则它是鸟。R4：若某动物会飞且生蛋，则它是鸟。：若某动物会飞且生蛋，则它是鸟。R5：若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动物。：若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动

24、物。R6：若某动物是哺乳动物且吃肉，则它是食肉动物。：若某动物是哺乳动物且吃肉，则它是食肉动物。R7：若某动物是哺乳动物且有蹄，则它是有蹄动物。：若某动物是哺乳动物且有蹄，则它是有蹄动物。R8：若某动物是有蹄动物且反刍食物，则它是偶蹄动物。：若某动物是有蹄动物且反刍食物，则它是偶蹄动物。R9：若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。：若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。R10：若某动物是食肉动物且黄褐色且有黑色斑点，则它是金钱豹。：若某动物是食肉动物且黄褐色且有黑色斑点，则它是金钱豹。R11:若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点若某动物是有蹄动物且长腿

25、且长脖子且黄褐色且有暗斑点,则它是长颈鹿。则它是长颈鹿。R12：若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。：若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。R13：若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是鸵鸟。：若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是鸵鸟。R14：若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。：若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。R15：若某动物是鸟且善飞且不怕风浪，则它是海燕。：若某动物是鸟且善飞且不怕风浪，则它是海燕。例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 有毛发有毛发吃

26、肉吃肉黄褐色黄褐色有黑色条纹有黑色条纹哺乳动物哺乳动物老虎老虎食肉动物食肉动物图图65 关于关于“老虎老虎”正向推理树正向推理树再给出再给出初始事实初始事实：F1：某动物有毛发：某动物有毛发F2：吃肉：吃肉F3：黄褐色：黄褐色F4：有黑色条纹：有黑色条纹目标条件为：该动物是什么？目标条件为：该动物是什么？易见易见，该系统的运行结果，该系统的运行结果为：该动物是老虎。其推理树为：该动物是老虎。其推理树如图如图65所示。所示。 可以看出，上述正向推可以看出，上述正向推理算法适合于只搜索目标节点理算法适合于只搜索目标节点而不需要路径的问题。而不需要路径的问题。(?)正向推理也称为前向推理、正向推理也

27、称为前向推理、正向链、数据驱动的推理。正向链、数据驱动的推理。例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 有毛发有毛发吃肉吃肉黄褐色黄褐色有黑色条纹有黑色条纹哺乳动物哺乳动物老虎老虎食肉动物食肉动物图图65 关于关于“老虎老虎”正向推理树正向推理树再给出再给出初始事实初始事实：F1：某动物有毛发：某动物有毛发F2：吃肉：吃肉F3：黄褐色：黄褐色F4：有黑色条纹：有黑色条纹目标条件为：该动物是什么？目标条件为：该动物是什么？易见易见，该系统的运行结果，该系统的运行结果为：该动物是老虎。其推理树为：该动物是老虎。其推理树如图如图65所示。所示。 可

28、以看出，上述正向推可以看出，上述正向推理算法适合于只搜索目标节点理算法适合于只搜索目标节点而不需要路径的问题。而不需要路径的问题。(?)正向推理也称为前向推理、正向推理也称为前向推理、正向链、数据驱动的推理。正向链、数据驱动的推理。例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 正向推理过程中正向推理过程中动态数据库动态数据库的变化情况？的变化情况？正向推理正向推理过程中过程中动态数据库动态数据库的变化情况？的变化情况？例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 有毛发有毛发吃肉吃肉黄褐色黄褐色有黑

29、色条纹有黑色条纹哺乳动物哺乳动物老虎老虎食肉动物食肉动物图图65 关于关于“老虎老虎”正向推理树正向推理树动态数据库用于动态数据库用于存储问题求存储问题求解过程中的各种当前信息解过程中的各种当前信息，例如，例如问题的初始事实、原始证据、推问题的初始事实、原始证据、推理中得到的中间结果理中得到的中间结果(中间结论中间结论)、和最后结果和最后结果。正向推理算法一：正向推理算法一：步步1 将初始事实将初始事实/数据置入动态数据库；数据置入动态数据库； 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条

30、纹有黑色条纹正向推理正向推理过程中过程中动态数据库动态数据库的变化情况？的变化情况？ 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹正向推理算法一：正向推理算法一：步步2 用动态数据库中的事实用动态数据库中的事实/数据，匹配数据，匹配/测试目标测试目标条件，若目标条件满足，则推理成功，结束；条件，若目标条件满足，则推理成功，结束；例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 正向推理正向推理过程中过程中动态数据库动态数据库的变化情况

31、？的变化情况？R2和和F1：哺乳动物：哺乳动物 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹正向推理算法一：正向推理算法一：步步3 用规则库中各规则的前提匹配动态数据库中用规则库中各规则的前提匹配动态数据库中的事实的事实/数据，将匹配成功的规则组成数据，将匹配成功的规则组成待用规则集待用规则集；步步4 若待用规则集为空，则运行失败，退出；若待用规则集为空，则运行失败，退出；例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 F5: 哺乳

32、动物哺乳动物正向推理正向推理过程中过程中动态数据库动态数据库的变化情况？的变化情况？R2和和F1：哺乳动物：哺乳动物 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹正向推理算法一：正向推理算法一：步步5 将待用规则集中各规则的结论加入动态数据将待用规则集中各规则的结论加入动态数据库，或者执行动作，转步库，或者执行动作，转步2；例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 F5: 哺乳动物哺乳动物正向推理正向推理过程中过程中动态数据库

33、动态数据库的变化情况？的变化情况？R2和和F1：哺乳动物：哺乳动物 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹正向推理算法一：正向推理算法一：步步2 用动态数据库中的事实用动态数据库中的事实/数据，匹配数据，匹配/测试目标测试目标条件，若目标条件满足，则推理成功，结束；条件，若目标条件满足，则推理成功，结束；例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 F5: 哺乳动物哺乳动物正向推理正向推理过程中过程中动态数据库动态数据库的变

34、化情况？的变化情况？R2和和F1：哺乳动物：哺乳动物R6和和F2, F5 ：食肉动物：食肉动物 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹正向推理算法一：正向推理算法一：步步3 用规则库中各规则的前提匹配动态数据库中用规则库中各规则的前提匹配动态数据库中的事实的事实/数据，将匹配成功的规则组成待用规则集；数据，将匹配成功的规则组成待用规则集；步步4 若待用规则集为空，则运行失败，退出；若待用规则集为空，则运行失败，退出；例例6.1 动物分类问题的产生式系统的描述及其求解。动物

35、分类问题的产生式系统的描述及其求解。 F5: 哺乳动物哺乳动物正向推理正向推理过程中过程中动态数据库动态数据库的变化情况？的变化情况？R2和和F1：哺乳动物：哺乳动物R6和和F2, F5 ：食肉动物：食肉动物 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹F6: 食肉动物食肉动物正向推理算法一：正向推理算法一：步步5 将待用规则集中各规则的结论加入动态数据将待用规则集中各规则的结论加入动态数据库，或者执行动作，转步库，或者执行动作，转步2；例例6.1 动物分类问题的产生式系统的描

36、述及其求解。动物分类问题的产生式系统的描述及其求解。 F5: 哺乳动物哺乳动物正向推理正向推理过程中过程中动态数据库动态数据库的变化情况的变化情况?R2和和F1：哺乳动物：哺乳动物R6和和F2, F5 ：食肉动物：食肉动物 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹F6: 食肉动物食肉动物正向推理算法一：正向推理算法一：步步2 用动态数据库中的事实用动态数据库中的事实/数据，匹配数据，匹配/测试目标测试目标条件，若目标条件满足，则推理成功，结束；条件，若目标条件满足，则推理成

37、功，结束；例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 F5: 哺乳动物哺乳动物正向推理正向推理过程中过程中动态数据库动态数据库的变化情况的变化情况?R2和和F1：哺乳动物：哺乳动物R6和和F2, F5 ：食肉动物：食肉动物R9和和F6, F3, F4 ：它是老虎：它是老虎 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹F6: 食肉动物食肉动物正向推理算法一：正向推理算法一：步步3 用规则库中各规则的前提匹配动态数据库中用规则库中各

38、规则的前提匹配动态数据库中的事实的事实/数据，将匹配成功的规则组成待用规则集；数据，将匹配成功的规则组成待用规则集；步步4 若待用规则集为空，则运行失败，退出；若待用规则集为空，则运行失败，退出；例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 F5: 哺乳动物哺乳动物正向推理正向推理过程中过程中动态数据库动态数据库的变化情况的变化情况?R2和和F1：哺乳动物：哺乳动物R6和和F2, F5 ：食肉动物：食肉动物R9和和F6, F3, F4 ：它是老虎：它是老虎 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是

39、什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹F6: 食肉动物食肉动物F7: 老虎老虎正向推理算法一：正向推理算法一：步步5 将待用规则集中各规则的结论加入动态数据将待用规则集中各规则的结论加入动态数据库，或者执行动作，转步库，或者执行动作，转步2；例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 F5: 哺乳动物哺乳动物正向推理正向推理过程中过程中动态数据库动态数据库的变化情况的变化情况?R2和和F1：哺乳动物：哺乳动物R6和和F2, F5 ：食肉动物：食肉动物R9和和F6, F3, F4 ：它是老虎：它是老虎 初始事实初

40、始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹F6: 食肉动物食肉动物F7: 老虎老虎正向推理算法一：正向推理算法一：步步2 用动态数据库中的事实用动态数据库中的事实/数据，匹配数据，匹配/测试目标测试目标条件，条件，若目标条件满足，则推理成功，结束若目标条件满足，则推理成功，结束；例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 黄褐色黄褐色有黑色条纹有黑色条纹老虎老虎R9有毛发有毛发哺乳动物哺乳动物R2F5: 哺乳动物哺乳动物正向推理正向推理

41、过程中过程中动态数据库动态数据库的变化情况的变化情况?R2和和F1：哺乳动物：哺乳动物图图65 关于关于“老虎老虎”的正向推理的正向推理树树R6和和F2, F5 ：食肉动物：食肉动物R9和和F6, F3, F4 ：它是老虎：它是老虎 初始事实初始事实 目标条件目标条件F1: 某动物有毛发某动物有毛发 该动物是什么？该动物是什么？ F2: 吃肉吃肉F3: 黄褐色黄褐色F4: 有黑色条纹有黑色条纹吃肉吃肉食肉动物食肉动物R6F6: 食肉动物食肉动物F7: 老虎老虎例例6.1 动物分类问题的产生式系统的描述及其求解。动物分类问题的产生式系统的描述及其求解。 6.2.3 控制策略与常用算法控制策略与常

42、用算法1. 正向推理正向推理2. 反向推理反向推理反向推理算法：反向推理算法：步步1 将初始事实将初始事实/数据置入动态数据库，将目标条件数据置入动态数据库，将目标条件(目标目标假设假设)置入目标链；置入目标链；步步2 若若目标链目标链为空则推理成功，结束；为空则推理成功，结束；步步3 取出目标链中的第一个目标，用动态数据库的事实取出目标链中的第一个目标，用动态数据库的事实/数据同其匹配，若匹配成功，转步数据同其匹配，若匹配成功，转步2；步步4 用规则集中的各规则的结论同该目标匹配，若匹配成用规则集中的各规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，功

43、，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，转步并取代原来的父目标而加入目标链，转步3；步步5 若该目标是初始目标，则推理失败，退出；若该目标是初始目标，则推理失败，退出；步步6 将该目标的父目标移回目标链，取代该目标及其兄弟将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步目标，转步3；可以看出，上述反向推理算法的推理过程也是一个图搜索可以看出，上述反向推理算法的推理过程也是一个图搜索过程，而且一般是一个与或树搜索。（？）过程，而且一般是一个与或树搜索。（？）有爪有爪有犬齿有犬齿目盯前方目盯前方有奶有奶有毛发有毛发吃肉吃肉黄褐色黄褐色 有黑色条

44、纹有黑色条纹哺乳动物哺乳动物食肉动物食肉动物老虎老虎图图66关于关于“老虎老虎”的反向推理树的反向推理树 可以看出，与正向推不同，这次的推理树是可以看出，与正向推不同，这次的推理树是从上而下扩展从上而下扩展而成的而成的，而且，而且推理过程中还发生过回溯推理过程中还发生过回溯。6.2.3 控制策略与常用算法控制策略与常用算法2. 反向推理反向推理例例6.2 对于例对于例6.1中的产生式系统，改为反向推理算法，则中的产生式系统，改为反向推理算法，则得到图得到图66所示的推理树。所示的推理树。有爪有爪有犬齿有犬齿目盯前方目盯前方有奶有奶有毛发有毛发吃肉吃肉黄褐色黄褐色 有黑色条纹有黑色条纹哺乳动物哺

45、乳动物食肉动物食肉动物老虎老虎图图66关于关于“老虎老虎”的反向推理树的反向推理树6.2.3 控制策略与常用算法控制策略与常用算法2. 反向推理反向推理例例6.2 对于例对于例6.1中的产生式系统，改为反向推理算法，则中的产生式系统，改为反向推理算法，则得到图得到图66所示的推理树。所示的推理树。反向推理也称为后向推理、反向链、目标驱动的推理等。反向推理也称为后向推理、反向链、目标驱动的推理等。请同学们分析一下：反向推理过程中请同学们分析一下：反向推理过程中动态数据库动态数据库的变化的变化情况情况?从上面的两个算法可以看出，正向推理是自底向上的综从上面的两个算法可以看出，正向推理是自底向上的综

46、合过程，而反向推理则是自顶向下的分析过程。合过程，而反向推理则是自顶向下的分析过程。 可以看出，与正向推不同，这次的推理树是可以看出，与正向推不同，这次的推理树是从上而下扩展从上而下扩展而成的而成的，而且，而且推理过程中还发生过回溯推理过程中还发生过回溯。有爪有爪有犬齿有犬齿目盯前方目盯前方有奶有奶有毛发有毛发吃肉吃肉黄褐色黄褐色 有黑色条纹有黑色条纹哺乳动物哺乳动物食肉动物食肉动物老虎老虎图图66关于关于“老虎老虎”的反向推理树的反向推理树6.2.3 控制策略与常用算法控制策略与常用算法2. 反向推理反向推理例例6.2 对于例对于例6.1中的产生式系统，改为反向推理算法，则中的产生式系统，改

47、为反向推理算法，则得到图得到图66所示的推理树。所示的推理树。请同学们分析一下：反向推理过程中请同学们分析一下：反向推理过程中动态数据库动态数据库的变化的变化情况情况?反向推理算法：反向推理算法：步步1 将初始事实将初始事实/数据置入动态数据库，将目标条件数据置入动态数据库，将目标条件(目标假设目标假设)置入目标链；置入目标链；步步2 若若目标链目标链为空则推理成功，结束；为空则推理成功，结束；步步3 取出目标链中的第一个目标，用动态数据库的事实取出目标链中的第一个目标，用动态数据库的事实/数据同其匹配，若匹数据同其匹配，若匹配成功，转步配成功，转步2；步步4 用规则集中的各规则的结论同该目标

48、匹配，若匹配成功，则将第一个匹用规则集中的各规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，转步转步3；步步5 若该目标是初始目标，则推理失败，退出；若该目标是初始目标，则推理失败，退出；步步6 将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步3； 可以看出，与正向推不同，这次的推理树是可以看出，与正向推不同，这次的推理树是从上而下扩展从上而下扩展而成的而成的，而且，而且推理过程中还发生过

49、回溯推理过程中还发生过回溯。有爪有爪有犬齿有犬齿目盯前方目盯前方有奶有奶有毛发有毛发吃肉吃肉黄褐色黄褐色 有黑色条纹有黑色条纹哺乳动物哺乳动物食肉动物食肉动物老虎老虎图图66关于关于“老虎老虎”的反向推理树的反向推理树6.2.3 控制策略与常用算法控制策略与常用算法2. 反向推理反向推理例例6.2 对于例对于例6.1中的产生式系统，改为反向推理算法，则中的产生式系统，改为反向推理算法，则得到图得到图66所示的推理树。所示的推理树。除了正向推理和反向推理以外，产除了正向推理和反向推理以外，产生式系统还可以进行双向推理。双向推生式系统还可以进行双向推理。双向推理就是同时从初始数据和目标条件（目理就

50、是同时从初始数据和目标条件（目标假设）出发进行推理，如果在中间某标假设）出发进行推理，如果在中间某处相遇，则推理搜索成功。处相遇，则推理搜索成功。 可以看出，与正向推不同，这次的推理树是可以看出，与正向推不同，这次的推理树是从上而下扩展从上而下扩展而成的而成的，而且，而且推理过程中还发生过回溯推理过程中还发生过回溯。6.2.3 控制策略与常用算法控制策略与常用算法2. 反向推理反向推理3. 冲突消解策略冲突消解策略上述正向推理算法中，对所有匹配成功的规则都同时触发上述正向推理算法中，对所有匹配成功的规则都同时触发启用。所以，它实现的搜索是穷举式的树式盲目搜索。下面我启用。所以，它实现的搜索是穷

51、举式的树式盲目搜索。下面我们给出一个正向推理的启发式线式搜索算法。们给出一个正向推理的启发式线式搜索算法。正向推理算法二：正向推理算法二：步步1 初始事实初始事实/数据置入动态数据库；数据置入动态数据库；步步2 用动态数据库中的事实用动态数据库中的事实/数据，匹配数据，匹配/测试目标条件，测试目标条件，若目标条件满足，则推理成功，结束。若目标条件满足，则推理成功，结束。步步3 用规则库中各种规则的前提匹配动态数据库中的事实用规则库中各种规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集；数据，将匹配成功的规则组成待用规则集；步步4 若待用规则集为空，则运行失败，退出。若待用

52、规则集为空，则运行失败，退出。步步5 用某种策略，从待用规则集中选取一条规则，将其结用某种策略，从待用规则集中选取一条规则，将其结论加入动态数据库，或者执行其动作，撤销待用规则集论加入动态数据库，或者执行其动作，撤销待用规则集，转步，转步2；6.2.3 控制策略与常用算法控制策略与常用算法3. 冲突消解策略冲突消解策略正向推理算法二：正向推理算法二：步步1 将初始事实将初始事实/数据置入动态数据库；数据置入动态数据库；步步2 用动态数据库中的事实用动态数据库中的事实/数据，匹配数据，匹配/测试目标条件，测试目标条件，若目标条件满足，则推理成功，结束。若目标条件满足，则推理成功，结束。步步3 用

53、规则库中各种规则的前提匹配动态数据库中的事实用规则库中各种规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集；数据，将匹配成功的规则组成待用规则集；步步4 若待用规则集为空，则运行失败，退出。若待用规则集为空，则运行失败，退出。步步5 用某种策略，从待用规则集中选取一条规则，将其结用某种策略，从待用规则集中选取一条规则，将其结论加入动态数据库，或者执行其动作，撤销待用规则集论加入动态数据库，或者执行其动作，撤销待用规则集，转步，转步2；该算法仅与前面的算法仅在步该算法仅与前面的算法仅在步5 5有所差别。该算法的表现有所差别。该算法的表现在在“用某种策略，从待用规则集中选取一

54、条规则用某种策略，从待用规则集中选取一条规则”这种选取策这种选取策略，也称为略，也称为“冲突消解冲突消解”策略。策略。因为这时可用规则集中的规则因为这时可用规则集中的规则都可触发执行，但只取其中之一，因而就产生了冲突或竞争。都可触发执行，但只取其中之一，因而就产生了冲突或竞争。所以，冲突消解策略对正向推理有重要意义。所以，冲突消解策略对正向推理有重要意义。6.2.3 控制策略与常用算法控制策略与常用算法3. 冲突消解策略冲突消解策略常用的冲突消解策略有：优先级法（优先级高常用的冲突消解策略有：优先级法（优先级高者优先）、可信度法（可信度高者优先）、代价法者优先）、可信度法（可信度高者优先）、代

55、价法（代价低者优先）及自然顺序法等。（代价低者优先）及自然顺序法等。当然，要使用优先级法、可信度法、代价法等当然，要使用优先级法、可信度法、代价法等策略时，须事先给规则设定相关的参数，即优先级、策略时，须事先给规则设定相关的参数，即优先级、可信度、代价等。可信度、代价等。产生式系统的推理方式、搜索策略及冲突消解产生式系统的推理方式、搜索策略及冲突消解策略等，一般统称为推理控制策略，或简称控制策策略等，一般统称为推理控制策略，或简称控制策略。一个产生式系统的控制策略就体现在推理机的略。一个产生式系统的控制策略就体现在推理机的算法描述中。算法描述中。6.2.3 控制策略与常用算法控制策略与常用算法

56、6.2.4 程序实现（程序实现（P.132-135） 1.产生式规则产生式规则的程序语言实现的程序语言实现2.规则库规则库的程序实现的程序实现3.动态数据库动态数据库的程序实现的程序实现4.推理机推理机的程序实现的程序实现（请同学们自学！了解一下基本情况。请同学们自学！了解一下基本情况。）6.2.3 控制策略与常用算法控制策略与常用算法6.2.4 程序实现（程序实现（P.132-135） 6.2.5 产生式系统与问题求解产生式系统与问题求解有些文献中，还介绍：有些文献中，还介绍：1）可交换的产生式系统；）可交换的产生式系统；2）可分解的产生式系统）可分解的产生式系统表表6.1 产生式系统与图搜

57、索对比产生式系统与图搜索对比产生式系统产生式系统 图搜索图搜索 初始事实数据初始事实数据 初始节点初始节点 目标条件目标条件 目标节点目标节点 产生式规则产生式规则 状态转换规则状态转换规则, ,问题变换规则问题变换规则 规则库规则库 操作集操作集 动态数据库动态数据库 节点节点( (状态状态/ /问题问题) ) 控制策略控制策略 搜索策略搜索策略 6.2.3 控制策略与常用算法控制策略与常用算法6.2.4 程序实现（程序实现（P.132-135） 6.2.5 产生式系统与问题求解产生式系统与问题求解P.136 P.136 （最后一段）（最后一段）由上述产生式系统与图搜索的关系可见，由上述产生

58、式系统与图搜索的关系可见， 这样，这样，产生式系统实际上就几乎成了人工智能问题求解系统产生式系统实际上就几乎成了人工智能问题求解系统的通用模型的通用模型。图图12-1 专家系统的概念结构专家系统的概念结构P.235人人 机机 界界 面面推理机推理机解释模块解释模块知识库知识库动态数据库动态数据库知识库管理系统知识库管理系统图图12-2 专家系统的理想结构专家系统的理想结构P.236人人 机机 界界 面面推理机推理机解释模块解释模块知识库知识库动态数据库动态数据库知识库管理系统知识库管理系统自学习模块自学习模块专家系统（专家系统（Expert System）就是具有专门领域知）就是具有专门领域知

59、识，能够像人类专家一样解决一些特定领域问题的一类识，能够像人类专家一样解决一些特定领域问题的一类知识系统。知识系统。专家系统的基本结构专家系统的基本结构人机交互界面人机交互界面推理机推理机解释器解释器知识库知识库动态数据库动态数据库知识获取知识获取知识工程师知识工程师用户用户图图12-1 专家系统的概念结构专家系统的概念结构P.235人人 机机 界界 面面推理机推理机解释模块解释模块知识库知识库动态数据库动态数据库知识库管理系统知识库管理系统图图12-2 专家系统的理想结构专家系统的理想结构P.236人人 机机 界界 面面推理机推理机解释模块解释模块知识库知识库动态数据库动态数据库知识库管理系

60、统知识库管理系统自学习模块自学习模块专家系统的基本结构专家系统的基本结构人机交互界面人机交互界面推理机推理机解释器解释器知识库知识库动态数据库动态数据库知识获取知识获取知识工程师知识工程师用户用户第第6章结束章结束作业作业P.137 P.137 第第7 7题（不用编程）题（不用编程）7、猴子摘香蕉问题。一个房间里，天花板上挂一串香猴子摘香蕉问题。一个房间里，天花板上挂一串香蕉。房间里有一只猴子，还有一只可被猴子推移的箱子，而蕉。房间里有一只猴子，还有一只可被猴子推移的箱子，而且，当猴子登上箱子时刚好能摘到香蕉。设猴子在房间的且，当猴子登上箱子时刚好能摘到香蕉。设猴子在房间的A A处，箱子在处，箱子在B B 处，香蕉