第6章基于产生式规则的机器推理

1、第第6 6章章 基于产生式规则的机器推理基于产生式规则的机器推理2022-4-22人工智能2第第6章基于产生式规则的机器推理章基于产生式规则的机器推理6.1 6.1 产生式规则产生式规则6.2 6.2 产生式系统产生式系统2022-4-22人工智能36.1.16.1.1产生式规则（产生式规则（1）产生式（产生式（ProductionProduction）-1943-1943年美国数学家年美国数学家PostPost在计算在计算形式体系中提出的术语形式体系中提出的术语产生式产生式一词从波斯特机中借用来的。波斯特机是一一词从波斯特机中借用来的。波斯特机是一种自动机，它是根据串替换规则提出的一种计算模

2、种自动机，它是根据串替换规则提出的一种计算模型。型。产生式就是逻辑蕴含式、推理规则以及各种关系产生式就是逻辑蕴含式、推理规则以及各种关系（包含经验性联想）的一种逻辑抽象。（包含经验性联想）的一种逻辑抽象。 产生式系统在形式上很简单，但在一定意义上模仿产生式系统在形式上很简单，但在一定意义上模仿了人类思考的过程。了人类思考的过程。人工智能使用产生式的理由人工智能使用产生式的理由为什么要采用产生式系统作为人工智能系统的为什么要采用产生式系统作为人工智能系统的主要结构呢？两点理由：主要结构呢？两点理由：用产生式系统结构求解问题的过程用产生式系统结构求解问题的过程和人类求解问题和人类求解问题时的思维过

3、程相似时的思维过程相似，因而可以用来模拟人类求解问，因而可以用来模拟人类求解问题时的思维过程。题时的思维过程。可把产生式系统可把产生式系统作为人工智能系统的基本结构单元作为人工智能系统的基本结构单元或基本模式看待或基本模式看待，就像积木中的积木块一样，因而，就像积木中的积木块一样，因而研究产生式系统的基本问题就具有一般意义。研究产生式系统的基本问题就具有一般意义。2022-4-22人工智能4产生式规则的界定及内容产生式规则的界定及内容产生式规则是产生式系统的主体，是产生式系统知识产生式规则是产生式系统的主体，是产生式系统知识表示的核心。故直接将产生式称为表示的核心。故直接将产生式称为产生式规则

4、产生式规则。一般产生式的结构可表示为自然语言形式，一般产生式的结构可表示为自然语言形式，“原因原因-结结果果”，“条件条件-结论结论”，“前提前提-操作操作”，“事实事实-进展进展”，“情况情况-行为行为”等结构都可归结为产生式的知识表等结构都可归结为产生式的知识表达形式。达形式。2022-4-22人工智能5可归结为产生式的表达形式可归结为产生式的表达形式例：例：（1）天下雨，地上湿。（）天下雨，地上湿。（“原因原因-结果结果”）（2）如果把冰加热到零摄氏度以上，冰会融化为水。（）如果把冰加热到零摄氏度以上，冰会融化为水。（“条件条件-结论结论”）（3）夜来风雨声，花落知多少。（）夜来风雨声，

5、花落知多少。（“事实事实-进展进展”）（4）若能找到一根合适的杠杆，就能撬超那座山。（）若能找到一根合适的杠杆，就能撬超那座山。（“前提前提-操作操作”）（5）刚才开机了，意味着发出了捕获目标图像的信号。（）刚才开机了，意味着发出了捕获目标图像的信号。（“情况情况-行为行为”）2022-4-22人工智能62022-4-22人工智能76.1.16.1.1产生式规则产生式规则（2）产生式的一般形式为：产生式的一般形式为：A A B B（或（或 IF IF A A ThenThen B B）A A是产生式的前提（前件），用于指出该产生式是是产生式的前提（前件），用于指出该产生式是否可用的条件否可用的

6、条件B B是一组结论或操作（后件），用于指出当前提是一组结论或操作（后件），用于指出当前提A A指指示的条件满足时，应得出的结论或应执行的操作。示的条件满足时，应得出的结论或应执行的操作。一个产生式规则就是一条知识，用产生式不仅可以进一个产生式规则就是一条知识，用产生式不仅可以进行推理，也可以实现操作。行推理，也可以实现操作。2022-4-22人工智能86.1.16.1.1产生式规则产生式规则（例）（例）例例三个聪明人问题。古代有个国王想知道他的三三个聪明人问题。古代有个国王想知道他的三个大臣中谁最聪明，就在他们每个人前额上都个大臣中谁最聪明，就在他们每个人前额上都画了一个点，他们都能看到别人

