《产生式系统》.ppt

第五章 产生式系统n产生式表示方法n产生式系统基本原理n产生式系统与图搜索n产生式系统应用Date1.第五章 产生式系统 产生式系统的体系结构是 实现图搜索的理想程序结构，产生式已是人工智能系统的一种最典型最普遍的结构形式 许多专家系统和机器学习系统都是用产生式系统实现的从结构形式上看很多人工智能系统都是产生式系统Date2.第五章 产生式系统n产生式表示方法n产生式系统基本原理n产生式系统与图搜索n产生式系统应用Date3.产生式表示法n产生式n产生式一词是从波斯特机中借用来的波斯特机是一种自动机，它是根据串替换规则提出的一种计算模型其中的每一条规则就叫一个产生式也称产生式规则，简称规则n这里产生式就是前面讨论过的操作、逻辑蕴含式、推理规则以及各种关系（包含经验性联想）的一种逻辑抽象 Date4.产生式表示法n产生式的一般形式为：n前件后件（情况行为）n前件是前提，规则的执行条件 后件是结论或动作，规则体n产生式规则的语义：如果前提满足，则可得结论或者执行相应的动作，即后件由前件触发n从基本事实到结论之间的复杂推理可以借助中间结论形成小型简单产生式Date5.产生式表示法例：一条知识的原始形态是 R: ( (A B) (C D) (E F) G)=S 引入中间结论S1，S2，形成一些小型的产生式: R1： A B =S1 R2： C D =S1 R3： E F =S2 R4： S1 G =S R5: S1 S2 =SDate6.产生式表示法n给定一组事实之后可用匹配技术寻找可用产生式，其基本思想是将已知事实代入产生式的前件，若前件为真，则该产生式是可用的。

n提高匹配效率的方法n索引匹配为状态建立可用产生式索引表，减少可用产生式搜索范围n分层匹配将产生式分成若干层或组，按一定特征进行分层搜索n过滤匹配边匹配边 按某些附加特征或参数对可用产生式进行精选Date7.产生式表示法n如果一组事实可以同时使几个产生式前提为真，常用以下方法进行选择（冲突消解策略）：n将所有产生式排序，选最早匹配成功的一个，不管其余的产生式；n在所有匹配成功的产生式中取最强的，即前提条件最多或情况元素最多者；n最近用过的产生式优先（或反之）；n给情况元素以不同的优先权；n使用估计函数f(x)排序；n利用上下文限制Date8.产生式表示法n在产生式系统中，从前提到结论通常也是一棵与或树n合取，与节点：一个产生式的前提包含了几个事实，那么它的结论对应这些事实的合取n析取，或节点：一个结论可以由多个产生式得到，则这个结论对应这些产生式的析取n每个产生式系统都隐含着许多这样的与或树Date9.产生式表示法F1P1F3F4F5F6BCDAP2P3P4P5F2事实中介事实B、C、D产生式规则P1、P2、P3、P4、P5结论Date10.产生式表示法（例）例 三个聪明人问题古代有个国王想知道他的三个大王中谁最聪明，就在他们每个人前额上都画了一个点，他们都能看到别人点的颜色，但看不到别人点的颜色。

国王说，你们中间至少有一个人的点式白色的于是重复地问他们：“谁知道自己点地颜色？”三位大臣们头两次都回答说不知道题目要求证明下一次他们全都会说“知道”，并且所有的点都是白色Date11.产生式表示法（例）分析： 这类问题的特点是有有限个受试者，每个人对问题都只有部分了解，无法直接求解但在推理过程中每个人又可以从别人那里获得新的知识，重新进行推理可以用产生式来表达推理过程中所用到的各种知识Date12.产生式表示法（例）状态集合表示： 用x1,x2,x3表示三个人点的颜色，1表示白色，0表示非白色 X(x1,x2,x3)表示颜色分布状态 全部可能的状态集合(可能界PW0)：(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) 实际给定的状态为现实界X0 (x10,x20,x30) 用排除法找到X0 Date13.产生式表示法（例）排除过程：n第一次，大臣只知道至少有一个人是白点，排除X0(0,0,0)状态这时如果有人看到两个非白点，根据排除的状态可推知自己是白点n第二次大臣根据没有一个人知道自己点颜色的事实推知至少两人为白点。

