人工智能chp1_第1页
人工智能chp1_第2页
人工智能chp1_第3页
人工智能chp1_第4页
人工智能chp1_第5页
已阅读5页,还剩35页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、人工智能(rn n zh nn)(AI)第一章 产生式系统(Production System)1.1 产生式系统结构1.2 产生式系统特点1.3 产生式系统适用范围1.4 产生式系统示例1.5 产生式系统的一般性算法1.6 产生式系统的基本控制策略1.7 产生式系统分类(fn li) 参考书:人工智能导论 作者:林尧瑞、马少平 出版社:清华大学出版社 人工智能原理 作者:石纯一、黄昌宁 出版社:清华大学出版社 人工智能基础 作者:高 济、朱淼良 出版社:高等教育出版社共四十页第一章 产生式系统(Production System) 产生式系统起源于美国数学家Post于1943年提出的称为产生

2、式系统的计算模型,以称为产生式的规则描述符号串替代运算,用于描述形式语言的语法,表示人类心理活动的认知过程,许多著名的专家系统都用产生式规则表示知识,或则说目前大多数专家系统都采用产生式系统的结构(jigu)方式来建立的。 共四十页第一章 产生式系统(Production System)1.1 产生式系统结构 产生式系统由三个部分组成(1) 综合数据库(Globe Database) 称为:事实库、上下文库等。 作用:存放问题求解过程中产生的状态描述信息,可以是事实元素集,数据结构,如向量、数组、表格等。 例如(lr)1:关于动物世界的产生式系统有如下综合数据库: (Mammal Dog),

3、(Eat Dog Meat) 共四十页第一章 产生式系统(Production System)(2) 规则库(Rule Base)称为:规则基、规则集等。 作用:存放规则知识。 产生式规则的一般表达形式:IF THEN (如果 那么 ) 例如1:关于世界动物的产生式系统规则: 若某动物是哺乳动物(brdngw),且吃肉; 则这种动物是食肉动物。 IF A 是一种动物 AND A 是哺乳动物 AND A 吃肉 THEN A是肉食动物 共四十页第一章 产生式系统(Production System)应用便于计算机操作的形式话方式表示:(Mammal ? x)(Eat ? X Meat)=(Carn

4、ivore ? x) 一般情况下依据规则右侧的表示方法把规则分类为:条件动作(dngzu)型和前提结论型。上例为前提结论型,看下例。例2:x 1 1 null(y) = x:= 0 由于规则的结论可视为对综合数据库的增加操作,方便起见不再区分两种规则。共四十页第一章 产生式系统(Production System)(3) 控制系统(Control System) 控制系统是产生式系统的推理机,驱动和控制整个系统的运行。过程: 1. Data初始数据库; 2. Until Data 满足结束(jish)条件以前, do; 3. Begin 4. 在规则中选适合与Data的规则R; 5. Dada

5、 R应用到Data得到的结果 6. end 共四十页第一章 产生式系统(Production System) 在一个循环的识别阶段,若有多于一条(y tio)的规则激活就称引起了一个冲突。基于某种控制策略选定要执行的规则是冲突解决。策略有三类: First 选择首条激活的规则执行; Best 选择规则中最好的执行; All 执行所有激活的规则。 共四十页第一章 产生式系统(Production System) 例如:关于动物世界的产生式系统中已建立数据库和规则(guz)库。该规则(guz)的左部两个匹配模式(Mammal ? x)和(Eat ?x)分别与综合数据库中的事实元素(Mammal D

6、og)和(Eat Meat)匹配,从而得以激活,并将右部的结论(Carnivore Dog)送入综合数据库。 1.2 产生式系统应用实例实例1:八数码问题(Eight Puzzle)规则库:R1 j0-11= Siojo:=Sio(jo-1)Sio(jo-1):=0 空格左移R2 i0-11= Siojo:=S(io-1)joS(io-1)jo:=0 空格上移R3 j0+13= Siojo:=Sio(jo+1)Sio(jo+1):=0 空格右移R4 i0+13= Siojo:=S(io+1)joS(io+1)jo:=0 空格下移共四十页第一章 产生式系统(Production System)

7、显然规则R1, R2, R3可以激活。若用解决策略First, 则R1右部的操作(cozu)得以执行,综合数据库变换。为快速搜索到解答,应用Best策略选取激活的规则,可以采用启发式函数W(n)判断下步使用规则。2831647512386475=共四十页第一章 产生式系统(Production System)实例2:传教士与野人问题(Missionaries and Cannibals) N个传教士和N个野人渡河,一条船,每次至多乘k人,任何时候岸上或船上:传教士人数(rn sh)野人数(rn sh)。渡和策略?(N=3, k=2为例) 规则库(10条):if(Ml,Cl,Bl=1) then