7、点的颜色，但画了一个点，他们都能看到别人点的颜色，但看不到自己点的颜色。国王说，你们中间至少看不到自己点的颜色。国王说，你们中间至少有一个人的点是白色的。于是重复地问他们：有一个人的点是白色的。于是重复地问他们：“谁知道自己点的颜色？谁知道自己点的颜色？”三位大臣们头两次三位大臣们头两次都回答说不知道。都回答说不知道。 题目要求证明下一次他们全都会说题目要求证明下一次他们全都会说“知道知道”，并且所有的点都是白色。并且所有的点都是白色。2022-4-22人工智能96.1.16.1.1产生式规则产生式规则（例）（例）分析分析： 这类问题的特点是有这类问题的特点是有有限个受试者有限个受试者，每个，

8、每个人对人对问题问题都都只有部分了解，无法直接求解只有部分了解，无法直接求解。但。但在推理过程中每个人又可以从别人那里获得新在推理过程中每个人又可以从别人那里获得新的知识，重新进行推理。可以用产生式来表达的知识，重新进行推理。可以用产生式来表达推理过程中所用到的各种知识。推理过程中所用到的各种知识。2022-4-22人工智能106.1.16.1.1产生式规则产生式规则（例）（例）状态集合表示：状态集合表示： 用用x1,x2,x3表示三个人点的颜色，表示三个人点的颜色，1表示白色，表示白色，0表示非白色。表示非白色。 X(x1,x2,x3)表示颜色分布状态。表示颜色分布状态。 全部可能的状态集合

9、全部可能的状态集合(可能界可能界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 。2022-4-22人工智能116.1.16.1.1产生式规则产生式规则（例）（例）排除过程：排除过程：第一次，大臣只知道至少有一个人是白点，排除第一次，大臣只知道至少有一个人是白点，排除X0=(0,0,0)状态。状态。这时如果有人看到两个非白点，根这时如果有人看到两个非白点，根据排除的状态可推知自己是白点。据排除的状态

10、可推知自己是白点。第二次大臣根据没有一个人知道自己点颜色的事实第二次大臣根据没有一个人知道自己点颜色的事实推知至少两人为白点。排除推知至少两人为白点。排除(0,0,1)(0,1,0)(1,0,0)状态。状态。这时如果有人看到一个非白点，根据排除后得到的这时如果有人看到一个非白点，根据排除后得到的状态可推知自己的点是白的。状态可推知自己的点是白的。第三次，大臣们根据仍无人知道自己点颜色的新事第三次，大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现，即实推知没有一个非白点出现，即X0=(1,1,1)。于是三。于是三人都知道自己点的颜色是白的。人都知道自己点的颜色是白的。2022-4-2

11、2人工智能126.1.16.1.1产生式规则产生式规则（例）（例）引入中介状态并定义下述符号：引入中介状态并定义下述符号： Si i大臣看到的大臣看到的非白点数非白点数； Wi i大臣猜出自己点的颜色否。如果他宣布大臣猜出自己点的颜色否。如果他宣布已已知道自己点的颜色，为知道自己点的颜色，为1，否则为，否则为0； nX0中中白点的个数白点的个数。 2022-4-22人工智能136.1.16.1.1产生式规则产生式规则（例）（例）(1) (n=1) X(n=1) X0 0 (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) (0,0,1

12、),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)；(2) (n=1) (2) (n=1) (S(Si i=2) =2) =(W=(Wi i=1),(i=1,2,3,=1),(i=1,2,3,下同下同) )；(3)( (3)( i ) i ) (W(Wi i=1) =1) (n=1) = (n=1) (n=1) = (n=1) ；(4) (n=1) = (4) (n=1) = ( i ) i ) (W(Wi i=1) =1) ；(5) (5) ( i ) i ) (W(Wi i=0) =0) (n=1) = (n=2) ; (n=1) = (n=

13、2) ;(6) (n=2) X(6) (n=2) X0 0 (0,1,1),(1,0,1),(1,1,0),(1,1,1) (0,1,1),(1,0,1),(1,1,0),(1,1,1)；(7) (n=2) (7) (n=2) (S(Si i=1) =1) =(W=(Wi i=1);=1);(8) ( (8) ( i ) i ) (W(Wi i=1) =1) (n=2) = (n=2) ;(n=2) = (n=2) ;(9) (n=2) = (9) (n=2) = ( i ) i ) (W(Wi i=1);=1);(10) (10) ( i ) i ) (W(Wi i=0) =0) (n=2)

