人工智能实验产生式系统解决汉诺塔

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

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

3、上产生式规则依据，在每次移动盘子时可选择产生式唯一，所以不需 要考虑路径选择。2、当移动的是一组盘子中的最大盘子（即：在要移动的一组盘子中的最下面的 盘子）时，观察目标柱子是否是C柱子（最终结果所在柱子），如果是则表示当 前盘子移动成功，并清空栈，转移问题（即减小一层盘子）；如果移动目标错误（即移动到了 A或B柱子）则执行回溯：栈顶状态出栈，向右选择目标柱子产生 新的产生式规则，并按此执行移动操作。3、如果要移动的一组盘子中最大的是1号盘（最后一个盘子），执行的移动操 作是将盘子移动到C柱子，则算法结束。四、主要功能流程图如下：（注意：本设计控制盘子为九个）。五、源程序:package Han

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

5、; i+) firsti0 = i + 1;System.outprintln(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;/定义上一个移动的盘子，初始值为nullStack stack = new Stack();/ 定义存放盘 子状态的栈Stack bs = new

6、 Stack();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:

7、+movePlace.length);Disk right = 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

8、;for (int i = 0; i n; i+)for (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.wove(canMoveDisk, right, first);before = right;if (maxValue

9、= 1 & Hanoi.findDiskPrice(right, 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

10、 else for ( int i = 0; i n; i+)for (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);Disk canMoveDisk2 = Hanoi. findMoveDisk(first, x); bs.pop();Disk movePlace2 = Ha

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

12、Place20;l=movePlace21;elseif(movePlace20.y=(canMoveDisk2.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 =

13、 1 & Hanoi.findDiskPrice(left, first) = 1& l. y = 2)break 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)& H

14、anoi.findDiskPrice(di, a) != 0& (Hanoi.findDiskPrice(di, a) Hanoi. findDiskPrice( d(i + 1) % 3, a) | Hanoi.findDiskPrice(di, a) Hanoi .findDiskPrice(d(i + 2) % 3, a)| Hanoi.findDiskPrice(d(i + 1) % 3, a) = 0 | Hanoi.findDiskPrice(d(i + 2) % 3, a) = 0) / System.out.println(di);return di;return null ;

15、/找出可以移动的位置坐标private static Disk movePlace(int a, Disk canMoveDisk) Disk 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.findDis

16、kPrice(canMoveDisk, a) Hanoi. findDiskPrice(d1, a) if (dl.x != 0) Disk d0 = new Disk(d1.x - 1, dl.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+;Disk

17、 d3;if(d1!=null)d3 = new Disk2;d30 = d0;d31 = d1;elsed3 = new Disk1;d30 = 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);retur

18、n d;return null ;/移动盘子，将盘子d1移至d2位置private static void move(Disk d1, Disk d2, int a) System. out .println(将盘子”+ Hanoi findDiskPrice(d1, a) + ”从位置”+ d1+ ”移至位置+ d2 + + (d1.y + 1) + 号柱子-+ (d2.y + 1)+ 号柱子);ad2.xd2.y = ad1.xd1.y;ad1.xd1.y = 0;Hanoi.print(a);/打印当前盘子位置分布private static void print(int a) for

19、(int i = 0; i a.length; i+)System.outprintln(Arrays.toString(ai);package Hanoi;/定义一个盘子的位置class Disk int x;/盘子的横坐标int y;/盘子的纵坐标public Disk(int x, int y) this.x = x;this.y = y;public boolean equals(Disk d) if (this.x = d.x & this.y = d.y) return true;return false;Overridepublic String toString() retur

20、n Disk + ( + this.x + , + this.y + );六、运行结果（9层汉诺塔结果）:Problems iw JavadocDeclarati on Console 3 Hanoi (1) Java Application C:Program FiIesJavajdk1.7.0 25binjavaw.exe (20154月11 日*4入江肘陞子莉个纹=1,矶 兀S 3, S 4,码 5,饥 &.码 兀S 国码 如矶before s nullA花陞子L土皿。i sk(0j)g至iADi 5 k ( 8,1) 1号芒于-m号在亍 国,矶0 2.码钊 3, S 好 4, 0. 0

21、 5,饥 0 sj % G 7,码时 % % 0 ,L。before:Disk(8jl)花陞于初、,旧)慈至iiDiskt&j 2) 1号斐于-f 3号在于0, 0. 0国,S 0 口,码可 4,码 0 5 0 6,码 0 兀 0 京码0 % L 2before:Di3k(8j2)terminatedHanoi (1) Java Application C:Program FiIesJavajdk1.7.0 25binjavaw.exe (2015年4月 11E入校捉鱼于1从位置Disk(8,l)移至卫置Disk(7,2) 2号芸于3号芸于。，。，0。，。，03, 。， 04,。，05, 。，

22、 06, 。， 07,。，08, 。， 19, 。， 2before:Disk(7?2)捉鱼于3从位置Disk(2,。)移至卫置Disk(8,l) 1号芸于2号芸于。，。，0。，。，0。，。，04,。，05, 。， 06, 。， 07,。，08, 。， 19, 3, 2before:Disk(8?l)AS捉鱼于1从位置Disk(7,2)移至卫置Disk(2,。)3号芸于1号芸于。，。，0。，。，01, 。， 04,。，05, 。， 06, 。， 07,。，08, 。， 09, 3, 2before:Disk(2J0)捉鱼于2从位置Disk(8,2)移至卫置Disk(7,l) 3号芸于2号芸于P

23、roblems Ja?adoc |5j；n Decl：=Lt_ation Console ： Hanoi (1) Java Application C:Prcgram FiIesJavajdk1.7.0_25binjavaw.exe (2D15年4月11 日 u =.J m 口d v =J_ J J J. J- / 叶 n 仁冒仁S % 0如给0L 码 04, 0, 05, e, a6, 0, 0P.码 0京 L 0如 3, 0before :Disk(7.l)将会子LLtiDimkQ。)秽垄:ziDi5k(8,1) 1号栏于-*2号芝予 也码B 0, % 饥 0,町 0 4,给 0 5,饥

24、0 6,吼 0 孔 1, 0 % L 0 9, & 0before :Disk(6l)4?&Jf4tiDi3k(3J0)5ziDisk(8J2) 1 号差于-T 号W 于 绮务00,给 0绮 % 00,给 0 5% 08,给 0N 1, 0 8, 2, 0 % 3, 4 before :Disk(8j2) 入粳sk(6j 1)SDisk(7j 2) 2号栏于-T号芝予 re,队 elProtlemE Jaradoc 恒:.Decl：=Lfati on曰 CunEule W3 Hanoi (1) Java Application C:Progranni FiIesJavajdk1.7.0 25b

25、injavaw.exe (201月 11 日给 0, 81,矶 9before:Disk(l2)驾校花会于L史坦Dimlc(8g)程基口。档1但，1) 1，斐于-W号斐于给%给%给%给%给幻2345 刃1,日检猴饥务饥务饥务饥务1，7B9一层汉诺塔:TrollenE 疝 Tax ado c HeclAratiorL Q Console 3 Hetnoi (1) Jma Application GPrograiri FilavsiSjdk1.7.0 25binjavaw.cxc (20154月 11 日下午乐48:1.2)脚;口涯于站中螳：对屋L H 0befcresriulL布子顼位置Dis

26、k(0j.ft)S SXJtDis成 1) 1气在于-，2号E子% 1* 0土枝左盘L 饥 0变适于顼.位置Disk(8.如程=iJtDisk(%2) KWF-3号子% 饥 1二层汉诺塔:ri.%T，rbWTN.普？rbWTNrttlnJ n. 7 r9j 富疽)喂SM叫阍餐IQ)喂HH日言0*3 rHm一 k GJ N , s_u z *EI I试一 k 成 prErm F凸 H 图 控中e?)专-H3#.电 E 肿削中 PH* 崩凸 SLOJ.置z KJ I r的一 k 成 5 rrlYm 察=应日3.言卜 * 号z rH.E 一 0 成 G r, (3 吊浦VH) V-H33.奇*嘲蜂

27、(tz-hliq&H rH-E 一 kS7NJ j (TcrvM-H凸月.倒竺 w Grw 甫* 裨vTTnualILIJOM-nJq“蜜祖用5Tt岸KE二皿 巴 土莅手*mMHLOJlo.pnmAse-lzEEEdJ3 忠*-c-dmnEaUBH n pmw.EEmt贸VI胃.WJ回小条Nri.SE?%氏*忠？小条HL 皿耳扫 QrJJun-rt-Mdnlsu.ygFT%-Huulanx.! -wsom7 ,.H n n9EH m-H凸胃,图浦(ii 捋凸日Xr4匹期翎 粤. 0Ir5KSEWqSNKZ rtr告凸胃，图竺0，I) X告凸胃-.寺rbE尊(tJrs-He叫如* qHN中rr ,C IrtrM-H凸胃，*SM M!-!凸日音告翎 可.,IlnLKQJJIo七- s rw 3 “住*普显NU_LneorEA5QJ-_LL.EESD-ldbc匚04昌一-址ra11.2片以1*口 幽 MFEAE- SEalqE1(=一oezehApdJA