第3章 产生式系统.ppt

《第3章 产生式系统.ppt》由会员分享，可在线阅读，更多相关《第3章 产生式系统.ppt（100页珍藏版）》请在课桌文档上搜索。

1、1,第3章 产生式系统,2,内容提要,产生式系统的描述推理控制策略两类特殊的产生式系统基于规则的演绎系统,产生式系统的描述推理控制策略两类特殊的产生式系统基于规则的演绎系统,3,产生式系统的描述,产生式一种知识表示方法，常用来表示有因果关系的知识。,前提 结论,条件 行动,下雨地面湿,烫手缩手,形式:,IF(conditions)THEN(actions),4,产生式系统的描述,产生式,左边表示条件,右边表示结论,例如：下雨甲未打伞甲被淋湿,5,产生式系统的描述,产生式系统把一组产生式放在一起，让它们互相配合，协同作用，一个产生式的结论可以供另一个产生式作为前提使用，以这种方式求解问题的系统称

2、为产生式系统。,AB,BC,CD,AD,？,6,产生式系统的描述,历史 1943年，美国数学家Post设计的产生式系统，称为Post系统。目的是构造一种形式化的计算工具。证明它和图灵机具有相同的计算能力。,7,产生式系统的描述,产生式系统的构成一组产生式规则(set of rules)综合数据库(global database)控制机制(control system),8,产生式系统的描述,产生式规则例子下雨地面湿下雨甲未打伞甲被淋湿 所有人会死甲是人甲会死,9,产生式系统的描述,综合数据库存放已知的事实和推导出的事实;数据基(global database);和database（数据库）不同

3、:database:强调数据的管理（存取、增、删、改等）产生式系统:抽象的概念只是说明数据在此存放，和物理实现没关系。具体实现时，用DBMS和文件等都可以。数据是广义的，可以是常量、变量、谓词、图像等。数据结构:符号串、向量、集合、数组、树、表格、文件等;,10,产生式系统的描述,控制机制控制机制完成的工作有：匹配规则条件部分；多于一条规则匹配成功时，选择哪条规则执行(点燃)；如何将匹配规则的结论部分放入综合数据库（是直接添加到数据库中，还是替换其中的某些东西）；决定系统何时终止；,11,产生式系统的描述,产生式系统的运行过程,建立产生式规则；,考察每一条产生式规则，如果条件部分和综合数据库中

4、的数据匹配，则规则的结论放入综合数据库；,将已知的事实放入综合数据库；,12,产生式系统的算法,初始化综合数据库,是否满足终止条件,是否有可以应用的规则,选择一条规则作用于综合数据库,NO,YES,END,YES,NO,13,产生式系统的描述,算法,14,产生式系统的描述,例1-八数码游戏(eight puzzle),15,产生式系统的描述,游戏说明：一个棋盘有9个方格，放了8个数（1-8）；初始时，8个数随机放置；数字移动规则：空格周围的数字可移动到空格中；如果通过移动数字，达到一个目标状态，则游戏成功结束；求一个走步序列;,问题：怎样用一个产生式系统描述并解决上述问题？,16,产生式系统的

5、描述,综合数据库：存放棋盘的状态。棋盘的状态：8个数字在棋盘上的位置分布。每走一步，状态就会发生变化；存放棋盘的当前状态；,规则：规则是数字移动的方法。空格的移动:如果空格左边有数字，则将左边的数字移到空格上；如果空格右边有数字，则将右边的数字移到空格上；如果空格上边有数字，则将上边的数字移到空格上；如果空格下边有数字，则将下边的数字移到空格上；,控制机制：用当前数据库与规则左半部分进行匹配，确定可执行的规则集；从中选择一条规则执行，用规则的右半部分代替数据库中的状态；如果当前数据库中的状态与目标状态相同，则终止;,17,产生式系统的描述,例2：问题：设字符转换规则ABCACDBCGBEFDE

6、已知：A，B求：F,综合数据库,x，其中x为字符,规则集,1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E,18,产生式系统的描述,控制策略:顺序排队,初始条件A，B结束条件Fx规则：1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E,数据库,可触发规则,被触发规则,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