14、 = (n=3); (n=2) = (n=3);(11) (n=3) X(11) (n=3) X0 0 (1,1,1) (1,1,1)；(12) (n=3) = (12) (n=3) = ( i ) i ) (W(Wi i=1).=1).2022-4-22人工智能146.1.16.1.1产生式规则产生式规则（例）（例）上述结果可以推广到更一般的情况：设有上述结果可以推广到更一般的情况：设有m个大个大臣，国王说至少有臣，国王说至少有l l个人的点是白色的，则有下个人的点是白色的，则有下述产生式：述产生式： (1) (n=l) X0 x|x中的白点数中的白点数=l； (2) (n=l) (Si=2

15、) =(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)。 2022-4-22人工智能156.1.26.1.2基于产生式规则的推理模式基于产生式规则的推理模式 A B B A B 把有前提的操作和逻辑推理统称为推理，把有前提的操作和逻辑推理统称为推理，产生式系统中的推理是更广义的推理。产生式系统中的推理是更广义的推理。2022-4-22人工智能16

16、6.26.2产生式系统产生式系统6.2.16.2.1系统结构系统结构6.2.26.2.2运行过程运行过程6.2.36.2.3控制策略常用算法控制策略常用算法6.2.46.2.4程序实现程序实现* *6.2.56.2.5产生式系统与问题求解产生式系统与问题求解2022-4-22人工智能176.2.16.2.1系统结构（系统结构（1 1）产生式系统结构产生式系统结构产生式规则库推理机全局数据库2022-4-22人工智能186.2.16.2.1系统结构（系统结构（2 2）组成组成产生式规则库产生式规则库作用在全局数据库上的一些作用在全局数据库上的一些规则规则的集合的集合。每条规则都有一定的条件，若全

17、局数据库。每条规则都有一定的条件，若全局数据库中内容满足这些条件可调用这条规则。一般可形成中内容满足这些条件可调用这条规则。一般可形成一个称为推理网络的结构图。对应过程性知识。一个称为推理网络的结构图。对应过程性知识。推理机推理机负责产生式规则的负责产生式规则的前提条件测试或匹配前提条件测试或匹配，规则的调度和选取，规则体的解释和执行。即推理规则的调度和选取，规则体的解释和执行。即推理机实施推理，并对推理进行控制，它也是规则的解机实施推理，并对推理进行控制，它也是规则的解释程序。对应控制性知识。释程序。对应控制性知识。全局数据库全局数据库人工智能系统的数据结构中心。是人工智能系统的数据结构中心

18、。是一个动态数据结构，用来存放初始一个动态数据结构，用来存放初始事实数据、中间事实数据、中间结果和最后结果结果和最后结果。对应叙述性知识。对应叙述性知识。2022-4-22人工智能196.2.16.2.1系统结构（系统结构（3 3）例例 旅行推销员问题。求从旅行推销员问题。求从A城出发，经过其他城市一次城出发，经过其他城市一次且仅一次，最后回到且仅一次，最后回到A城的最小费用路线。城市之间的城的最小费用路线。城市之间的交通费用标在相应的联线上。建立产生式系统。交通费用标在相应的联线上。建立产生式系统。BCADE713109656710102022-4-22人工智能206.2.16.2.1系统结

19、构（系统结构（4 4）（1）全局数据库全局数据库（已访问过的城镇名称序列）。（已访问过的城镇名称序列）。约约束条件是除城镇束条件是除城镇A之外其他名称不得在序列中重复出现；之外其他名称不得在序列中重复出现；只有所有的名称都在序列中出现后，城镇只有所有的名称都在序列中出现后，城镇A才能重复出才能重复出现。现。（2）规则集规则集如下表所示如下表所示。（3）推理推理： （A） （AB） （ABE） （4）终止条件终止条件序列始于序列始于A，终止于，终止于A，其中包含其，其中包含其他所有城镇一次，且费用最少。他所有城镇一次，且费用最少。（5）各种各种搜索策略搜索策略选择规则，如广度优先搜索，最好优选择

