产生式系统精品课件

1、产生式系统第1页，共35页，2022年，5月20日，9点24分，星期日一、产生式规则产生式用于表示具有因果关系的知识基本形式：P Q或者 IF P THEN Q P 是产生式的前提（前件），用于指出该产生式是否可用的条件Q 是一组结论或操作（后件），用于指出当前提 P 所指示的条件满足时，应该得出的结论或应该执行的操作第2页，共35页，2022年，5月20日，9点24分，星期日2产生式规则的语义：如果前提 P 被满足，则可推出结论 Q 或执行 Q 所规定的操作例：R: IF 动物会飞 AND 会下蛋 THEN 该动物是鸟第3页，共35页，2022年，5月20日，9点24分，星期日3二、产生式系

2、统组成三要素：1、一个综合数据库存放问题求解过程中当前信息的数据结构2、一组产生式规则 描述相应领域内的知识3、一个控制系统 选择规则库中与当前综合数据库相匹配的规则并执行，必要时进行冲突消解第4页，共35页，2022年，5月20日，9点24分，星期日4产生式规则库综合数据库控制系统产生式系统的基本结构第5页，共35页，2022年，5月20日，9点24分，星期日5规则库用于描述相应领域内知识的产生式集合称为规则库有效的表达领域内的过程性的知识对知识进行合理的组织和管理综合数据库用于存放问题求解过程中各种当前信息的数据结构推理机（控制系统）第6页，共35页，2022年，5月20日，9点24分，星

3、期日6控制策略与常用算法P127-130正向推理将初始事实/数据置入动态数据库；用动态数据库中的事实/数据，匹配/测试目标条件，若目标条件满足，则推理成功，结束。用规则库中各规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集；若待用规则集为空，则运行失败，退出。将待用规则集中个规则的结论加入动态数据库，或者执行其动作，转入2；第7页，共35页，2022年，5月20日，9点24分，星期日7反向推理将初始事实/数据置入动态数据库，将目标条件置入目标链；若目标链为空，则推理成功，结束。取出目标链中的第一个目标，用动态数据库中的事实/数据同其匹配，若匹配成功，转步2；用规则集中的各

4、规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，转步3；若该目标是初始目标，则推理失败，退出。将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步3；第8页，共35页，2022年，5月20日，9点24分，星期日8一个简单的例子问题：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F第9页，共35页，2022年，5月20日，9点24分，星期日9一个简单的例子（续1）一、综合数据库x，其中x为字符二、规则集 1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THE

5、N F5，IF D THEN E第10页，共35页，2022年，5月20日，9点24分，星期日10一个简单的例子（续2）三、控制策略顺序排队四、初始条件A，B五、结束条件Fx第11页，共35页，2022年，5月20日，9点24分，星期日11一个简单的例子（续3）综合数据库可触发规则被触发规则A，B（1）（1）A，B，C（2）（3）（2）A，B，C，D（3）（5）（3）A，B，C，D，G（5）（5）A，B，C，D，G，E（4）（4）A，B，C，D，G，E，F1，IF AB THEN C 2，IF AC THEN D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN

6、E求解过程第12页，共35页，2022年，5月20日，9点24分，星期日12例：传教士与野人问题（M-C问题）问题：N个传教士，N个野人，一条船，可同时乘坐 k 个人，要求在任何时刻，在河的两岸及船上，传教士人数不能少于野人的人数。问：如何过河。以N=3，k=2为例求解。第13页，共35页，2022年，5月20日，9点24分，星期日13M-C问题（续1） L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 1L 左岸 R 右岸 B 1（有船）、0（无船）第14页，共35页，2022年，5月20日，9点24分，星期日14M-C问题（续2）1，综合数据库 （m, c

7、, b)，其中：0m, c3, b 0, 12，初始状态 （3，3，1） ( 简化，只描述左岸的情况即可 )3，目标状态（结束状态） （0，0，0）第15页，共35页，2022年，5月20日，9点24分，星期日15M-C问题（续3 ）4，规则集IF (m, c, 1) THEN (m-1, c, 0)IF (m, c, 1) THEN (m, c-1, 0) IF (m, c, 1) THEN (m-1, c-1, 0)IF (m, c, 1) THEN (m-2, c, 0)IF (m, c, 1) THEN (m, c-2, 0)第16页，共35页，2022年，5月20日，9点24分，星期

8、日16M-C问题（续4）IF (m, c, 0) THEN (m+1, c, 1)IF (m, c, 0) THEN (m, c+1, 1)IF (m, c, 0) THEN (m+1, c+1, 1)IF (m, c, 0) THEN (m+2, c, 1)IF (m, c, 0) THEN (m, c+2, 1)5，控制策略：（略）第17页，共35页，2022年，5月20日，9点24分，星期日17例：猴子摘香蕉问题abc第18页，共35页，2022年，5月20日，9点24分，星期日18猴子摘香蕉问题（续1）1，综合数据库（M, B, Box, On, H）M：猴子的位置B：香蕉的位置Box

