人工智能第二章三

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

2.1产生式系统概述

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

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

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

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

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

选择规则:按左、上、右、下的顺序移动空格。终止条件：匹配成功。1/22/20238三、产生式系统的基本过程ProcedurePRODUCTIONDATA←初始状态描述untilDATA满足终止条件，do：begin在规则集合中，选出一条可用于DATA的规则RDATA←把R应用于DATA所得的结果End1/22/20239步骤4是不确确定的，只要要求选出一条条可用的规则则R，至于这条条规则如何选选取，却没有有具体说明。。选取规则所依依据的原则称称为控制策略略。多数人工智能能系统控制策策略的信息并并不足以在第4步选出最最合用的规则则，因此，控控制策略便成成了一个搜索过程。。高效的系统需需要被求解问问题足够的知知识，以便在在步骤4选出一一条最合用的的规则。第三章，第四四章三、产生式系系统的基本过过程1/7/202310产生式式系统统的特特点一、模块块性强。。综合数数据库、、规则集集和控制制系统相相对独立，，程序的的修改更更加容易易。二、各产产生式规规则相互互独立，，不能互互相调用用，增加加一些或删删去一些些产生式式规则都都十分方方便。三、产生生式规则则的形式式与人们们推理所所用的逻逻辑形式式十分接近近，人们们具有的的知识转转换成产产生式规规则很容易，，产生式式规则也也容易被被人们读读懂。DENDRAL和MYCIN都采用用了产生生式系统统的结构构。1/7/2023112.2控控制制策略产生式系系统的控控制策略略分为两两类：不可撤回回的控制制策略试探性控控制策略略：回溯溯方式和和图搜索索方式1/7/202312一、不可可撤回的的控制策策略（瞎瞎子爬山山法）基本思想想采用不可可撤回控控制方式式的解题题过程类类似于盲盲人爬山山过程，，是利用用关于每每一个状状态的局局部知识识构造全全局性解解的过程程。在盲盲人爬山山过程中中，无论论爬到哪哪一点，，他总沿沿着坡度度最陡的的方向向向上爬，，这是局局部性的的知识，，尽管他他事先对对爬山路路线并不不了解，，但只要要按照这这个原则则向上爬爬，就一一定能爬爬到某一一山顶，，于是确确定了一一条从山山脚到山山顶的爬爬山路线线，也可可以说构构造出一一个具有有某种意意义下全全局性的的解。1/7/202313一、不可可撤回的的控制策策略爬山函数数：定义在整整个综合合数据库库上的实实数值函函数，目标状态态有最大大的函数数值。目标标：爬到山顶顶。控制策略略：应用爬山山函数选选一规则则，使得得所选下下一状态态的爬山山函数值值不减少少且最大大（有两两个相同同的最大大值时任任选一个个；若无无这样的的规则，，则终止止爬山过过程）。。1/7/202314设爬山函数CF(S)：：不在目标位的的数码个数的的负值。初始状态S0目标状态SgCF(S0)＝-4CF(Sg)＝0状态描述S：：3阶方阵4条产生式规规则使用顺序序：空格左、上、、右、下移。。2831647512384765例：八数码难题，，不可撤回式式控制1/7/202315控制策略：处于任一状态态S，系统根根据爬山函数数选择一条规规则使得这条条规则作用于于S时，，获得的下一一状态爬山函函数不减少且且最大（亦即即距离目标状状态最少）。。例：八数码难题，，不可撤回式式控制1/7/202316283164752831476523184765231847651238476512384765例：八数码难难题不可可撤回式控制制-4-3-3-1-201/7/202317不可撤回回控制策策略的优优点1.只只记录当当前一个个节点，，空间复复杂性很很低。2.若若能找到到解，则则速度很很快。1/7/202318不可撤回回控制策策略的局局限性多数情况况下找不不到解。。原因：：(a)爬爬山山函数有有多个局局部极大大值例如：目标0初初始-2(b)爬爬山山函数具具有“平平顶值””解决方法法：设计更更好的的爬山山函数数；选选多余余规则则12374865125748631/7/202319二、回回溯控控制策策略回溯方方式是一种种试探探性的的控制制策略略。（（类似似深度度优先先）基本思思想控制系系统先先选用用一条条规则则，如如果发发现这这条规规则的的选用用不能能导致致产生生解，，则系系统““忘掉掉”选选用规规则所所涉及及的步步骤和和产生生的状状态，，然后后选用用另外外一条条规则则，重重新进进行试试探。。1/7/202320回溯方方法特特点1.只只存储储初始始节点点到当当前节节点的的路径径，占占用空空间较较小。。2.总总的的时间间复杂杂性无无法定定论:最好情情况复复杂性性很低低：当当控制制系统统掌握握较多多的有有关解解的知知识时时，则则回溯溯次数数大为为减少少，效效率高高。最坏情情况复复杂性性很高高：当当控制制系统统一点点也没没掌握握有关关解的的知识识时，，则规规则选选取是是任意意的，，回溯溯次数数高，，效率率低。。为了避避免进进入无无限的的境地地，设设置回回溯深深度限限制强强行回回溯，，问题题：太太深：：效率率低；；太浅浅：可可能找找不到到解。。3.当当深深度限限制可可变时时，通通常能能找到到解，，是实实际用用得多多、应应用最最广的的一种种搜索索策略略。1/7/202321四条规则使用用顺序：左、、上、右、下下（可加入启启发式信息，，如使用爬山山函数安排规规则的顺序））