20、规则，如广度优先搜索，最好优先搜索等。先搜索等。 R2R52022-4-22人工智能216.2.16.2.1系统结构（系统结构（5 5）规则集规则集 规则规则动作动作条件条件R1下一步到下一步到A系列中包含所有城镇时可用系列中包含所有城镇时可用R2下一步到下一步到B每条规则只能使用一次，即每条规则只能使用一次，即序列中已有某城镇时，不能序列中已有某城镇时，不能再使用相应规则再使用相应规则R3下一步到下一步到CR4下一步到下一步到DR5下一步到下一步到E2022-4-22人工智能226.2.16.2.1系统结构（系统结构（6 6）与一般分级组织的计算机软件相比具有特点：与一般分级组织的计算机软件

21、相比具有特点：全局数据库的内容可以为所有规则所访问，没有任全局数据库的内容可以为所有规则所访问，没有任何部分是专为某一规则建立的，这种特性便于模仿何部分是专为某一规则建立的，这种特性便于模仿智能行为中的智能行为中的强数据驱动强数据驱动。规则本身规则本身不调用其他规则不调用其他规则。规则之间的联系必须通。规则之间的联系必须通过全局数据库联系。过全局数据库联系。全局数据库、规则和推理机之间全局数据库、规则和推理机之间相对独立相对独立，这种积，这种积木式结构便于整个系统木式结构便于整个系统增加和修改知识增加和修改知识。2022-4-22人工智能236.2.26.2.2产生式系统的产生式系统的运行过程

22、（运行过程（1）推理机一次运行过程推理机一次运行过程从规则库中取出一条规则，将其前提同从规则库中取出一条规则，将其前提同当前动态数据库中的事实进行模式匹配当前动态数据库中的事实进行模式匹配匹配成功否？匹配成功否？把该规则的结论放入当前动态数据库；把该规则的结论放入当前动态数据库；或执行规则所规定的动作或执行规则所规定的动作YN2022-4-22人工智能246.2.26.2.2产生式系统的产生式系统的运行过程运行过程（2 2）产生式系统运行过程产生式系统运行过程实际的产生式系统，目标条件往往要实际的产生式系统，目标条件往往要经过多步推理经过多步推理才能满足或者证明问题无解。才能满足或者证明问题无

23、解。产生式系统的运行过程就是产生式系统的运行过程就是推理机不断的运用规则推理机不断的运用规则库中的规则库中的规则，作用于动态数据库作用于动态数据库，不断进行推理并，不断进行推理并不断检测目标条件是否被满足的过程。不断检测目标条件是否被满足的过程。产生式系统运行过程是从初始事实出发，寻求到达产生式系统运行过程是从初始事实出发，寻求到达目标条件的通路的过程。所以也是一个目标条件的通路的过程。所以也是一个搜索搜索的过程。的过程。例例1 一个简单的例子一个简单的例子问题：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F2022-4-22人工智能25例例1 一个简单的例子（一个简单的例子（1

24、）一、综合数据库x，其中x为字符二、规则集1，IFABTHENC2，IFACTHEND3，IFBCTHENG4，IFBETHENF5，IFDTHENE2022-4-22人工智能26三、控制策略顺序排队四、初始条件A，B五、结束条件Fx例例1 一个简单的例子（一个简单的例子（2）2022-4-22人工智能27综合数据库可触发规则 被触发规则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，F求解过程28问题：问题：N个传教士，个传教士，N个野人，一条船，可同时乘坐个野人，一条船

25、，可同时乘坐 k 个人，要求在任何时刻，在河的两岸及船上，传教个人，要求在任何时刻，在河的两岸及船上，传教士人数不能少于野人的人数。士人数不能少于野人的人数。问：问：如何过河。（给出综合数据库、初始状态和如何过河。（给出综合数据库、初始状态和目标状态、规则集合的形式化描述）目标状态、规则集合的形式化描述）以以N=3，k=2为例求解。为例求解。例例2：传教士与野人问题（：传教士与野人问题（M-C问题）问题）29例例2：M-C问题（续问题（续1） L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 1nL 左岸 R 右岸 B 1（有船）、0（无船）30例例2：M-C

26、问题（续问题（续2）1，综合数据库，综合数据库 （m, c, b)，其中：其中：0m, c3, b 0, 12，初始状态，初始状态 （3，3，1） ( 简化，只描述左岸的情况即可简化，只描述左岸的情况即可 )3，目标状态（结束状态），目标状态（结束状态） （0，0，0）31例例2：M-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

