人工智能实验产生式系统解决汉诺塔(有代码)

《人工智能实验产生式系统解决汉诺塔(有代码)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一一、实验目的：掌握产生式系统解决汉诺塔算法的基本思想。二、问题描述：如图所示放置3根柱子，其中一根从上往下按由小到大顺序串有若干个圆盘，要求通过3根柱子移动圆盘。若规定每次只能移动1片，且不许大盘放在小盘之上，最后要将圆盘从一根柱子移动到另一根柱子上。三、问题分析及基本思想：汉诺塔(也被称为梵塔)问题有很多解决方法，比较典型的是使用递归算法，而本次设计的算法则是应用人工智能中产生式相关知识进行的求解。数学模型描述如下：1、设计该问题的状态。使用了二维数组描述汉诺塔的状态，对n个盘子由大到小分别用数组n、n-1...2、1描述。例如：

2、当n＝4时，二维数组为：1002003004002、定义目标状态。当n＝4时，这里是：001002003004依据如下规则定义产生式规则：1、在移动盘子时，每次只移动ABC柱子上可以移动的盘子中最大的盘子。2、如果上一次已经移动了某个盘子，则下一次不能继续移动，即：一个盘子不能被连续移动两次。如：某次操作将1号盘子由A柱子移动到B柱子，那么在选择下一个要移动的盘子时应不在考虑1号盘。3、当某个可以移动的盘子摆放位置不唯一时要将当前状态入栈，并选择盘子移动前所在的柱子的左侧（同理：反方向选择也可）柱子作为移动的目标柱子。为提高程序运行过

3、程中的空间利用率，产生式规则在汉诺塔移动过程中依据以上规则自动生成。控制策略依据如下：1、根据以上产生式规则依据，在每次移动盘子时可选择产生式唯一，所以不需要考虑路径选择。2、当移动的是一组盘子中的最大盘子（即：在要移动的一组盘子中的最下面的盘子）时，观察目标柱子是否是C柱子（最终结果所在柱子），如果是则表示当前盘子移动成功，并清空栈，转移问题（即减小一层盘子）；如果移动目标错误（即移动到了A或B柱子）则执行回溯：栈顶状态出栈，向右选择目标柱子产生新的产生式规则，并按此执行移动操作。3、如果要移动的一组盘子中最大的是1号盘（最后一个盘子）

4、，执行的移动操作是将盘子移动到C柱子，则算法结束。四、主要功能流程图如下：（注意：本设计控制盘子为九个）。五、源程序：packageHanoi;importjava.util.Arrays;importjava.util.Scanner;importjava.util.Stack;publicclassHanoi{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);System.out.println("请输入汉诺塔盘子的个数：");intn=in.next

5、Int();//定义初始状态int[][]first=newint[n][3];System.out.println("初始状态：");for(inti=0;i

6、lue=n;//定义可以移动的最大盘子的值，初值Diskbefore=null;//定义上一个移动的盘子，初始值为nullStackstack=newStack();//定义存放盘子状态的栈Stackbs=newStack();b:while(true){System.out.println("before:"+before);DiskcanMoveDisk=Hanoi.findMoveDisk(first,before);//找出当前可移动盘子//System.out.prin

7、tln("canMoveDisk:"+canMoveDisk);Disk[]movePlace=Hanoi.movePlace(first,Hanoi.findMoveDisk(first,before));//返回当前可移动去的位置数组//System.out.println("locateionNumber:"+movePlace.length);Diskright=movePlace[0];//如果可移动位置有两个，right为右侧位置Diskleft=movePlace[0];//如果可移动位置有两个，left为左侧位置if(mo

8、vePlace.length==2){if(movePlace[0].y==(canMoveDisk.y+1)%3){right=movePlace[0];left=movePlace[1];