人工智能之产生式系统

知识表示知识是一切智能行为的基础，也是软件智能化的重要研究对象。要使软件具有智能，就必须使它具有知识，而要使软件具有知识，首先必须解决知识的表示问题。所谓知识表示实际上就是对知识的一种描述，即用一些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。一般来说，同一知识可以有多种不同的表示形式，而不同表示形式所产生的效果又可能不一样。9/25/20231常用的知识表示方法非结构化方法逻辑表示法QA3,STRIPS,DART,MOMO产生式系统DENDRAL，MYCIN结构化方法框架语义网络过程式知识表示法9/25/20232第二章产生式系统

2.1产生式系统概述

一、产生式系统的定义产生式系统是人工智能系统中常用的一种程序结构，是一种知识表示系统。

通常由以下三部分组成：综合数据库产生式规则集控制系统9/25/20233综合数据库：存放问题的状态描述的数据结构。Note:综合数据库不是常规意义的数据库，是一种数据结构。一般数据库所存数据的结构很简单，通常只有数值与字符串；综合数据库的数据可以很复杂，其中状态描述可以为常规的各种数据结构，如表、数组、字符串、集合、矩阵、树、图等等。综合数据库是动态变化的。一、产生式系统的定义9/25/20234产生式规则形式：

IF

前提条件

THEN

操作

当规则的前提条件被某一状态描述满足时，就对该状态施行规则所指出的操作。一、产生式系统的定义9/25/20235控制系统：

（1）选择规则：对同一个状态的多个可用规则排序。（2）检验状态描述是否满足终止条件。如果满足终止条件，则终止产生式系统的运行，并用使用过的规则序列构造出问题的解。一、产生式系统的定义9/25/20236二、产生式系统的例

八数码难题由8个标有1－8的棋子和一个3×3的棋盘组成。把8个棋子放在棋盘里，形成一个初始状态，然后移动棋子，想办法达到规定的目标状态。在移动棋子时，只能把棋子移进相邻的空格中。图2.1八数码难题的初始状态与目标状态28316475123847659/25/20237八数码难题的产生式系统表示综合数据库：以状态为节点的有向图。状态描述：3×3矩阵产生式规则：IF<空格不在最左边>Then<左移空格>；IF<空格不在最上边>Then<上移空格>；IF<空格不在最右边>Then<右移空格>；IF<空格不在最下边>Then<下移空格>。控制系统：

选择规则:按左、上、右、下的顺序移动空格。终止条件：匹配成功。9/25/20238三、产生式系统的基本过程ProcedurePRODUCTIONDATA←初始状态描述untilDATA满足终止条件，do：begin在规则集合中，选出一条可用于DATA的规则RDATA←把R应用于DATA所得的结果End9/25/20239

步骤4是不确定的，只要求选出一条可用的规则R，至于这条规则如何选取，却没有具体说明。

选取规则所依据的原则称为控制策略。多数人工智能系统控制策略的信息并不足以在第4步选出最合用的规则，因此，控制策略便成了一个搜索过程。

高效的系统需要被求解问题足够的知识，以便在步骤4选出一条最合用的规则。第三章，第四章三、产生式系统的基本过程9/25/202310产生式系统的特点一、模块性强。综合数据库、规则集和控制系统相对独立，程序的修改更加容易。二、各产生式规则相互独立，不能互相调用，增加一些或删去一些产生式规则都十分方便。三、产生式规则的形式与人们推理所用的逻辑形式十分接近，人们具有的知识转换成产生式规则很容易，产生式规则也容易被人们读懂。DENDRAL和MYCIN都采用了产生式系统的结构。9/25/2023112.2控制策略

产生式系统的控制策略分为两类：不可撤回的控制策略试探性控制策略：回溯方式和图搜索方式9/25/202312一、不可撤回的控制策略（瞎子爬山法）基本思想采用不可撤回控制方式的解题过程类似于盲人爬山过程，是利用关于每一个状态的局部知识构造全局性解的过程。在盲人爬山过程中，无论爬到哪一点，他总沿着坡度最陡的方向向上爬，这是局部性的知识，尽管他事先对爬山路线并不了解，但只要按照这个原则向上爬，就一定能爬到某一山顶，于是确定了一条从山脚到山顶的爬山路线，也可以说构造出一个具有某种意义下全局性的解。9/25/202313一、不可撤回的控制策略爬山函数：定义在整个综合数据库上的实数值函数，目标状态有最大的函数值。目标：爬到山顶。控制策略：应用爬山函数选一规则，使得所选下一状态的爬山函数值不减少且最大（有两个相同的最大值时任选一个；若无这样的规则，则终止爬山过程）。9/25/202314设爬山函数CF(S)：不在目标位的数码个数的负值。

初始状态S0目标状态Sg

