(人工智能实验.docVIP

人工智能 实 验 报 告 一、实验目的： 掌握产生式系统解决汉诺塔 二、问题描述：如图所示放置3根柱子，其中一根从上往下按由小到大顺序串有若干个圆盘，要求通过3根柱子移动圆盘。若规定每次只能移动1片，且不许大盘放在小盘之上，最后要将圆盘从一根柱子移动到另一根柱子上。 三、问题分析及基本思想：汉诺塔(也被称为梵塔)问题有很多解决方法，比较典型的是使用递归算法，而本次设计的算法则是应用人工智能中产生式相关知识进行的求解。数学模型描述如下：1、设计该问题的状态。使用了二维数组描述汉诺塔的状态，对n个盘子由大到小分别用数组n、n-1...2、1描述。例如：当n＝4时，二维数组为：100200300400 2、定义目标状态。当n＝4时，这里是：001002003004 依据如下规则定义产生式规则：1、在移动盘子时，每次只移动A\B\C柱子上可以移动的盘子中最大的盘子。2、如果上一次已经移动了某个盘子，则下一次不能继续移动，即：一个盘子不能被连续移动两次。如：某次操作将1号盘子由A柱子移动到B柱子，那么在选择下一个要移动的盘子时应不在考虑1号盘。3、当某个可以移动的盘子摆放位置不唯一时要将当前状态入栈，并选择盘子移动前所在的柱子的左侧（同理：反方向选择也可）柱子作为移动的目标柱子。为提高程序运行过程中的空间利用率，产生式规则在汉诺塔移动过程中依据以上规则自动生成。控制策略依据如下：1、根据以上产生式规则依据，在每次移动盘子时可选则产生式唯一，所以不需要考虑路径选择。2、当移动的是一组盘子中的最大盘子（即：在要移动的一组盘子中的最下面的盘子）时，观察目标柱子是否是C柱子（最终结果所在柱子），如果是则表示当前盘子移动成功，并清空栈，转移问题（即减小一层盘子）；如果移动目标错误（即移动到了A或B柱子）则执行回溯：栈顶状态出栈，向右选择目标柱子产生新的产生式规则，并按此执行移动操作。3、如果要移动的一组盘子中最大的是1号盘（最后一个盘子），执行的移动操作是将盘子移动到C柱子，则算法结束。 四、数据结构及算法说明：定义类hanno描述汉诺塔，定义窗体FORM作为前台显示窗口1、数据结构：主要属性及类型、作用如下：Const MAX = 200Public intLevel As Integer?????????????? 汉诺塔的层数Private intHnBeam(3, 9) As Integer?????? 汉诺塔的每个柱子的情况描述数组Private intMaxDisk As Integer??????????? 当前要移动的一组盘子中最大盘子的编号Private intMaxDiskTop(3, 2) As Integer?? 当前ABC柱上最上的盘子编号和所在下标(位置)Private intStackTop????? As Integer?????? 栈顶指针Private intStack(3, MAX) As Integer????? 栈：记录ABC柱上盘子情况，对应intHnBeam(3, 9)Private intStackPreDisk(MAX) As Integer 栈：记录前一移动的盘子, 对应intPreMovDisk Private intStackMaxDisk(MAX) As Integer 栈：记录当前要移动的最大盘子, 对应intMaxDiskPrivate intStackMaxDiskTop(3, MAX) As Integer 栈：记录各柱子顶端情况的栈,对应intMaxDiskTop(3, 2)Private intStackMov(MAX) As Integer????? 栈：记录当前要移动的盘子所在的柱子编号，对应movPrivate intPreMovDisk??? As Integer????? 前一个移动的盘子Private mov As Integer????????????????? 找出的满足条件的拟移动的盘子所在的柱子编号说明：intStack(3, MAX)栈为主要栈，用于记录三个柱子上的盘子情况。其他栈相当于在移动盘子过程中的状态记录栈，和intStack(3, MAX)栈一起使用（入栈、出栈、清空栈）2、算法：主要方法如下：* 初始化方法：Private Sub Class_Initialize()使用Public Property Let HanoLevel(ByVal vData As Integer) （汉诺塔层数属性赋值）代替，即初始化生成汉诺塔。?? 主要功能为：1) 设置参与的DISK层数2) 初始化ABC柱子3) 初始化A柱子4) 初始化当前要移