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

1、实验一一、实验目的：掌握产生式系统解决汉诺塔算法的基本思想。二、问题描述：331三、问题分析及基本思想：下：1、设计该问题的状态。使用了二维数组描述汉诺塔的状态，对 n 个盘子由大到小分别用数组 n、n-1.2、1 描述。例如：当 n4 时，二维数组为：1002003004002、定义目标状态。当 n4 时，这里是：001002003004依据如下规则定义产生式规则：1、在移动盘子时，每次只移动 ABC 柱子上可以移动的盘子中最大的盘子。2、如果上一次已经移动了某个盘子，则下一次不能继续移动，即：一个盘子不1AB13、当某个可以移动的盘子摆放位置不唯一时要将当前状态入栈，并选择盘子移动前所在的

2、柱子的左侧（同理：反方向选择也可）柱子作为移动的目标柱子。规则自动生成。控制策略依据如下：1、根据以上产生式规则依据，在每次移动盘子时可选择产生式唯一，所以不需要考虑路径选择。2、当移动的是一组盘子中的最大盘子（即：在要移动的一组盘子中的最下面的盘子）时，观察目标柱子是否是C 柱子（最终结果所在柱子），如果是则表示当前盘子移动成功，并清空栈，转移问题（即减小一层盘子）；如果移动目标错误（AB新的产生式规则，并按此执行移动操作。31（最后一个盘子），C四、主要功能流程图如下：（注意：本设计控制盘子为九个）。五、源程序：package Hanoi;import java.util.Arrays;i

3、mport 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 intn3; System.out.println(初始状态：); for (int i = 0; i n; i+) firsti0 = i + 1; System.