7、，F,(4),(4),A，B，C，D，G，E,求解过程,19,产生式系统的描述,例3:猴子摘香蕉问题,综合数据库（M,B,Box,On,H）M：猴子的位置B：香蕉的位置Box：箱子的位置On=0：猴子在地板上On=1：猴子在箱子上H=0：猴子没有抓到香蕉H=1：猴子抓到了香蕉,初始综合数据库（a,b,c,0,0）结束综合数据库（x1,x2,x3,x4,1）其中x1x4为变量。,20,产生式系统的描述,例3:猴子摘香蕉问题（M,B,Box,On,H）规则集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)r3:IF(x,y

8、,x,0,0)THEN(x,y,x,1,0)r4:IF(x,x,x,1,0)THEN(x,x,x,1,1)其中x,y,z,w为变量,21,产生式系统的描述,产生式系统的特点规则的表示形式固定：规则分为左半部分和右半部分；左半部分是条件，右半部分是结论；知识模块化：知识元：通俗的说，知识元是产生式规则的条件中的独立部分，Ai；所有的规则或数据库中的数据都是由知识元构成；,22,产生式系统的描述,产生式系统的特点(续)产生式之间的相互影响是间接的产生式之间的作用通过综合数据库的变化完成，因此是数据驱动的；易扩展:规则的添加和删除较为自由，因为没有相互作用；添加规则不能造成矛盾；AB，AB。系统自动

9、完成?谓词情况困难；可解释性,23,产生式系统的描述,适用领域对某些领域适用，而对某些领域不适用;按照知识的性质，可将系统划分为两种知识由许多独立的知识元组成，彼此之间的关系不很密切；(西医)有一个很小的核心，其它部分由此核心推导出来，或彼此纠缠，形成一个整体，难以分割。(数学)产生式系统适合于前者，不适合后者。知识是否可以模块化。,24,推理,推理(reasoning)从某些已知事实依照推理规则推出另外一些结论的过程。系统状态的转换;向前推理(正向推理)：向后推理(反向推理)：,25,推理,正向推理基本思想：从用户提供的初始己知事实出发，在规则集中找出当前可适用的规则,然后进行推理，并将推出

10、的新事实加入到综合数据库中作为下一步推理的已知事实,在此之后再在知识库中选取可适用的规则进行推理，如此重复进行这一过程，直到求得了所要求的解或者没有知识可用用综合数据库与规则的条件部分匹配，并用规则的结论部分修改综合数据库;,26,推理,正向推理,算法,27,28,推理,积木世界,初始状态,目标状态,29,推理,知识元：HANDEMPTY，Holding(x),Ontable(x),Clear(x),On(x,y)规则:R1:Pickup(x):机械手从桌子上拿起积木x。HANDEMPTY Ontable(x)Clear(x)Holding(x)R2:Putdown(x):机械手把拿着的积木放

