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

实验一一、实验目的：掌握产生式系统解决汉诺塔算法的基本思想。二、问题描述：如图所示放置3根柱子，其中一根从上往下按由小到大顺序串有若干个圆盘，要求通过3根柱子移动圆盘。若规定每次只能移动1片，且不许大盘放在小盘之上，最后要将圆盘从一根柱子移动到另一根柱子上。 三、问题分析及基本思想：汉诺塔(也被称为梵塔)问题有很多解决方法，比较典型的是使用递归算法，而本次设计的算法则是应用人工智能中产生式相关知识进行的求解。数学模型描述如下：1、设计该问题的状态。使用了二维数组描述汉诺塔的状态，对n个盘子由大到小分别用数组n、n-1...2、1描述。例如：当n＝4时，二维数组为：1002003004002、定义目标状态。当n＝4时，这里是：001002003004依据如下规则定义产生式规则：1、在移动盘子时，每次只移动A\B\C柱子上可以移动的盘子中最大的盘子。2、如果上一次已经移动了某个盘子，则下一次不能继续移动，即：一个盘子不能被连续移动两次。如：某次操作将1号盘子由A柱子移动到B柱子，那么在选择下一个要移动的盘子时应不在考虑1号盘。3、当某个可以移动的盘子摆放位置不唯一时要将当前状态入栈，并选择盘子移动前所在的柱子的左侧（同理：反方向选择也可）柱子作为移动的目标柱子。为提高程序运行过程中的空间利用率，产生式规则在汉诺塔移动过程中依据以上规则自动生成。控制策略依据如下：1、根据以上产生式规则依据，在每次移动盘子时可选择产生式唯一，所以不需要考虑路径选择。2、当移动的是一组盘子中的最大盘子（即：在要移动的一组盘子中的最下面的盘子）时，观察目标柱子是否是C柱子（最终结果所在柱子），如果是则表示当前盘子移动成功，并清空栈，转移问题（即减小一层盘子）；如果移动目标错误（即移动到了A或B柱子）则执行回溯：栈顶状态出栈，向右选择目标柱子产生新的产生式规则，并按此执行移动操作。3、如果要移动的一组盘子中最大的是1号盘（最后一个盘子），执行的移动操作是将盘子移动到C柱子，则算法结束。四、主要功能流程图如下：（注意：本设计控制盘子为九个）。五、源程序：package Hanoi;import java.util.Arrays;import java.util.Scanner;import java.util.Stack;public class Hanoi {public static void main(String[] args) {Scanner in = new Scanner(System.in);System.out.println(请输入汉诺塔盘子的个数：);int n = in.nextInt();// 定义初始状态int[][] first = new int[n][3];System.out.println(初始状态：);for (int i = 0; i n; i++) {first[i][0] = i + 1;System.out.println(Arrays.toString(first[i]));}// 定义目标状态int[][] end = new int[n][3];for (int i = 0; i n; i++) {end[i][2] = i + 1;// System.out.println(Arrays.toString(end[i]));}int maxValue = n;// 定义可以移动的最大盘子的值，初值Disk before = null;// 定义上一个移动的盘子，初始值为nullStackint[][] stack = new Stackint[][]();// 定义存放盘子状态的栈StackDisk bs = new StackDisk();b: while (true) {System.out.println(before: + before);Disk canMoveDisk = Hanoi.findMoveDisk(first, before);// 找出当前可移动盘子//System.out.println(canMoveDisk: + canMoveDisk);Disk[] movePlace = Hanoi.movePlace(first,Hanoi.findMoveDisk(first, before));// 返回当前可移动去的位置数组//System.out.println(locateionNumber: + movePlace.length);Disk right = movePlace[0];// 如果可移动位置有两个，right为右侧位置Disk left = movePlace[0];// 如果可移动位置有两个，left为左侧位置if (movePlace.length