9、：箱子的位置On=0：猴子在地板上On=1：猴子在箱子上H=0：猴子没有抓到香蕉H=1：猴子抓到了香蕉第19页，共35页，2022年，5月20日，9点24分，星期日19猴子摘香蕉问题（续2）2，初始状态（c, a, b, 0, 0）3，目标状态（x1, x2, x3, x4, 1）其中x1x4为变量。第20页，共35页，2022年，5月20日，9点24分，星期日20猴子摘香蕉问题（续3）4，规则集r1: IF (x, y, z, 0, 0) THEN (w, y, z, 0, 0)表示猴子走动r2: IF (x, y, x, 0, 0) THEN (z, y, z, 0, 0)表示猴子推动箱子

10、r3: IF (x, y, x, 0, 0) THEN (x, y, x, 1, 0)表示猴子站到箱子上r4: IF (x, y, x, 1, 0) THEN (x, y, x, 0, 0)表示猴子跳下箱子r5: IF (x, x, x, 1, 0) THEN (x, x, x, 1, 1)表示猴子摘取香蕉其中x, y, z, w为变量第21页，共35页，2022年，5月20日，9点24分，星期日21产生式表示法的特点优点：（1）自然性：“如果 ，则 ” 形式表示知识，直观、自然，便于推理。（2）模块性：规则与推理机构相对独立；对规则库的维护方便。（3）有效性：既可表示确定性知识，又可表示不确

11、定性知识；既有利于表示启发式知识，又可方便地表示过程性知识。（4）清晰性：规则格式固定，由前件与后件构成。第22页，共35页，2022年，5月20日，9点24分，星期日22局限性：（1）效率不高：求解过程是 “匹配-冲突消解-执行” 的过程，若规则库较大，易引起组合爆炸。（2）不能表示具有结构性的知识：产生式适合于表示具有因果关系的过程性知识，不能表示具有结构关系的事物间的区别与联系。第23页，共35页，2022年，5月20日，9点24分，星期日23第四节 框架表示法框架的概念框架的表达能力基于框架的推理P138-P142第24页，共35页，2022年，5月20日，9点24分，星期日24框架表

12、示法的特点：结构性：善于表达结构性的知识表达知识的内部结构关系槽-侧面-值表达知识间的联系框架网络第25页，共35页，2022年，5月20日，9点24分，星期日25继承性：通过使槽值为另一个框架的名字实现框架间的联系，建立起表示复杂知识的框架网络。在框架系统中，下层框架可以继承上层框架的槽值，也可以进行补充和修改，减少了知识的冗余。自然性：体现了人们在观察事物时的思维活动当遇到新事物时，通过从记忆中调用类似事物的框架，并将其中某些细节进行修改、补充，就形成了对新事物的认识。第26页，共35页，2022年，5月20日，9点24分，星期日26第五节 语义网络表示法语义网络奎廉（）于1968年在他的

13、博士论文中作为人类联想记忆的一个显式心理学模型最先提出的是通过概念及其语义关系来表达知识的一种网络图第27页，共35页，2022年，5月20日，9点24分，星期日27基本网元ABR 其中A、B是节点，表示事物、对象、概念、行为、性质、状态等 R 表示A、B之间的某种语义联系第28页，共35页，2022年，5月20日，9点24分，星期日28ABR1BCR2ACR3ABR1CR2三个基本网元R3合并后的语义网络第29页，共35页，2022年，5月20日，9点24分，星期日29语义网络的表达能力：P144147基于语义网络的推理P147第30页，共35页，2022年，5月20日，9点24分，星期日3

14、0例：“小信使”这只鸽子从春天到秋天占有一个窝小信使鸽子占有鸟窝情况春天时间秋天鸟窝是一只是一种是一个占有物开始于结束于是是是一种占有者第31页，共35页，2022年，5月20日，9点24分，星期日31例：黎明的自行车是飞鸽牌，黑色，28型 刘华的自行车是金狮牌，红色，26型人28型黎明飞鸽刘华红色交通工具金狮黑色车名是一种所有者颜色车型是自行车-1自行车自行车-226型是所有者车型是是车名颜色第32页，共35页，2022年，5月20日，9点24分，星期日32例：每个学生都背诵了一首唐诗GS学生g背诵rsp唐诗ISA是是是主体客体F第33页，共35页，2022年，5月20日，9点24分，星期日33语义网络表示法的特点优点：（1）结构性：是一种结构化的表示方法，能把事物的属性及事物间的各种语义联系显式地表示出来。（2）联想性：强调事物间的语义联系，通过这些联系很容易地找到与某一节点有关的信息。（3）自