8、 (Ml-1,Cl,Bl-1); (p10操作)if(Ml,Cl,Bl=1) then (Ml,Cl-1,Bl-1); (p01操作)if(Ml,Cl,Bl=1) then (Ml-1,Cl-1,Bl-1); (p11操作)if(Ml,Cl,Bl=1) then (Ml-2,Cl,Bl-1); (p20操作)if(Ml,Cl,B=0) then (Ml,Cl+2,B+1); (q02操作) 共四十页第一章 产生式系统(Production System)综合数据库(20合法状态):(Ml,Cl,Bl),其中 0Ml,Cl3, Bl0,1 (0,0,1) (0,0,0) (0,1,1) (0,1

9、,0) (3,3,1) (3,3,0) 问题描述: (3,3,1)(0,0,0) 讨论:用产生式系统求解问题常常(chngchng)引入状态空间图概念,它是一个有向图,结点表示问题的各种状态(综合数据库元素),结点间弧线代表对应规则的操作,可以把一种状态导向另一种状态。本例N=3的M-C问题对应的状态空间图见参考书图1.3(P22)。共四十页第一章 产生式系统(Production System)实例3:旅行商问题(Business Traveler) A城工作的推销员需去个外地城市B,C,D,E办理业务,每个城市只允许(ynx)去一次,遍历这些城市后回到城市A。寻最短遍历路线。 规则库: R

10、1: not-visit(x) = move(x)指示未访问过城市xR2: visit-all() = move(A) 指示已遍历过各城市操作函数move(x)指示去城市x并将x加进城市名列表。综合数据库(初始):A 问题描述:当综合数据库中包含所有城市且走过的路径最短。共四十页第一章 产生式系统(Production System) 控制策略:由于有4个外地城市所以开始时应用规则R1,有4条规则实例被激活,即x分别取值B,C,D,E。而如果以上下两城市间路径最短作为(zuwi)冲突解决的依据则应先取C。依次经由推理相继走向D,B,E。最后用R2激活,推销员返回A。78ABED61510C56

11、13312共四十页第一章 产生式系统(Production System) 1.3 产生式系统控制策略 分析产生式系统的循环: 3.Begin 4. 在规则中选适合于Data的规则R; 5. Dada R应用到Data得到的结果 6.end 在产生式系统的实际应用中有两点是重要的:一是数据库元素和规则的表示方式,二是对Data选择规则的使用(shyng)方法(搜索策略)研究。 1.不可撤回方式;2.试探性方式包括:回溯方式、图搜索方式。 共四十页第一章 产生式系统(Production System) 1.3.1 不可撤回方式(Irrevocable) 根据当前可靠的局部知识选一条可用规则作用

12、于当前数据库,再根据新状态继续选取规则搜索下去,不必考虑撤回用过的规则。所谓“可用”实际就是应用“Best”冲突解法控制求解过程,相当于应用启发式知识搜索最好的规则。 在这种方式下,识别-行动循环一个接一个推动问题求解向目标状态前进,即使有些循环中选用(xunyng)的规则在执行后发现不合适甚至错误也不撤消,而是选择新的更适合的规则弥补造成的不良影响。共四十页第一章 产生式系统(Production System) 实例:爬山问题 人们在登山过程中目标是峰顶,问题是确定如何(rh)一步一步朝目标前进。很容易想到利用高度随位置变化的函数H(P),就变成在爬山过程中寻求函数极大值问题,不可撤回的。

13、zyxz0y0 x0p0(x0,y0,z0)爬山过程(guchng)示意图共四十页第一章 产生式系统(Production System) 人所处的位置P0,规定四种走法向东(x),向西(-x),向北(y),向南(-y)。可以(ky)用H(P)计算不同方向时高度变化的情况,即求出z1=H(x) H0, z2=H(-x) H0, z3=H(y) H0, z4=H(-y) H0, 然后选择z变化最大的走向攀登一步,进入新的位置P。即在梯度最陡的方向前进,重复这个过程直达到某点为止。 用爬山法只有在登单峰时才总是有效的。共四十页第一章 产生式系统(Production System) 实例:爬山问题