CF(S0)＝-4CF(Sg)＝0状态描述S：3阶方阵4条产生式规则使用顺序：空格左、上、右、下移。2831647512384765例：八数码难题，不可撤回式控制9/25/202315控制策略：处于任一状态S，系统根据爬山函数选择一条规则使得这条规则作用于S时，获得的下一状态爬山函数不减少且最大（亦即距离目标状态最少）。例：八数码难题，不可撤回式控制9/25/202316

283164752831476523184765231847651238476512384765例：八数码难题不可撤回式控制-4-3-3-1-209/25/202317不可撤回控制策略的优点1.只记录当前一个节点，空间复杂性很低。2.若能找到解，则速度很快。9/25/202318不可撤回控制策略的局限性多数情况下找不到解。原因：(a)爬山函数有多个局部极大值例如：目标0初始-2(b)爬山函数具有“平顶值”解决方法：设计更好的爬山函数；选多余规则12374865125748639/25/202319二、回溯控制策略回溯方式是一种试探性的控制策略。（类似深度优先）基本思想控制系统先选用一条规则，如果发现这条规则的选用不能导致产生解，则系统“忘掉”选用规则所涉及的步骤和产生的状态，然后选用另外一条规则，重新进行试探。

9/25/202320回溯方法特点1.只存储初始节点到当前节点的路径，占用空间较小。2.总的时间复杂性无法定论:最好情况复杂性很低：当控制系统掌握较多的有关解的知识时，则回溯次数大为减少，效率高。最坏情况复杂性很高：当控制系统一点也没掌握有关解的知识时，则规则选取是任意的，回溯次数高，效率低。为了避免进入无限的境地，设置回溯深度限制强行回溯，问题：太深：效率低；太浅：可能找不到解。3.当深度限制可变时，通常能找到解，是实际用得多、应用最广的一种搜索策略。

9/25/202321四条规则使用顺序：左、上、右、下（可加入启发式信息，如使用爬山函数安排规则的顺序）

深度：6

控制策略：回溯式

回溯条件：

⑴产生了一个上溯到初始状态的路径上出现过的状态时（产生了祖先节点）。

⑵无可用的规则。

⑶达深度未得解。2831647512384765八数码难题的初始状态与目标状态例：八数码难题回溯式9/25/2023222831647583264175832641752831647583264175834261758326417586324175283641758326417586324175

8326417583264175八数码问题回溯控制

83264175

（1）（5）（6）（5）（2）（6）（7）（6）

（3）（7）（7）

（4）（5）

（6）

9/25/202323三、图搜索控制策略基本思想：从初始状态开始，使用全部可用规则序列。对所有的下一步状态每一个再用全部可用的规则，直到目标状态为止。（类似广度优先搜索策略）搜索树：记录规则的应用和所产生的状态的树结构。树根：初始状态有向弧：规则的使用除根以外的其它各节点：规则应用的结果图搜索控制方式不断地扩展搜索树，直到它包括了满足终止条件的节点为止。

9/25/202324图搜索控制策略的特点1.不再选择规则，而是使用所有可用的规则，下一步选择节点来扩展。2.存储所有产生的节点，占用空间大。3.有解一定能找到（相当于穷举）。4.平均时间复杂性高，系统效率低。9/25/202325

例：八数码难题图搜索式2831647512384765八数码难题的初始状态与目标状态书中图：按照深度小的排在前面、优先选择左节点。9/25/202326四、产生式系统的工作方式1.正向产生式系统（数据驱动控制）：综合数据库：用状态描述产生式规则：F规则--状态产生新状态

从初始状态出发，不断地应用F规则，直到产生目标状态为止。适用条件：初始节点数≤目标节点数9/25/2023272.反（逆）向产生式系统（目标驱动控制）：综合数据库：用目标描述产生式规则：B规则目标产生子目标从目标状态出发，利用反向的产生式规则（B规则）不断地产生子目标，直到产生出与初始状态相同的子目标为止。适用条件：初始节点数≥目标节点数9/25/2023283.双向产生式系统：正向产生式系统和反向产生式系统结合.综合数据库：既有初始状态描述，又有目标状态描述。产生式规则集：既有F规则，又有B规则。

正向产生式规则用在初始方向的状态描述上，反向产生式规则用在目标描述上。控制系统:判断选F规则还是B规则；判断已经产生的状态和目标是否能以某种方式匹配，从而满足结束条件。结束条件：中间汇合时的状态。适用条件：初始节点数与目标节点数都很多。特点：效率高；复杂。9/25/2023292.3特殊的产生式系统一、可交换产生式系统在某些产生式系统中。规则应用的次序对产生的状态无影响，即从初始状态到目标状态不依赖规则次序，因此可应用不可撤回式控制策略，从而提高了产生式系统的效率，这类产生式系统就是可交换的产生式系统。例：基于归结方法的产生式系统9/25/202330

