【doc】建立产生式系统求解八数码难题.doc
建立产生式系统求解八数码难题第27成宁学院led{Vo1。27,No。3Jun。2007文章编号:1O06—5342(2O07)O3一O063～O2建立产生式系统求解八数码难题(1。成宁学院信息工程学院计算机系,湖北成宁437100~2。咸宁市高级中学,湖北成宁437005)摘要:产生式系统可以很好地模拟人类推理的思维过程。所以在建立人工智能系统时,人们常常利用产生式系统建立人类认知的模型来解决一些难题。本文利用产生式系统解决了八数码难题。关键词:人工智能;产生式系统;八数码问题中图分类号:TP18文献标识码:A引言产生式系统是人工智能的一种问题表达模型hao123,反映了人工智能的结构特征,便于描述人工智能问题空间的搜索过程。产生式系统既可用来描述人的认知过程(属思维科学领域)114信息网sitemaps,也可作为一种通用的问控制系统题表达模型。其突出特点是模块性好E。综合数据库,产生式规则集和控制系统,被称为产生式系统的三要素E。这里的综合数据库,只是借用了数据库这样一个名词,与我们通常所说的数据库概念并不一致。它是个数据的集合,用于存放在推理过程中的已知条件推导出的中间结果和最终结论等。
一组产生式规则(规则集)相当于系统的知识库,它采用"IF前件THEN后件"的形式,来表达求解问题所需要的知识。其中规则的前件表达的是该条规则所要满足的条件,规则的后件表示的是该规则所得出的结论,或者动作。规则表达的可以是与待求解的问题有关的客观规律方面的知识,也可以是对求解问题有帮助的策略方面的知识。以中国象棋为例,前者描述的是象棋的走棋规则,如"马走日","象走田"等。这是系统所必须表达出来的知识。而后者描述的则是在什么情况下,应该如何走棋才能战胜对手,或者什么样的局面比较有力,什么样的局面不利等。这方面的知识与搜索结合在一起,决定了系统下棋的水平。控制系统,又称为控制策略或者搜索策略,用于控制系统的运行,它根据综合数据库中的当前数据,来选择合适的规则。不同的选择规则的方法,就构成了不同的控制策略。因此,控制系统也可以称之为推理引擎。产生式系统的特点(1)数据驱动。系统是在数据的驱动下运行的,数据一旦发生变化,如增加数据,删除数据等,就会导致系统行为的变化。而一旦数据不再发生变化,系统的运行也就停止(2)独立性。独立性包含两方面的含义。其一实验二 利用状态空间搜索法实现八数码问题,数据(综合数据库),知识(规则集)和控制(控制系统),三者之间是*收稿日期:2006—05—28相互独立的,而不是混杂在一起的。
其二,规则之间是相互独立的,不同的规则之间没有明显的连接关系,规则之间是通过数据联系在一起的。这样可以方便规则集的维护,例如,一条规则的修改或者增删,不需要考虑它与哪些规则相关联。由于规则之间是相互独立的,因此一般来说,问题的求解与规则的排列顺序无关。八数码难题的描述[3?八数码难题是人工智能的一个经典的问题。其具体的描述如下:在3X3的棋盘上,摆有8个棋子,在每个棋子上标有1中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是,给出一种初始布局(初始状态)和目标布局(目标状态),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。初始状态和目标状态。如下:初始状态目标状态28365由于题目要找的解是达到目标的最少步骤,因此可以这样来设计解题的方法:初始状态为搜索的出发点,把移动步后的布局全部找到,检查是否有达到目标的布局【doc】建立产生式系统求解八数码难题.doc,如果没有,再从这些移动一步的布局出发,找出移动两步后的所有布局,再判断是否有达到目标的布局。依此类推,一直到某布局达到目标状态为止,然后输出结果。由于是按移动步数从少到多产生新布局,所以找到的第一个目标一定是移动步数最少的一个,也就是最优解。
八数码问题的产生式系统建立(1)综合数据库。用3X3的二维数组来表示棋盘的布局比较直观。我们用ChEi,j]表示第i列格子上放的棋子数字,空格则用0来表示。为了编程方便,还需要存储下面三个数据:该布局的空格位置(Si,Sj);初始布局到该布64咸宁学院第27局的步数实验二 利用状态空间搜索法实现八数码问题,即深度dep;以及该布局的上一布局,即父结点的位置(pnt)。这样数据库每一个元素应该是由上述几个数据组成的记录。在程序中,定义组成数据库元素的记录型为:----:array[1。。3,1。。3]ofbyte;{存放某种棋盘布局}si,sj:byte;{记录此布局中空格位置)dep,pnt:byte;end;(2)产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察,也可看作空格向上,下,左,右四个位置移动,这样处理更便于编程。设空格位置在(Si,sj),则有四条规则:1)空格向上移动:ifsi一1一1thench[si,sj]:=ch[si1,sj];ch[si一1,sj]:一O2)空格向下移动:江si+1一3then[si,sj]:=ch[si+1,sj];ch[si+1,sj]:一O3)空格向左移动:ifsj一1一1then[si,sj]:=ch[si,sj一1];ch[sl,sj4)空格向右移动:ifsj+1=3then[si,sj]:=ch[si,sj+1];ch[si,sj+1]:一O用数组Di和Dj来表示移动时行列的增量,移动后新空格的位置可表示为:nx:=si+di(r)ny:一sj+dj(r)其中,r=l,2,3,4为空格移动方向,且r1234方向左上右下diO一1O1dj一1010(3)控制策略它规定在什么条件下用什么规则进行操作,什么条件下停止运行,即它规定了问题求解的搜索策略和路线。
因为新产生的结点深度(从初始布局到该结点的步数)般要比数据库中原有的结点深度大(或相等)。按广度优先搜索的算法,深度大(步数多)的结点后扩展,所以新产生的结点应放在数据库的后面。而当前扩展的结点从数据库前面选取,即处理时是按结点产生的先后次序进行扩展。这样广度优先搜索的数据库结构采用队列的结构形式较合适。我们用记录数组data来表示数据库,并设置两个指针:Head为队列的首指针,tail为队列的尾指针。本文采用的搜索策略为广度优先策略。一些重要部分的实现(1)检查某步移动是否可行的函数(k:integer):boolean;beginni:=t锄p。si+di[k];nj:一t咖p。sj+djif(niin[1。。3])and(njin[1。。3]):一:=false;end;(2)检查队尾新存人布局是否已在队列中存在的函数:boolean;vari,j,k:integer;buf:boolean;:=falsei:一0; {变量将i 依次指向队列中的各个布局(最后一个除外) 的位置} repeat inc(i);buf:一true; f0rj:一1to3do f0rk:一1to3do ifdata[i]。
chEi,k]~dam[tail]。ch[。i,k] {dam[tail]是队列中最后一个元素即新产生的布局) thenbur:一false; (i=tail {buf=truee新布局与队列中布局有重复) dupe:一buf end; (3)比较是否达到目标布局状态的函数 :boolean; vati,j:byte begin goals:一true; f0ri:一1to3do f0rj:一1to3do ifdata[tail]。ch[i,j]goal[i,j] :=false{未达到目标布局) end; 实验及结果本文根据上述原理和方法,使用Pascal 语言编程实现 了求解八数码难题,程序运行结果如下: 输人数据:283123 164——+8O4 705765 运行结果: 2832832 164 一104 一184 一184 一084 一804 7765765 结束语八数码难题是人工智能的一个经典的问题。本文通过 使用产生式系统和Pascal 语言程序解决了八数码问题,本 程序能够实现从一个初始状态到目标状态的搜索,一般情 况下,总能得到最优的搜索过程,提高了搜索效率。
参考文献: [1]王万森。人工智能原理及其应用[M]。北京:电子工业出 版社,2000。 [2]孙成存,李凯,赵克。产生式系统分析和应用[J]。电 子科技,2004,(9)。 [3]唐朝舜,董玉德。八数码的启发式搜索算法及实现[J]。 安徽职业技术学院,2004,3(3)。 [43 张信一,黎燕。基A3 算法的八数码问题的程序求解 l-J]。现代计算机,2003,5(14)。
【本文来源于互联网转载，如侵犯您的权益或不适传播，请邮件通知我们删除】