14、中的各种复杂情况(qngkung) 复杂情况下的数据库对于搜索是困难的,用不可撤回的方法可能导致达不到最高峰。下面是各种情况,虚线表示搜索点可能游走的方向。 (1) 多峰时搜索的初始位置不在最高峰区域可能导致局部的最高点,即陷入局部最优共四十页第一章 产生式系统(Production System) zyx复杂(fz)地形中的爬山路径示意图yxzyxxzyxx(2) 在有山脊的情况下若搜索的方向与山脊的走向一致,则就会停留在山脊处,并认为找到了极值点。(3) 当有多个孤立的高点下是大片平原,可能(knng)出现搜索点在平原区域游荡的情况。共四十页第一章 产生式系统(Production Sys

15、tem)实例1:八数码问题 用不在位置数码的个数表示当前状态的函数(hnsh)W(n)。(1) 可以寻到目标状态的情况 初始状态有三条规则可以应用,但是空格向上移动的函数值为3,属最小值。2831647512384765=283164752831476523184765283147651238476512384765共四十页第一章 产生式系统(Production System)实例1:八数码(shm)问题 (2) 搜索进入停止不动的情况 任何一个(y )应用于初始状态的规则都会使函数值增大,所以找不到全局最大。事实上从计算角度考虑通过移动空格是不可能达到目标状态的。初始状态逆序数9,而目标状

16、态为6。1257486312374865=共四十页第一章 产生式系统(Production System)实例1:八数码问题中逆序数的概念 对于八数码问题还有另外一个概念需要注意,逆序数的概念。我们可以把表格中的八个数值按照自然顺序做成一个向量,例如下面初始状态对应的向量为 (2 8 3 1 6 4 7 5),目标状态向量(1 2 3 8 4 7 6 5)。 从线性代数理论知道上述两个向量的逆序数分别为11 和 7。在八数码问题中有结论(jiln):如果目标状态和初始状态对应向量的逆序数奇偶性不一致,则我们就不能够通过正常的空格移动从初始态变化为目标态。共四十页第一章 产生式系统(Produc

17、tion System)实例1:八数码(shm)问题中逆序数的概念 28316475 针对前例中的第一个例题,其中的初始态和目标态对应向量的逆序数都是奇数,因此通过算法可以从初始态变换成目标态。而对于第二个例题,初始状态逆序数9,而目标状态为6。两者的奇偶性不一致,从计算(j sun)角度考虑通过移动空格是不可能达到目标状态的。即不存在从初始态到目标态的路径。1257486312374865=12384765=共四十页第一章 产生式系统(Production System) 1.3.2 回溯方式(Backtracking) 有时会发现选择的不合适规则导致找不到目标点,或拖延到达目标的过程。所以

18、某些情况下发现使用的规则不适合时允许退回某点选用另一条更可能的规则。但回溯的条件是什么呢?通过下面例题进行说明。 八数码问题(wnt)的回溯应发生在下面三种情况:1.新生成的状态在通往初始状态的路径上出现过;2.从初始态始,应用的规则达到了规定数目但搜索未达到目标点;3.对当前状态,再没有可应用的规则。共四十页第一章 产生式系统(Production System) 283164752831647583264175863241758326417583264175863241758342617583264175 右面表示了回溯式策略应用于八数码问题(wnt)时的局部搜索图。搜索深度规定为6,对于

19、此问题(wnt)在这个深度内一定可以找到目标点。但是一般情况下设置深度太浅可能找不到解,而设置深度太深可能导致回溯次数增加。1.2.1.2.3.共四十页第一章 产生式系统(Production System) 1.3.3 图搜索方式 把问题求解的过程用树状图进行描述,即图中的结点表示问题状态,结点间的弧表示应用的规则。图搜索方式就是用某种策略选择每一步骤使用的规则,并把状态变化过程用树状图结构记录,直到得出解,也即从树状图中搜索出含有解路径的子图。 上述是问题求解的三种方式:1、不可回撤方式; 2、回溯方式(表示对求解的路径可以修正); 3、图搜索方式(图形方法(fngf)表示搜索过程)。 下

20、图表示了八数码穹举搜索图。共四十页第一章 产生式系统(Production System) 28316475283164752831647583264175863241752368417528324765231867542831567428163754共四十页第一章 产生式系统(Production System) 1.4 产生式系统问题表示方法实例 实际问题中好的表示方法对寻求解是有很大帮助(bngzh)的,产生式系统也一样,下面是产生式系统两个表示方法实例。 1.4.1 旅行商问题 还是前节的实例3,利用书中P33图1.10所示的搜索控制方式产生部分搜索树,并由此计算出其中最合适路径的里程