深度：6

控制策略略：回溯式回回溯条件：：⑴产生了一个上上溯到初始状状态的路径上上出现过的状状态时（产生生了祖先节点点）。⑵无可用的规则则。⑶达深度未得解解。2831647512384765八数码难题的的初始状态与与目标状态例：八数码难难题回回溯式1/7/20232228316475832641758326417528316475832641758342617583264175863241752836417583264175863241758326417583264175八数码问题回回溯控制83264175（1）（（5）（（6）（（5）（2）（（6）（（7）（（6）（3）（7）（（7）（4）（5）（6）1/7/202323三、图搜索控控制策略基本思想：从初始状态开开始，使用全全部可用规则则序列。对所所有的下一步步状态每一个个再用全部可可用的规则，，直到目标状状态为止。（（类似广度优优先搜索策略略）搜索树：记录录规则的应用用和所产生的的状态的树结结构。树根：初始状状态有向弧：规则则的使用除根以外的其其它各节点：：规则应用的的结果图搜索控制方方式不断地扩扩展搜索树，，直到它包括括了满足终止止条件的节点点为止。1/7/202324图搜索控制制策略的特特点1.不再选选择规则，，而是使用用所有可用用的规则，，下一步选选择节点来来扩展。2.存储所所有产生的的节点，占占用空间大大。3.有解一一定能找到到（相当于于穷举）。。4.平均时时间复杂性性高，系统统效率低。。1/7/202325例：八数码码难题图图搜索索式2831647512384765八数码难题题的初始状状态与目标标状态书中图：按按照深度小小的排在前前面、优先先选择左节节点。1/7/202326四、产生式系系统的工作方方式1.正向产生式系系统（数据驱驱动控制）：：综合数据库：：用状态描述述产生式规则：：F规则--状态产生新状状态从初始状态出出发，不断地地应用F规则则，直到产生生目标状态为为止。适用条件：初初始节点数≤≤目标节点数数1/7/2023272.反（逆）向产产生式系统（（目标驱动控控制）：综合数据库：：用目标描述述产生式规则：：B规则目目标产生子子目标从目标状态出出发，利用反反向的产生式式规则（B规则）不不断地产生子子目标，直到到产生出与初初始状态相同同的子目标为为止。适用条件：初初始节点数≥≥目标节点数数1/7/2023283.双向产生式系系统：正向产生式系系统和反向产产生式系统结结合.综合数据库：：既有初始状状态描述，又又有目标状态态描述。产生式规则集集：既有F规规则，又有B规则。正向产生式规规则用在初始始方向的状态态描述上，反反向产生式规规则用在目标标描述上。控制系统:判判断选F规则则还是B规则则；判断已经产生生的状态和目目标是否能以以某种方式匹匹配，从而满足结束条件。结束条件：中中间汇合时的的状态。适用条条件：：初始始节点点数与与目标标节点点数都都很多多。特点：：效率高高；复复杂。1/7/2023292.3特特殊的的产生生式系系统一、可可交换换产生生式系系统在某些些产生生式系系统中中。规规则应应用的的次序序对产产生的的状态态无影影响，，即从从初始始状态态到目目标状状态不不依赖赖规则则次序序，因因此可可应用用不可可撤回回式控控制策策略，，从而而提高高了产产生式式系统统的效效率，，这类类产生生式系系统就就是可可交换换的产产生式式系统统。例：基于归归结方方法的的产生生式系系统1/7/202330一个产产生式式系统统称为为可交交换的的，如如果对对任意意状态态描述述D具具有如如下性性质：：(a)设设RD是可应应用于于D的的规则则集，，任取取r∈RD，r作用用于D得D’’，设设为D’=r(D)，则则r对对D’’可可用(即：：设D’的的可用用规则则集为为RD’，则r∈RD’，即RDRD’)；（每每一条条对D可应应用的的规则则，对对于对对D应应用一一条可可应用用的规规则后后所产产生的的状态态描述述仍是是可应应用的的）（（可应应用性性）可交换换产生生式系系统定定义1/7/202331(b)设设D满足足目标条条件，D的可用用规则集集为RD，任取r∈RD，用r作作用到D产生状状态D’’，D’满足足目标条条件。（如果D满足目目标条件件，则对对D应用用任何一一条可应应用的规规则所产产生的状状态描述述也满足足目标条条件）（可满足足性）。。1/7/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的规则所所构成的规规则序列所所产生的状状态描述不不因序列的的次序不同同而改变））(无次序序性）。1/7/202333R1R3R1S12S11S0S13S3S2SGS1R3R2R1R2R3R1R2R3R2R1R3R3R2R1R2R3R1可交换的产产生式系统统例R2R3R2R11/7/202334可交换产生式式系统优点：：从初始状态到到目标状态不不依赖规则次次序，不必探探查等价路径径，可以使用用不可撤回策策略。Note：产生式系统的的可交换性并并不意味着整整个规则序列列的次序可以以改变。只是是最初作用于于给定状态的的那些规则使使用起来与次次序无关。1/7/202335设产生式系统统P：综合数数据库，一组组规则，图搜搜索策略造另一可交换换的产生式系系转换P’如如下：综合数据库：：初始状态：P的整个搜索索树目标状态：只只剩解路转换可用如下方法法将一产生式式系转换为可可交换的：1/7/202336转换可用如下方法法将一产生式式系转换为可可交换的：规则Ri：若综合数据库库中第i层节节点n不是解解路P上的点点，则从综合合数据库中删删除节点n。。控制策略：不可撤回式将P转换为P’，P’’是可交换的的产生式系统统综合数据库变变复杂；规则则数目少，但但操作复杂（（如何判断n不是解路P上的点）；；控制策略简简单。1/7/202337二、可分解的的产生式系统统可交换产生式式系统可以避避免搜索多余余路径，可以使用不可撤撤回策略。避避免搜索多余余路径的另一一种方法是可分解的产生生式系统。1/7/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组成的符符号串。1/7/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)1/7/202340Note:按照图搜索控控制方式在产产生终止状态态时可能会探探索许多完全全等价的路径径,导致系统统的低效。从失败路径上上浪费很多工工作。节点的内容之之间存在着大大量的符号冗冗余。1/7/202341观察：：该产生生式系系统的的初始状状态可以分解成C,B和和Z，，然后把把产生式式规则则分解解使得可可应用用于这这些组组成部部分：：R1:(C)→→(D,L)R2:(C)→→(B,M)R3:(B)→→(M,M)R4:(Z)→→(B,B,M)应用规规则后后所得得的结结果状状态又又可以以进一一步分分裂，，这样样不断断地分分解，，不断断地应应用规规则，，直到到所产产生的的状态态是M字符符为止止，即即终止条条件分分解为一个个M字字符作作成的的状态态。1/7/202342重写问问题的的与/或树树(C,B,Z)CBZ(D,L)(B,M)(M,M)(B,B,M)DLBM(M,M)MMMMBMB(M,M)(M,M)MMMMR1R2R3R4R3R3R31/7/202343定义能够把把产生生式系系统综综合数数据库库的状状态描描述分分解为为若干干组成成部分分，产产生式式规则则可以以分别别用在在各组组成部部分上上，并并且整整个系系统的的终止止条件件可以以用在在各组组成部部分的的终止止条件件表示示出来来的产产生式式系统统，