一个产生式系统称为可交换的，如果对任意状态描述D具有如下性质：(a)设RD是可应用于D的规则集，任取r

∈RD，r作用于D得D’，设为D’=r

(D)，则r对D’可用(即：设D’的可用规则集为RD’，则r∈RD’，即RD

RD’)；（每一条对D可应用的规则，对于对D应用一条可应用的规则后所产生的状态描述仍是可应用的）（可应用性）可交换产生式系统定义9/25/202331(b)设D满足目标条件，D的可用规则集为RD，任取r∈RD，用r作用到D产生状态D’，D’满足目标条件。（如果D满足目标条件，则对D应用任何一条可应用的规则所产生的状态描述也满足目标条件）

（可满足性）。9/25/202332（c）设D的可用规则集为RD，任取r1,r2,…,rn

∈RD，依据（a）将r1,r2,…,rn依次作用到D及产生的状态上，得状态Dn；设r1’,r2’,…,rn’是r1,r2,…,rn的任意一个排列，用r1’,r2’,…,rn’依次作用到D及产生的状态上，得状态Dn’，则Dn’=Dn

（对D应用一个由可应用于D的规则所构成的规则序列所产生的状态描述不因序列的次序不同而改变）(无次序性）。

9/25/202333R1R3R1S12S11S0S13S3S2SGS1R3R2R1R2R3R1R2R3R2R1R3R3R2R1R2R3R1可交换的产生式系统例R2R3R2R19/25/202334可交换产生式系统优点：从初始状态到目标状态不依赖规则次序，不必探查等价路径，可以使用不可撤回策略。Note：产生式系统的可交换性并不意味着整个规则序列的次序可以改变。只是最初作用于给定状态的那些规则使用起来与次序无关。9/25/202335设产生式系统P：综合数据库，一组规则，图搜索策略造另一可交换的产生式系转换P’如下：综合数据库：初始状态：P的整个搜索树目标状态：只剩解路转换

可用如下方法将一产生式系转换为可交换的：9/25/202336转换可用如下方法将一产生式系转换为可交换的：规则Ri：若综合数据库中第i层节点n不是解路P上的点，则从综合数据库中删除节点n。控制策略：不可撤回式将P转换为P’，P’是可交换的产生式系统

综合数据库变复杂；规则数目少，但操作复杂（如何判断n不是解路P上的点）；控制策略简单。9/25/202337二、可分解的产生式系统

可交换产生式系统可以避免搜索多余路径，可以使用不可撤回策略。避免搜索多余路径的另一种方法是可分解的产生式系统。9/25/202338可分解的产生式系统例:字符串重写综合数据库：串节点的有向图状态：字符串（或用表）初始状态：(C,B,Z)产生式规则：R1:IF<(*1,C,*2)>THEN<(*1,D,L,*2)>

（重写规则）R2:IF<(*1,C,*2)>THEN<(*1,B,M,*2)>R3:IF<(*1,B,*2)>THEN<(*1,M,M,*2)>R4:IF<(*1,Z,*2)>THEN<(*1,B,B,M,*2)>控制系统：

选择规则：用图搜索控制策略终止条件：状态描述仅有M组成的符号串。

9/25/202339重写问题的解序列（不完整）R3R3R3R3R3R4R4R3R3R3R2R1R4（C，B，Z）(M,M,M,B,Z)(M,M,M,M,M,Z)(M,M,M,M,M,B,B,M)(M,M,M,M,M,M,M,B,M)(M,M,M,M,M,M,M,M,M,M)(C,B,B,B,M)(B,M,B,B,B,M)(M,M,M,B,B,B,M)(D,L,B,Z)(D,L,M,M,Z)(D,L,M,M,B,B,M)(D,L,M,M,M,M,B,M)(D,L,M,M,M,M,M,M,M)R2R3(B,M,B,Z)9/25/202340Note:按照图搜索控制方式在产生终止状态时可能会探索许多完全等价的路径,导致系统的低效。从失败路径上浪费很多工作。节点的内容之间存在着大量的符号冗余。9/25/202341观察：该产生式系统的初始状态可以分解成C,B和Z，然后把产生式规则分解使得可应用于这些组成部分：R1:(C)→(D,L)R2:(C)→(B,M)R3:(B)→(M,M)R4:(Z)→(B,B,M)应用规则后所得的结果状态又可以进一步分裂，这样不断地分解，不断地应用规则，直到所产生的状态是M字符为止，即终止条件分解为一个M字符作成的状态。9/25/202342重写问题的与/或树(C,B,Z)CBZ(D,L)(B,M)(M,M)(B,B,M)DLBM(M,M)MMMMBMB(M,M)(M,M)MMMM

R1R2R3R4

R3R3R39/25/202343

定义

能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统