27、 (m, c-2, 0)32IF (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)例例2：M-C问题（续问题（续4）例例2：N=5，k=3为例为例2022-4-22人工智能33例例3：猴子摘香蕉问题：猴子摘香蕉问题一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到处走动，推移箱

28、子，攀登箱子等）。设房间里还有一只可被猴子移动的箱子处走动，推移箱子，攀登箱子等）。设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为c，箱子位置为，箱子位置为b，香蕉位置为，香蕉位置为a），如何行动可摘取到香蕉。），如何行动可摘取到香蕉。2022-4-22人工智能34nanbnc例例3：猴子摘香蕉问题：猴子摘香蕉问题2022-4-22人工智能351，综合数据库，综合数据库定义定义5元组（元组（M, B, Box, On, H）M：猴子的位置：猴子的位置B：香蕉的位置：香蕉的位置Bo

29、x：箱子的位置：箱子的位置On=0：猴子在地板上：猴子在地板上On=1：猴子在箱子上：猴子在箱子上H=0：猴子没有抓到香蕉：猴子没有抓到香蕉H=1：猴子抓到了香蕉：猴子抓到了香蕉例例4：量水问题：量水问题对量水问题给出产生式系统描述，并画出状态对量水问题给出产生式系统描述，并画出状态空间图。空间图。 有两个无刻度标志的水壶，分别可有两个无刻度标志的水壶，分别可装装5升和升和2升的水。设另有一水缸，可用来向水升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。已知互倾灌。已知5升壶为满壶，升壶为满壶，2升壶为空壶，问升壶为空壶，

30、问如何通过倒水或灌水操作，使能在如何通过倒水或灌水操作，使能在2升的壶中升的壶中量出一升的水来。量出一升的水来。2022-4-22人工智能36例例4：量水问题：量水问题2022-4-22人工智能372022-4-22人工智能386.2.36.2.3控制策略与常用算法控制策略与常用算法（1 1）推理方式推理方式正向推理正向推理 从初始事实数据出发，正向使用规则从初始事实数据出发，正向使用规则进行推理，朝目标方向前进。又称为前向推理、正进行推理，朝目标方向前进。又称为前向推理、正向链、数据驱动的推理。向链、数据驱动的推理。反向推理反向推理从目标出发，反向使用规则进行推理，从目标出发，反向使用规则进

31、行推理，朝初始事实或数据方向前进。又称反向推理、反向朝初始事实或数据方向前进。又称反向推理、反向链、目标驱动的推理。链、目标驱动的推理。2022-4-22人工智能396.2.36.2.3控制策略与常用算法控制策略与常用算法（2 2）正向推理算法一正向推理算法一步步1 将初始事实将初始事实/数据置入动态数据库；数据置入动态数据库；步步2 用动态数据库中的事实匹配目标条件，若目标条件用动态数据库中的事实匹配目标条件，若目标条件满足，推理成功，结束。满足，推理成功，结束。步步3 用规则库中各规则的前提匹配动态数据库中的事实，用规则库中各规则的前提匹配动态数据库中的事实，将匹配成功的规则组成待用规则集

32、。将匹配成功的规则组成待用规则集。步步4 若待用规则集为空，则运行失败，退出。若待用规则集为空，则运行失败，退出。步步5 将待用规则集中各规则的结论加入动态数据库，或将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步者执行其动作，转步2。2022-4-22人工智能406.2.36.2.3控制策略与常用算法（控制策略与常用算法（3 3）若把若把动态数据库动态数据库的的每一个状态每一个状态作为一个作为一个节点节点的话，则的话，则上述推理过程就是一个从初始状态到目标状态的上述推理过程就是一个从初始状态到目标状态的状态状态图搜索图搜索过程。过程。如果把动态数据库中的如果把动态数据库中的每一

33、个事实每一个事实/数据数据作为一个作为一个节点节点的话，则上述推理过程就是一个自底向上的的话，则上述推理过程就是一个自底向上的与或树搜与或树搜索索过程。过程。2022-4-22人工智能416.2.36.2.3控制策略与常用算法控制策略与常用算法（4 4）反向推理算法反向推理算法步步1 将初始事实将初始事实/数据置入动态数据库，数据置入动态数据库，将目标条件置入将目标条件置入目标链；目标链；步步2 若目标链为空，则推理成功，结束。若目标链为空，则推理成功，结束。步步3 取出目标链中第一个目标，用动态数据库中的事实取出目标链中第一个目标，用动态数据库中的事实同其匹配，若匹配成功，转步同其匹配，若匹