排除(0,0,1)(0,1,0)(1,0,0)状态这时如果有人看到一个非白点，根据排除后得到的状态可推知自己的点是白的n第三次，大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现，即X0(1,1,1)于是三人都知道自己点的颜色是白的Date14.产生式表示法（例）引入中介状态并定义下述符号： Si i大臣看到的非白点数； Wi i大臣猜出自己点的颜色否如果他宣布已知道自己点的颜色，为1，否则为0； nX0中白点的个数 Date15.产生式表示法（例）(1)(已知)(n=1) X0 (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)；(2)(有人看见两个非白点)(n=1) (Si=2) =(Wi=1),(i=1,2,3,下同)；(3)( i ) (Wi=1) (n=1) = (n=1) ；(4) (n=1) = ( i ) (Wi=1) ；(5) ( i ) (Wi=0) (n=1) = (n=2) ;(6) (n=2) X0 (0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)；(7) (有人看见一个非白点)(n=2) (Si=1) =(Wi=1);(8) ( i ) (Wi=1) (n=2) = (n=2) ;(9) (n=2) = ( i ) (Wi=1);(10) ( i ) (Wi=0) (n=2) = (n=3);(11) (n=3) X0 (1,1,1)；(12) (n=3) = ( i ) (Wi=1).Date16.产生式表示法（例） 上述结果可以推广到更一般的情况：设有m个大臣，国王说至少有l个人的点是白色的，则有下述产生式： (1) (n=l) X0 x|x中的白点数=l； (2) (n=l) (Si=2) =(Wi=1),(i=1,2,m,下同)； (3)( i ) (Wi=1) (n=l) = (n=l) ； (4) (n=l) = ( i ) (Wi=l) ； (5)( i ) (Wi=0) (n=l) (l (n=l1) ; (6)( i ) (Wi=0) (n=l) (lm-1)= (nm)。

Date17.第五章 产生式系统n产生式表示方法n产生式系统基本原理n产生式系统与图搜索n产生式系统应用Date18.产生式系统基本原理n组成和分类n运行过程n常用算法Date19.产生式系统基本原理（组成和分类）n产生式系统结构产生式规则库(知识库)推理机（控制）全局数据库Date20.产生式系统基本原理（组成和分类）n组成n全局数据库人工智能系统的数据结构中心是一个动态数据结构，用来存放初始事实数据、中间结构和最后结果对应叙述性知识n产生式规则库作用在全局数据库上的一些规则的集合每条规则都有一定的条件，若全局数据库中内容满足这些条件可调用这条规则对应过程性知识n推理机负责产生式规则的前提条件测试或匹配，规则的调度和选取，规则体的解释和执行对应控制性知识Date21.产生式系统基本原理（组成和分类）例 旅行推销员问题求从A城出发，经过其他城市一次且仅一次，最后回到A城的最小费用路线城市之间的交通费用标在相应的联线上建立产生式系统BCADE71310965671010Date22.产生式系统基本原理（组成和分类）（1）全局数据库（已访问过的城镇名称序列）约束条件是除城镇A之外其他名称不得在序列中重复出现；只有所有的名称都在序列中出现后，城镇A才能重复出现。

2）规则集如下表所示3）推理： （A） （AB） （ABE） （4）终止条件序列始于A，终止于A，其中包含其他所有城镇一次，且费用最少5）各种搜索策略选择规则，如广度优先搜索，最好优先搜索等 R2R5Date23.产生式系统基本原理（组成和分类）规则集 规则动作条件R1下一步到A系列中包含所有城镇时可用R2下一步到B每条规则只能使用一次，即序列中已有某城镇时，不能再使用相应规则R3下一步到CR4下一步到DR5下一步到EDate24.产生式系统基本原理（组成和分类）n与一般分级组织的计算机软件相比具有特点：n全局数据库的内容可以为所有规则所访问，没有任何部分是专为某一规则建立的，这种特性便于模仿智能行为中的强数据驱动n规则本身不调用其他规则规则之间的联系必须通过全部数据库联系n全局数据库、规则和推理机之间相对独立，这种积木式结构便于整个系统增加和修改知识Date25.产生式系统基本原理（组成和分类）n分类体系（尼尔逊）n按搜索策略分n不可挽回（irreversible）的产生式系统n试探性的（Tentative）产生式系统n回溯式（Backing）产生式系统n图搜索式（Graph Search）产生式系统n按搜索方向分n向前产生式系统（Forward Production System）n向后产生式系统（Backward Production System）n双向产生式系统（Bidirectional Production System）n两种特殊的产生式系统n可交换的（Commutative）产生式系统n可分解的（Decomposable）产生式系统Date26.产生式系统基本原理n组成和分类n运行过程n控制策略与常用算法Date27.产生式系统基本原理（运行过程）n推理机一次运行过程从规则库中取出一条规则，将其前提同当前动态数据库中的事实进行模式匹配匹配成功否？把该规则的结论放入当前动态数据库；或执行规则所规定的动作YNDate28.产生式系统基本原理（运行过程）n产生式系统运行过程n实际的产生式系统，目标条件往往要经过多步推理才能满足或者证明问题无解。

产生式系统的运行过程就是推理机不断的运用规则库中的规则，作用于动态数据库，不断进行推理并不断检测目标条件是否被满足的过程n产生式系统运行过程是从初始事实出发，寻求到达目标条件的通路的过程所以也是一个搜索的过程Date29.产生式系统基本原理n组成和分类n运行过程n常用算法Date30.产生式系统基本原理（常用算法）n推理方式n正向推理 从初始事实数据出发，正向使用规则进行推理，朝目标方向前进又称为前向推理、正向链、数据驱动的推理n反向推理 从目标出发，反向使用规则进行推理，朝初始事实或数据方向前进又称反向推理、反向链、目标驱动的推理Date31.产生式系统基本原理（常用算法）n正向推理算法步1 将初始事实/数据置入动态数据库；步2 用动态数据库中的事实匹配目标条件，若目标条件满足，推理成功，结束步3 用规则库中各规则的前提匹配动态数据库中的事实，将匹配成功的规则组成待用规则集步4 若待用规则集为空，则运行失败，退出步5 将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步2Date32.产生式系统基本原理（常用算法）n反向推理算法步1 将初始事实/数据置入动态数据库，将目标条件置入目标链；步2 若目标链为空，则推理成功，结束。

步3 取出目标链中第一个目标，用动态数据库中的事实同其匹配，若匹配成功，转步2步4 用规则集中的各规则的结论同该目标匹配，若匹配成功，则33将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标加入目标链，转步3步5 若该目标是初始目标，则推理失败，退出步6 将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步3Date33.产生式系统基本原理（常用算法）例：动物识别系统的产生是系统描述及求解规则：r1： IF 该动物有毛发 THEN 该动物是哺乳动物r2： IF 该动物有奶 THEN 该动物是哺乳动物r3： IF 该动物有羽毛 THEN 该动物是。