11、在桌子上。Holding(x)HANDEMPTY,Ontable(x),Clear(x)R3:Unstack(x,y):积木x在积木y上,机械手拿起x。HANDEMPTY On(x,y)Clear(x)Holding(x),Clear(y)R4:Stack(x,y):机械手把拿着的积木x放在积木y上。Holding(x)Clear(y)HANDEMPTY,On(x,y),Clear(x),30,推理,综合数据库 初始状态：(HANDEMPTY，Ontable(A)，Ontable(B),On(C,A),Clear(C),Clear(B)目标状态：(Ontable(A)，On(B,A),On(C

12、,B),Clear(C),初始状态,目标状态,31,推理,(HANDEMPTY，Ontable(A)，Ontable(B),On(C,A),Clear(C),Clear(B)R3:Unstack(C,A)HANDEMPTY On(x,y)Clear(x)Holding(x),clear(y)(Holding(C)，Ontable(A)，Ontable(B),Clear(B),Clear(A),32,推理,(Holding(C)，Ontable(A)，Ontable(B),Clear(B),Clear(A)R2:Putdown(c)Holding(x)HANDEMPTY,Ontable(x),C

13、lear(x)(HANDEMPTY，Ontable(A)，Ontable(B),Ontable(C),Clear(A),Clear(B),Clear(C),33,推理,(HANDEMPTY，Ontable(A)，Ontable(B),Ontable(C),Clear(A),Clear(B),Clear(C)R1:Pickup(B)HANDEMPTY Ontable(x)Clear(x)Holding(x)(Holding(B),Ontable(A)，Ontable(C),Clear(A),Clear(C),34,推理,(Holding(B),Ontable(A)，Ontable(C),Clea

14、r(A),Clear(C)R4:Stack(B,A)Holding(x)Clear(y)HANDEMPTY,On(x,y),Clear(x)(HANDEMPTY,Ontable(A)，Ontable(C),On(B,A),Clear(B),Clear(C),A,C,B,35,推理,(HANDEMPTY,Ontable(A)，Ontable(C),On(B,A),Clear(B),Clear(C)R1:Pickup(C)HANDEMPTY Ontable(x)Clear(x)Holding(x)(Holding(B),Ontable(A)，Ontable(C),On(B,A),Clear(B),

15、36,推理,(Holding(C),Ontable(A)，On(B,A),Clear(B)R4:Stack(C,B)Holding(x)Clear(y)HANDEMPTY,On(x,y),Clear(x)(HANDEMPTY,Ontable(A)，On(B,A),On(C,B),Clear(C),37,推理,例：动物世界规则:R1：动物有毛 哺乳类 R2：动物产奶 哺乳类 R3：哺乳类 吃肉 食肉类 R4：哺乳类 吃草 有蹄类 R5：食肉类 黄褐色 有斑点 猎狗 R6：食肉类 黄褐色 黑条纹 虎 R7：有蹄类 长脖 长颈鹿 R8：有蹄类 黑条纹 斑马,38,推理,例：动物世界规则集的树表示,规

16、则:R1：动物有毛 哺乳类 R2：动物产奶 哺乳类 R3：哺乳类 吃肉 食肉类 R4：哺乳类 吃草 有蹄类 R5：食肉类 黄褐色 有斑点 猎狗 R6：食肉类 黄褐色 黑条纹 虎 R7：有蹄类 长脖 长颈鹿 R8：有蹄类 黑条纹 斑马,39,推理,例：动物世界问题：观察到一种动物是有毛，吃草，黑条纹，问是不是斑马？推理过程：寻找结论是斑马的规则，看它的条件部分是否可以被当前综合数据库满足。如果是，则结束；否则，看哪些条规则能推出这些条件（规则的结论与这些条件匹配）。重复这个过程。,40,推理,例：动物世界问题：观察到一种动物是有毛，吃草，黑条纹，问是不是斑马？具体推理过程有毛，吃草，黑条纹R1：

17、动物有毛 哺乳类 R2：动物产奶 哺乳类 R3：哺乳类 吃肉 食肉类 R4：哺乳类 吃草 有蹄类 R5：食肉类 黄褐色 有斑点 猎狗 R6：食肉类 黄褐色 黑条纹 虎 R7：有蹄类 长脖 长颈鹿 R8：有蹄类 黑条纹 斑马,41,推理,例：动物世界问题：观察到一种动物是有毛，吃草，黑条纹，问是不是斑马？具体推理过程有毛，吃草，黑条纹R1：动物有毛 哺乳类 R2：动物产奶 哺乳类 R3：哺乳类 吃肉 食肉类 R4：哺乳类 吃草 有蹄类 R5：食肉类 黄褐色 有斑点 猎狗 R6：食肉类 黄褐色 黑条纹 虎 R7：有蹄类 长脖 长颈鹿 R8：有蹄类 黑条纹 斑马,42,推理,例：动物世界问题：观察到

18、一种动物是有毛，吃草，黑条纹，问是不是斑马？具体推理过程有毛，吃草，黑条纹R1：动物有毛 哺乳类 R2：动物产奶 哺乳类 R3：哺乳类 吃肉 食肉类 R4：哺乳类 吃草 有蹄类 R5：食肉类 黄褐色 有斑点 猎狗 R6：食肉类 黄褐色 黑条纹 虎 R7：有蹄类 长脖 长颈鹿 R8：有蹄类 黑条纹 斑马,43,推理,反向推理基本思想：首先选定个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需要的证据，说明原假设不成立，此时需要另作新的假设。,44,推理,反向推理,45,推理,反向推理,46,推理,反向推理的特点优点:不必使用与目标无关的知识，

19、目的性强，有利于向用户提供解释。缺点:初始目标的选择有盲目性，若不符合实际，就要多次提出假设，影响到系统的效率。,47,推理,反向推理的特点注意 向前推理是从事实到目标的推理，称为数据驱动的推理;向后推理是从假设目标为真，再用事实证明这个目标为真，称为目标驱动的推理;向前推理还是向后推理，由问题决定:向前推理:机器人规划，程序自动设计；向后推理:诊断问题。一起使用;,48,推理,混合推理正向推理具有盲目、效率低等缺点，可能推出许多与问题求解无关的子目标;逆向推理若提出的假设目标不合适，也会降低系统的效率。正向推理+逆向推理?混合推理,1.robin(x)bird(x)2.robin(x)sma

20、ll(x)3.robin(x)red breast(x)4.bird(x)animal(x)5.bird(x)Has Wings(x)6.redbreast(x)colourful(x)7.redbreast(x)attractive(x)8.small(x)not large(x)9.small(x)not medium(x),推理,50,控制策略,选取规则的原则称为控制策略;不可撤回的控制策略：在任意时刻，如果从被激励的规则集中选择点燃的规则都是合适的，即，使用这条规则所求的解，一定在全局解的路径上。特点：局部解与全局解是一致的。,51,控制策略,试探性控制策略使用某条规则时,必须为以后应

21、用另一条规则做好准备;回溯型:特点：每个被放弃的状态，可以保证不在解路上。,52,控制策略,图搜索 任一个暂时放弃的状态，将来都可能被重新使用;,53,控制策略,注意：效率最高:不可撤回的控制策略效率最低:图搜索,54,控制策略,冲突删除策略规则的状态:激励：如果某规则的全部条件与综合数据库匹配，此规则处于激励状态。点燃：根据策略从激励的规则中选取一个执行，称此规则被点燃。,55,控制策略,当激励的规则多于一条时，选择哪条点燃，策略有两种：领域相关:启发式知识领域无关:冲突删除策略(并不是严格领域无关),56,控制策略,重要性排序新旧排序 匹配程度排序数据排序 特殊排序,57,控制策略,重要性

22、排序 产生式规则事先按照重要性排序;当多条规则被激励时，选择最重要的规则点燃。,58,控制策略,新旧排序 如果规则的获取时间不同，新得到的知识比旧知识更先点燃。匹配程度排序非确定性匹配中，如果有加权的情况，按照规则的权值大小排序。数据排序 重要性排序：对知识元事先按重要性排序。被激励的规则的条件部分第一个文字在综合数据库中的重要性，决定点燃的规则。例：A，B，C，D，ER1：ADE R2：BC 先执行R1.新旧排序：新进入综合数据库的数据优先级高。,59,控制策略,特殊排序 更特殊的规则先执行。尺寸排序：条件多的先执行。R1：ABC R2：DE 先执行R1.包含排序:两个规则的条件部分，一个是

23、另一个的子集，执行全集的那条(尺寸排序的特例)R1：ABC R2：AB 先执行R1.,60,控制策略,有时是矛盾的;例如尺寸排序和数据排序;论域知识很重要;,61,两类特殊的产生式系统,可交换产生式系统 可分解产生式系统,62,两类特殊的产生式系统,可交换产生式系统 使用规则的次序不影响产生的结果;例子：r1r2r3r1r3r2r2r1r3r2r3r1r3r1r2r3r2r1,63,两类特殊的产生式系统,可交换产生式系统,64,两类特殊的产生式系统,可交换产生式系统 如果一个产生式系统对任意数据库都满足如下条件，则称这个产生式系统是可交换的:令R是可作用于数据库D的规则集，ri R，作用于D产

24、生D，则R中的任一条规则均可作用于D。如果D满足目标条件，那么可作用于D上的任一条规则，作用于D后产生D，也满足目标条件。令R是可作用于数据库D的规则集，对数据库D来说，使用规则ri R的顺序不影响从D 到D。,65,两类特殊的产生式系统,可交换产生式系统 特点可交换产生式系统可以采用不可撤回的搜索策略;但相反不成立。效率高;纯粹的可交换产生式系统一般不存在，但一个系统的局部可能满足这个条件;,66,两类特殊的产生式系统,可分解产生式系统如果一个系统可将其数据库分为几个子数据库，并通过规则作用于子数据库，而达到目标，这个系统称为可分解产生式系统。,规则集合,67,两类特殊的产生式系统,可分解产

25、生式系统例子:初始数据库：（C,B,Z）目标数据库：（M,M,M）规则：R1:C(D,L)R2:C(B,M)R3:B(M,M)R4:Z(B,B,M),68,两类特殊的产生式系统,可分解产生式系统SPLIT算法：1DATA初始数据库；2DiDATA的分解表示。每个Di为一个子数据库；3直到所有Di满足结束条件。3.1 从Di中选择不满足结束条件的数据库D*;3.2 从Di中删除D*;3.3 选择一条可作用于D*的规则R;3.4 DR作用于D*所产生的结果;3.5 diD的分解表示;3.6 将di加入Di中;,69,两类特殊的产生式系统,可分解产生式系统SPLIT算法：,规则：R1:C(D,L)R

26、2:C(B,M)R3:B(M,M)R4:Z(B,B,M),70,两类特殊的产生式系统,可分解产生式系统注意：关键在于如何用控制策略选择规则;如果一个问题使用这个算法，可以终止，则这个问题是可分解的，否则是不可分解的；具体来说，数据库如何分解，是领域相关的。分解的一个好处是可用分布式系统求解。,71,两类特殊的产生式系统,应用Slagle,1963,符号积分程序SAINT产生式求解系统输入:不定积分题目输出:积分结果例子:xsin3xdx1/9(sin3x)1/3(xcos3x)软件：Mathematica,Maple,Matlab,James Robert Slagle,72,两类特殊的产生式

27、系统,应用产生式规则集:分部积分规则:udv udv-vdu 和式分解规则:(f(x)+g(x)dx f(x)dx+g(x)dx因子规则:kf(x)dx kf(x)dx相除化简变换:z4/(z2+1)dz(z2-1+1/(z2+1)dz,73,两类特殊的产生式系统,应用由于任意一个含有积分和式的表达式均可分解为若干个单独的积分式，每一个积分式又可单独进行求解，因此可以看成是一个可分解产生式系统.,74,两类特殊的产生式系统,应用,75,两类特殊的产生式系统,产生式系统的应用专家系统分类：诊病，故障诊断 规划：机器人规划，自动程序设计、自动电路设计等,76,两类特殊的产生式系统,固定的产生式系统

28、(Fixed production system)只能解决某些特定的问题，没有学习的功能.自适应的产生式系统(Adaptive Production system)是一种计算机程序，能够在问题解决的过程中建构新的产生式规则，并把这些规则加到它的“记忆”中去，从而能更加有效地解决问题。例子:一个学生由于迟到而没有听到老师的讲课；但在课堂上，他看了其他的学生的解题作业；在课后的测试中，这个迟到的学生正确地完成了所有的测试题。,77,基于规则的演绎系统,归结方法的缺点：不便于阅读与理解。“鸟能飞”：(x)(Bird(x)fly(x)子句：Bird(x)fly(x)不够直观，自然,78,基于规则的演绎

29、系统,归结方法的缺点：有可能丢失一些重要的控制信息。(AB)C(AC)B(BC)AA(BC)B(AC)C(AB)子句:A B C,79,基于规则的演绎系统,基于规则的演绎系统(与/或形演绎推理)分类正向演绎反向演绎双向演绎,80,基于规则的演绎系统,基本定义在谓词逻辑中，把原子公式和原子公式的否定统称为文字。任何文字的析取式称为子句。,81,基于规则的演绎系统,正向演绎已知事实用不含蕴含符号“”的与或形表示。与或形无量词约束否定符只作用于单个文字只有“与”()、“或”()例子:(u)(v)(Q(v,u)(R(v)P(v)S(u,v)=(u)(v)(Q(v,u)(R(v)P(v)S(u,v)=Q

30、(v,a)(R(v)P(v)S(a,v)Skolem化=Q(w,a)(R(v)P(v)S(a,v)主合取元变量换名,82,基于规则的演绎系统,事实的与或树表示例：Q(w,A)(R(v)P(v)S(A,v),解图集：Q(w,a),R(v)S(a,v),P(v)S(a,v),83,基于规则的演绎系统,规则表示规则的形式(F规则)：L W其中，L是单文字，W是与或形，变量受全称量词约束例：(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)（消去蕴含符）=(x)(y)(z)P(x,y,z)(u)Q(x,u)（否定符移植谓词前）=(x)(y)(z)

31、(u)(P(x,y,z)Q(x,u)（化为前束形）=P(x,y,f(x,y)Q(x,u)(略去全称量词）=P(x,y,f(x,y)Q(x,u)例：(L1 L2)W=L1 W 和 L2 W,84,基于规则的演绎系统,命题逻辑例：事实：(P Q)R)(S(T U)规则：S(X Y)Z,85,基于规则的演绎系统,P Q SP Q T US RR T UP Q X ZP Q Y ZP Q T UR X ZR Y ZR T U,规则的子句：S(X Y)Z=S（(X Y)Z）=S X Z S Y Z,结论：加入规则后得到的解图，是事实与规则对应子句的归结式,86,基于规则的演绎系统,目标表示和结束条件目标

32、表示化为析取式结束条件找到一个终止在目标节点上的解图;,87,基于规则的演绎系统,目标表示和结束条件例：事实：A B规则集：A C D B E G目标公式：C G,88,基于规则的演绎系统,谓词逻辑的情况事实表达式化成与或形规则化成L W的形式，其中L为单文字目标用Skolem 化的对偶形式，即消去全称量词，用Skolem函数代替保留存在量词对析取元作变量换名例：(y)(x)(P(x,y)Q(x,y)=(y)(P(f(y),y)Q(f(y),y)=P(f(y1),y1)Q(f(y2),y2)换名,89,基于规则的演绎系统,谓词逻辑的情况例：事实：P(x,y)(Q(x,A)R(B,y)规则集：P

33、(A,B)(S(A)X(B)Q(B,A)U(A)R(B,B)V(B)目标：S(A)X(B)U(A)V(B),90,基于规则的演绎系统,规则集：P(A,B)(S(A)X(B)Q(B,A)U(A)R(B,B)V(B)目标：S(A)X(B)U(A)V(B),91,基于规则的演绎系统,一个问题:置换是否相容?事实:P(x)Q(x)规则:P(A)R(A)Q(B)R(B)目标:R(A)R(B),92,基于规则的演绎系统,一致(consistent)解图如果一个解图中所涉及的置换是一致的，则该解图称为一致解图。设有置换集u1,u2,un,其中ui=ti1/vi1,ti,mi/vi,mi，定义表达式U1=(v

34、11,v1,m1,vn1,vn,mn),U2=(t11,t1,m1,tn1,tn,mn)置换集u1,u2,un称为一致的，当且仅当U1和U2是可合一的。U1、U2的mgu是u1,u2,un的合一复合。,93,基于规则的演绎系统,例子,94,基于规则的演绎系统,正向演绎系统小结事实表达式为与或形规则形式：L W,其中L为单文字目标公式为文字析取对事实和规则进行Skolem化，消去存在量词，变量受全称量词约束，对主合取元和规则中的变量换名用“对偶形”对目标进行Skolem化，消去全称量词，变量受存在量词约束，对析取元中的变量换名从事实出发，正向应用规则，到得到目标节点为结束的一致解图为止存在合一复

35、合时，则解图是一致的;,95,基于规则的演绎系统,反向演绎系统目标表示用“对偶形”对目标进行Skolem化，即消去全称量词，变量受存在量词约束，对主析取元中的变量换名合取用连接符连结;,96,基于规则的演绎系统,反向演绎系统事实表示合取式;规则表示L W 其中W为单文字，如果形为：L W1 W2，则变换为：L W1 和 L W2终止条件:包含一个终止于事实节点的一致解图.,97,基于规则的演绎系统,反向演绎的例子事实:P L规则:LTQ目标:P(QS),98,基于规则的演绎系统,双向演绎起因:正向演绎要求目标公式是文字的析取式，逆向演绎推理要求事实公式为文字的合取式，都有定的局限性为克服这些局限性，并充分发挥各自的长处可进行双向演绎推理。例子:规则:S(XY)Z终止条件解图终止;连接弧与非连接弧对应;连接弧必须保证所有出发的枝都相接;非连接弧节点只要保证有一枝相接;一致;,99,100,作业,程序设计，用产生式系统求解下列问题：设有N(本次设计控制在1-9之间，下同)个传教士和N个野人同在河的左岸，他们都要到对岸去；河里只有一条船，他们都会划船，但每次渡船至多只能乘N人；如果在任何一边河岸上，野人的数量超过传教士，野人就要吃掉传教士。问怎样才能用船将N个传教士和N个野人从左岸都渡到右岸，又不会发生传教士被吃的事件呢？,