4、out.println(Arrays.toString(firsti);/ 定义目标状态int end = new intn3; for (int i = 0; i n; i+) endi2 = i + 1;/ System.out.println(Arrays.toString(endi);int maxValue = n;/ 定义可以移动的最大盘子的值，初值Disk before = null;/ 定义上一个移动的盘子，初始值为null Stack stack = new Stack();/ 定义存放盘子状态的栈Stack bs = new Stack(); b: while (true)

5、 System.out.println(before: + before);DiskcanMoveDisk=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

6、= movePlace0;/ 如果可移动位置有两个，right为右侧位置左侧位置Disk left = movePlace0;/ 如果可移动位置有两个，left为if (movePlace.length = 2) if(movePlace0.y=(canMoveDisk.y+1)%3) right=movePlace0;left=movePlace1;else if(movePlace0.y=(canMoveDisk.y+2)%3) right=movePlace1;left=movePlace0;int a = new intn3; for (int i = 0; i n; i+)for (

7、int j = 0; j 3; j+)aij = firstij; stack.push(a);/ 把当前状态入栈if (before = null)bs.push(null);else Disk x = new Disk(before.x, before.y); bs.push(x);System.out.println(入栈);/System.out.println(right: + right); Hanoi.move(canMoveDisk, right, first); before =right;if (maxValue = 1 & Hanoi.findDiskPrice(righ

8、t, first)= 1& right.y = 2)break b;if (Hanoi.findDiskPrice(right, first) = maxValue) /如果移动了要移动的最大盘子/ 如果是则判断目标柱子是否是最终结果所在柱子if (right.y = 2) / 如果是/ 清空栈while(!stack.isEmpty() stack.pop();while(!bs.isEmpty() bs.pop();System.out.println(清空栈);maxValue =maxValue-1/ 要移动的最大盘子减1 else for (int i = 0; i n; i+)fo

9、r (int j = 0; j 3; j+) firstij = stack.peek()ij;stack.pop();/ 出栈恢复System.out.println(出栈恢复); Hanoi.print(first);Disk x = null;if (bs.peek() != null)x = new Disk(bs.peek().x, bs.peek().y); DiskcanMoveDisk2=Hanoi.findMoveDisk(first,x); bs.pop();Disk movePlace2 = Hanoi.movePlace(first,/System.out.printl

10、n(canMoveDisk:+ canMoveDisk2);/System.out.println(locateionNumber:+movePlace2.length);Disk r = movePlace20;/ 如果可移动位置有两个，right为右侧位置left为左侧位置Disk l = movePlace20;/ 如果可移动位置有两个，if (movePlace2.length = 2) if(movePlace20.y=(canMoveDisk2.y+1)%3) r=movePlace20;l=movePlace21;else if(movePlace20.y=(canMoveDis

11、k2.y+2)%3)r=movePlace21; l=movePlace20;置移动盘子Hanoi.move(canMoveDisk2, l, first);/ 选择左侧位/System.out.println(canMoveDisk:+ canMoveDisk2);/System.out.println(locateionNumber:+ movePlace.length);/System.out.println(left: +l); before =l;if (maxValue = 1 & Hanoi.findDiskPrice(left,first) = 1& l.y = 2)break

12、 b;/ 找出可移动的盘子private static Disk findMoveDisk(int a, Disk before) Disk d = new Disk3;/ 柱子1,2,3的顶部盘子for (int i = 0; i 3; i+) di = Hanoi.findTopDisk(i + 1, a);for (int i = 0; i 3; i+) if (before = null) return d0;else if (!before.equals(di)& Hanoi.findDiskPrice(di, a) != 0 & (Hanoi.findDiskPrice(di, a

13、) Hanoi.findDiskPrice(= 0 | d(i + 1) % 3, a)| Hanoi.findDiskPrice(di, a) Hanoi.findDiskPrice(d(i + 2) % 3, a)| Hanoi.findDiskPrice(d(i + 1) % 3,a).findDiskPrice(d(i + 2) % 3, a) =0)/ System.out.println(di);return di;return null;/ 找出可以移动的位置坐标private static Disk movePlace(int a, Disk canMoveDisk)Disk

14、d = new Disk2;int h = 0;/ h是数组Disk的下标int i = canMoveDisk.y;/ 当前可移动盘子的柱子纵坐标Disk d1 = findTopDisk(i + 1) % 3 + 1, a); Disk d2 = findTopDisk(i + 2) % 3 + 1, a); if (Hanoi.findDiskPrice(d1, a) = 0) dh = d1; h+; else if (Hanoi.findDiskPrice(canMoveDisk, a) Hanoi.findDiskPrice(d1, a) if (d1.x != 0) Disk d

15、0 = new Disk(d1.x - 1, d1.y); dh = d0;h+;if (Hanoi.findDiskPrice(d2, a) = 0) dh = d2;h+; else if (Hanoi.findDiskPrice(canMoveDisk, a) Hanoi.findDiskPrice(d2, a) if (d2.x != 0) Disk d0 = new Disk(d2.x - 1, d2.y); dh = d0;h+;Diskd3;if(d1!=null)d3 = new Disk2; d30 =d0;d31 =d1;elsed3 = new Disk1; d30 =

16、d0;return d3;/ 找出一个Disk对应坐标的盘子值private static int findDiskPrice(Disk d, int a) return ad.xd.y;/ 找出柱子i的顶部盘子private static Disk findTopDisk(int i, int a) int j;for (j = 0; j = a.length) Disk d = new Disk(a.length - 1, i - 1);return d;return null;/ 移动盘子,将盘子d1移至d2位置private static void move(Disk d1, Disk

17、 d2, int a) System.out.println(将盘子 + a) +从位置 + d1(d2.y + 1)+ 移至位置 + d2 + + (d1.y + 1) + 号柱子- + 号柱子);ad2.xd2.y = ad1.xd1.y; ad1.xd1.y = 0; Hanoi.print(a);/ 打印当前盘子位置分布private static void print(int a) for (int i = 0; i a.length; i+) System.out.println(Arrays.toString(ai);package Hanoi;/定义一个盘子的位置class Disk int x;/盘子的横坐标int y;/盘子的纵坐标public Disk(int x, int y) this.x = x;this.y = y;public