21、来。但是对于复杂的旅行商问题用手工图的方式是不可行的。 共四十页第一章 产生式系统(Production System) 1.4.2 句法分析问题 文法分析中的初始数据库:The president of new company approves the sale,文法重写规则NNP,A NPNP,ofP,approves V , , theDET,产生式的目标条件是数据库具有单个符号S。 分析过程例如首先使用合适规则TheDET,saleN等,逐步过渡到使用NNP,A NPNP等规则,是最终数据库中出现符号S即判断出初始的数据库中是否(sh fu)语言中的句子,即符合自然语言的规则要求。句法

22、分析树请参阅教材P35图1.11句法问题的搜索树。共四十页第一章 产生式系统(Production System) 1.5 产生式系统类型 1.5.1 正向、逆向、双向产生式系统 正向产生式系统是从初始状态出发朝着目标状态这个方向使用规则的,即正推方式工作的,并称这些规则为F规则(forward Rule)。反之从目标状态向初始状态使用规则为逆向产生式系统,使用的规则称为B规则(Backward Rule)。同时使用F、B规则从两个方向进行搜索称为双向产生式系统。这时要求:将初始状态和目标状态合并构成综合(zngh)数据库,F规则只适应于初始状态描述,B规则适应于目标描述。其中控制策略所使用的

23、结束条件要表示成综合(zngh)数据库中初始状态描述部分与目标描述部分之间某种形式的匹配条件,而且搜索时还要决定每一步在那一段选用F规则还是B规则。 共四十页第一章 产生式系统(Production System) 1.5 产生式系统类型 例如八数码问题中如果目标状态只有一个,那么使用正向和逆向求解没有区别。当有多个显式表示的目标状态时,使用逆向求解可能产生较低的搜索效率。而双向求解时只有当综合数据库中正推状态描述与逆推目标描述完全匹配时,才可以结束(jish)搜索得到解,如果没有双向合适的匹配目标将极大地降低搜索效率。共四十页第一章 产生式系统(Production System) 1.5

24、产生式系统类型 1.5.2 可交换的产生式系统 当一个产生式系统对任何一个数据库D都具有下面性质时称该产生式系统是可交换的:(1) 可应用于D的规则集合对用了其中任意一条(y tio)规则之后生成的任何数据库,这个规则集合还适用;(2) 满足目标条件的某数据库D当应用任何一个可应用于数据库D的规则之后所生成的任何数据库,仍然满足目标条件;共四十页第一章 产生式系统(Production System) 1.5 产生式系统类型 1.5.2 可交换的产生式系统 (3) 若对D应用某一规则序列后得到一数据库D,则。当改变D的可应用规则集合中的规则次序后,仍然可求得解,即求得D与使用满足D的可应用规则

25、集合中的规则次序无关。 例子:(参考教材P36图1.12)S0是初始状态,Sg是目标态可应用于S0的规则集R1,R2,R3,对由S0生成的三个新状态(zhungti)前述规则集仍然适用,对其后裔状态(zhungti)也适用,但是对于新生成的数据库所添加的其他可应用规则,则不能随意交换、应用。(同样可参考教材P37图1.13)共四十页第一章 产生式系统(Production System) 1.5 产生式系统类型 1.5.3 可分解的产生式系统 将初始数据库分解成几个可以独立加以处理的分量,分别求解。即对每个分量数据库测试产生式规则可应用的条件,然后应用于每个分量生成新的数据库,如此分解、生成交

26、替进行直到(zhdo)每个分量数据库满足某种结束条件。但一般结束条件也应对应分解成各数据库满足的结束条件。 能够分解数据库和相应结束条件的产生式系统称为可分解的产生式系统。共四十页第一章 产生式系统(Production System) 1.5 产生式系统类型 1.5.3 可分解的产生式系统其SPLIT过程描述如下:(1) DAT:=初始数据库; (2) Di:=DAT的分解,每个Di都看成单独(dnd)数据库;(3) Until Di的所有元素都满足结束条件之前,do:(4) Begin(5) 从Di中选一个不满足结束条件的D*; (6) 从Di中删除D*(7) 在规则集中选择一条可以应用于D*的规则R(8) D:=R应用于D*的结果; (9) di:=D的分解式; (10)在Di中添加di(11) end 下面是几个可分解产生式系统例题。共四十页第一章 产生式系统 1.5 产生式系统类型字符重写问题的与或树表示初始数据库:C,B,Z; 结束(jish)条件:生成只包含M的数据库,即M,M,产生式规则: R1: C(D,L); R2:C(B,M); R3: B(M,M); R4: Z(B,B,M)。 应用图搜索方式求解可分解产生式系统时可用与或树结构来表示。(C,B,Z)CBZ(D,L)(B,M)(M,M)(B,B,M)DLMMBMB(M,M)(M,M)(M,M)MMMMMMB

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论