34、配成功，转步2。步步4 用规则集中的各规则的结论同该目标匹配，若匹配用规则集中的各规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标加入目标链，转步为新的目标，并取代原来的父目标加入目标链，转步3。步步5 若该目标是初始目标，则推理失败，退出。若该目标是初始目标，则推理失败，退出。步步6 将该目标的父目标移回目标链，取代该目标及其兄将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步弟目标，转步3。2022-4-22人工智能426.2.36.2.3控制策略与常用算法控制策略与常用算法（5

35、5）在产生式系统中，从前提到结论的产生式规则在产生式系统中，从前提到结论的产生式规则通常也是一棵与或树。通常也是一棵与或树。合取，与节点：一个产生式的前提包含了几个事实，合取，与节点：一个产生式的前提包含了几个事实，那么它的结论对应这些事实的合取。那么它的结论对应这些事实的合取。析取，或节点：一个结论可以由多个产生式得到，析取，或节点：一个结论可以由多个产生式得到，则这个结论对应这些产生式的析取。则这个结论对应这些产生式的析取。每个产生式系统都隐含着许多这样的与或树。每个产生式系统都隐含着许多这样的与或树。2022-4-22人工智能436.2.36.2.3控制策略与常用算法控制策略与常用算法（

36、6 6）F1P1F3F4F5F6BCDAP2P3P4P5F2事实中介事实B、C、D产生式规则P1、P2、P3、P4、P5结论2022-4-22人工智能446.2.36.2.3控制策略与常用算法控制策略与常用算法（7 7）例例6.1：动物分类问题的产生式系统描述及求解。：动物分类问题的产生式系统描述及求解。 规则规则：r1 r1： IF IF 该动物有毛发该动物有毛发 THEN THEN 该动物是哺乳动物该动物是哺乳动物r2r2： IF IF 该动物有奶该动物有奶 THEN THEN 该动物是哺乳动物该动物是哺乳动物r3r3： IF IF 该动物有羽毛该动物有羽毛 THEN THEN 该动物是鸟

37、该动物是鸟r4r4： IF IF 该动物会飞该动物会飞 AND AND 会下蛋会下蛋 THEN THEN 该动物是鸟该动物是鸟r5r5： IF IF 该动物吃肉该动物吃肉 THEN THEN 该动物是食肉动物该动物是食肉动物r6r6： IF IF 该动物有犬齿该动物有犬齿 AND AND 有爪有爪 AND AND 眼盯前方眼盯前方 THEN THEN 该动物是食肉动物动物该动物是食肉动物动物2022-4-22人工智能456.2.36.2.3控制策略与常用算法控制策略与常用算法（8 8）r7r7： IF IF 该动物是哺乳动物该动物是哺乳动物 AND AND 有蹄有蹄 THEN THEN 该动物

38、是有蹄类动物该动物是有蹄类动物r8r8： IF IF 该动物是哺乳动物该动物是哺乳动物 AND AND 是嚼反刍动物是嚼反刍动物 THEN THEN 该动物是有蹄动物该动物是有蹄动物r9r9： IF IF 该动物是哺乳动物该动物是哺乳动物 AND AND 是食肉动物是食肉动物 AND AND 是黄褐色是黄褐色 AND AND 身上有暗斑点身上有暗斑点 THEN THEN 该动物是该动物是金钱豹金钱豹 r10r10： IF IF 该动物是哺乳动物该动物是哺乳动物 AND AND 是食肉动物是食肉动物 AND AND 是黄褐色是黄褐色 AND AND 身上有黑色条纹身上有黑色条纹 THEN THE

39、N 该动物是该动物是虎虎2022-4-22人工智能466.2.36.2.3控制策略与常用算法控制策略与常用算法（9 9）r11r11： IF IF 该动物是有蹄类动物该动物是有蹄类动物 AND AND 有长脖子有长脖子 AND AND 有长腿有长腿 AND AND 身上有暗斑点身上有暗斑点 THEN THEN 该动物是该动物是长颈鹿长颈鹿 r12r12： IF IF 该动物有蹄类动物该动物有蹄类动物 AND AND 身上有黑色条纹身上有黑色条纹 THEN THEN 该动物是该动物是斑马斑马r13r13： IF IF 该动物是鸟该动物是鸟 AND AND 有长脖子有长脖子 AND AND 有长腿

