资源描述：
《LISP语言及其在人工智能中的应用(三).pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、DOI:10.13976/j.cnki.xk.1980.06.012LlsP语言及其在人工智能中的应用(三)宋国宁(中国科学院沈阳自动化所)(,一1)个盘子转移到缓冲①首先解决顶上;号例1解智力难题棒上的问题。,;②移动第个盘子这是一个简单问题:,,(,一1)个盘子的问题的描述在桌上竖着三根细棒A③最后解决缓冲棒上的.。B,C在,A棒上套着一叠盘子盘子中间穿转移问题,正好可以套,,,孔在棒上盘子叠放的次序按直也就是说解决个盘子的转移问题取决,。径大小由下往上排列如图所示于,一1)个盘子的转移问题,
2、(这仍然是一个复,,因为盘杂问题但复杂的程度毕竞降低了些。,子的数目少了一个根据同样的思路解决(,一1)个盘子的转移问题,又可以分解成三个子问:题(,一2)个盘子的转移问题;①先解决②然后移BC:一1)个盘子;动第(③最后还得再解决一次,一。,现在的任务是要将A棒上盘子全部转移到(2)个盘子的转移问题这样一直分解下去,C棒上(用B棒作为缓冲)在转移盘子时必须最后问题全部简化为移动一个盘子的问题而遵守:!(如下二条规则这恰恰是简单的问题这也就是递归的出.。1口,否则,每次只能移动最上层的一个盘子将发
3、生无限递归的情况)也许有人2.大盘子不许放到小盘子上面。问,这样移动盘子是否能在每一步中都遵守上。,,面提出的二条规则呢当盘子数目较少时(例如长5)很容易?回答是肯定的因为在,,人就会乱,只要保证每个子解这个问题但当盘子数目增加时将问题分解为三个子问题时。,、。套要求用LISP语言写出一个算法由计算问题都遵守规则则全体也是遵循规则的而这。机来解决这个智力难题些子问题的解决最后都归结为移动最上面一个:,,问题的分析这是一个典型的应用递归概盘子而这恰好是符合规则的因为它是最小。。念的;例子我们的总体任
4、务是从A转移个盘的一个子到,,:C去由于规则的限制我们不能随心所把问题化为表处理问题要用LISP语言,,欲的移动盘子关键的问题是首先要设法把顶来解决上述问题关键的一步是将问题转化为,。二,,:,上的(卜1)个盘子从A转移到B然后才能从表处理问题我们可以一般地假定少为,。A将最大的一个盘子移动到C最后设法把B三根棒的名称在每根棒上套着的盘子情况称,一,刀。,上的(1)个盘子转移到C也就是将转移为状态这个状态可以用原子特性表来描述:,::个盘子的问题分解成三个子问题例如A上套着九个盘子状态就是(DD…
5、…LISP语言及其在人工智能中的应用(三)。.),二;S;;从盘子的移动意味着状态在变化这些变Put〔TATENIL〕。transfer〔length〔disk〕;x;少;:〕;化要及时地打印出来,return按照LISP程序的惯例我们首先定义一〔OK〕〕,,。ransr。;x;;二=ro;些函数最后调用这些函数问题就得到解决tfe〔少〕Pg〔()u:ze:,=ireturnove;:;首先定义一个函数Pl它的任务是〔〔m,〕〕〕建立原子特性表,并调用转移移个盘子的函数transfe一r〔,一1;
6、二;礼少;〕,.atransfer,move〔公;幻;一transr:transr。一i;少;二;:;定义函数fe它的任务是将问题化fe〔〕〕,“ove”.ove=ro,;,;简最后分解成挪动一个盘子的函数mm〔二;幻Pg〔〔〕move:,:=et;定义函数它的任务是具体实现娜g〔补STATE〕。、;;cr:;动一个盘子的操作(反映在特性表的变化上)Put〔STATEd〔〕〕。,:=et;并且将这个操作打印出来g〔补STATE〕Pu:zle〔disk;叉;7;二〕=Prog〔();Put〔:;sT
7、ATE;eons〔ear〔,〕;,〕〕,Put〔二;STATE;disk〕;Print〔list〔MOVE;ear〔:〕;FRO城Put〔少;STATE;NIL〕;X;TO;么〕〕〕一“xr:用Sp形式写的完整ILSP程序如下DEFINE(((PUZZLE(LAMBDA(DISKXYZ)(PROG()(PUTX(QUOTESTATE)DISK)(PUTY(QUOTESTATE)NIL)(PUTZ(QUOTESTATE)NIL)(TRANSFER(LENGTHDISK)XYZ)(RETURN(QUO
8、TEOK)))))(TRANSFER(LAMBDA(NXYZ)(PROG()(COND((EQUALNl)(RETURN(MOVEXZ))))(TRANSFER(SUBIN)XZY)(MOVEXZ)(TRANSFER(SUBIN)YXZ))))(MOVE(LAMBDA(XZ)(PROG(UV)(SETQU(GETX(QUOTESTATE)))(PUTX(QUOTESTATE)(CDRU))(SETQV(GETZ(QUOTESTATE)))(PUTZ(QUOTESTATE)(CONS