40、有长腿 AND AND 不会飞不会飞 AND AND 有黑白二色有黑白二色 THEN THEN 该动物是该动物是鸵鸟鸵鸟2022-4-22人工智能476.2.36.2.3控制策略与常用算法控制策略与常用算法（1010）r14r14： IF IF 该动物是鸟该动物是鸟 AND AND 会游泳会游泳 AND AND 不会飞不会飞 AND AND 有黑白二色有黑白二色 THEN THEN 该动物是该动物是企鹅企鹅r15r15：IF IF 该动物是鸟该动物是鸟 AND AND 善飞善飞 AND AND 不怕风浪不怕风浪 THEN THEN 该动物是该动物是海燕海燕老虎老虎黄褐色黄褐色有黑色条纹有黑色条

41、纹食肉动物食肉动物哺乳动物哺乳动物有毛发有毛发有奶有奶吃肉吃肉有爪有爪有犬齿有犬齿目 盯 前目 盯 前方方金钱豹金钱豹有 黑 色 斑有 黑 色 斑点点长颈鹿长颈鹿有蹄动物有蹄动物有蹄有蹄长腿长腿长脖子长脖子有 暗 斑有 暗 斑点点图图6-4 6-4 动物分类产生式规则集所形成的部分推理网络动物分类产生式规则集所形成的部分推理网络2022-4-22人工智能496.2.36.2.3控制策略与常用算法控制策略与常用算法（1212）初始事实：初始事实： f1 f1：某动物有毛发。：某动物有毛发。 f2f2：吃肉。：吃肉。 f3f3：黄褐色。：黄褐色。 f4f4：有黑色条纹：有黑色条纹目标条件为：该动物

42、为什么？目标条件为：该动物为什么？2022-4-22人工智能506.2.36.2.3控制策略与常用算法控制策略与常用算法（1313）哺乳类食肉动物有毛发食肉黄褐色有黑色条纹老虎正向推理推理树r2r6r102022-4-22人工智能516.2.36.2.3控制策略与常用算法控制策略与常用算法（1414）哺乳类食肉动物有毛发有奶黄褐色有黑色条纹老虎反向推理推理树目盯前方有毛发有爪吃肉r10r5r1r2r6例例6.2 使用反向推理算法使用反向推理算法2022-4-22人工智能526.2.36.2.3控制策略与常用算法（控制策略与常用算法（1515）3 冲突消解策略冲突消解策略给定一组事实之后可用匹配

43、技术寻找可用产生式，其给定一组事实之后可用匹配技术寻找可用产生式，其基本思想是将已知事实代入产生式的前件，若前件为基本思想是将已知事实代入产生式的前件，若前件为真，则该产生式是可用的。真，则该产生式是可用的。提高匹配效率的方法提高匹配效率的方法索引匹配。为状态建立可用产生式索引表，减少可用产生式索引匹配。为状态建立可用产生式索引表，减少可用产生式搜索范围。搜索范围。分层匹配。将产生式分成若干层或组，按一定特征进行分层分层匹配。将产生式分成若干层或组，按一定特征进行分层搜索。搜索。过滤匹配。边匹配边过滤匹配。边匹配边 按某些附加特征或参数对可用产生式进按某些附加特征或参数对可用产生式进行精选。行

44、精选。2022-4-22人工智能536.2.36.2.3控制策略与常用算法控制策略与常用算法（2 2）正向推理算法二正向推理算法二步步1 将初始事实将初始事实/数据置入动态数据库；数据置入动态数据库；步步2 用动态数据库中的事实匹配目标条件，若目标条件用动态数据库中的事实匹配目标条件，若目标条件满足，推理成功，结束。满足，推理成功，结束。步步3 用规则库中各规则的前提匹配动态数据库中的事实，用规则库中各规则的前提匹配动态数据库中的事实，将匹配成功的规则组成待用规则集。将匹配成功的规则组成待用规则集。步步4 若待用规则集为空，则运行失败，退出。若待用规则集为空，则运行失败，退出。步步5 用某种策略，从待用规则集中选取一条规则，用某种策略，从待用规则集中选取一条规则，将其将其结论加入动态数据库，或者执行其动作，撤消待用规结论加入动态数据库，或者执行其动作，撤消待用规则集，转步则集，转步2。