人工智能实验一 产生式系统解汉诺塔问题

< 人工智能 > 实 验 报 告 1

一、实验目的：

掌握产生式系统解决汉诺塔算法的基本思想。

二、问题描述：

如图所示放置3根柱子，其中一根从上往下按由小到大顺序串有若干个圆盘，要求通过3根柱子移动圆盘。若规定每次只能移动1片，且不许大盘放在小盘之上，最后要将圆盘从一根柱子移动到另一根柱子上。

三、问题分析及基本思想：

汉诺塔(也被称为梵塔)问题有很多解决方法，比较典型的是使用递归算法，而本次设计的算法则是应用人工智能中产生式相关知识进行的求解。数学模型描述如下：

1、设计该问题的状态。使用了二维数组描述汉诺塔的状态，对n个盘子由大到小分别用数组n、n-1...2、1描述。例如：当n＝4时，二维数组为：

100

200

300

400

2、定义目标状态。当n＝4时，这里是：

001

002

003

004

依据如下规则定义产生式规则：

1、在移动盘子时，每次只移动A\B\C柱子上可以移动的盘子中最大的盘子。

2、如果上一次已经移动了某个盘子，则下一次不能继续移动，即：一个盘子不能被连续移动两次。如：某次操作将1号盘子由A柱子移动到B柱子，那么在选择下一个要移动的盘子时应不在考虑1号盘。

3、当某个可以移动的盘子摆放位置不唯一时要将当前状态入栈，并选择盘子移动前所在的柱子的左侧（同理：反方向选择也可）柱子作为移动的目标柱子。 为提高程序运行过程中的空间利用率，产生式规则在汉诺塔移动过程中依据以上规则自动生成。

控制策略依据如下：

1、根据以上产生式规则依据，在每次移动盘子时可选则产生式唯一，所以不需要考虑路径选择。

2、当移动的是一组盘子中的最大盘子（即：在要移动的一组盘子中的最下面的盘子）时，观察目标柱子是否是C柱子（最终结果所在柱子），如果是则表示当前盘子移动成功，并清空栈，转移问题（即减小一层盘子）；如果移动目标错误（即移动到了A或B柱子）则执行回溯：栈顶状态出栈，向右选择目标柱子产生新的产生式规则，并按此执行移动操作。

3、如果要移动的一组盘子中最大的是1号盘（最后一个盘子），执行的移动操作是将盘子移动到C柱子，则算法结束。

四、数据结构及算法说明：

定义类hanno描述汉诺塔，定义窗体FORM作为前台显示窗口

1、数据结构：

主要属性及类型、作用如下：

Const MAX = 200

Public 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 '栈：记录当前要移动的最大盘子, 对应intMaxDisk

Private intStackMaxDiskTop(3, MAX) As Integer '栈：记录各柱子顶端情况的栈,对应

intMaxDiskTop(3, 2)

Private intStackMov(MAX) As Integer '栈：记录当前要移动的盘子所在

的柱子编号，对应mov

Private 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) 初始化当前要移动的最大盘子的编号

5) 初始化当前ABC柱子上最上面的盘子的编号和所在下标(位置)

6) 初始化栈顶指针

7) 初始化前一个移动盘

* 清空栈方法：Private Sub ClearStack()

* 入栈方法：Private Sub PushStack()

* 出栈方法：Private Sub PopStack()

* 开始移动方法：Public Sub MovDisk()

主要功能为：如下流程图： （汉诺塔层

五、运行例（4层汉诺塔移动过程演示）：

六、算法分析及评价：

1、对本问题如果在产生式规则的制定原则中加入对移动目标选择规则，则可以避免回溯。如现在有1-2-3三个盘子在A柱子，则可以确定：3号盘目标柱子是C, 2号盘目标柱子是B, 1号盘目标柱子是C,在第一次移动1好盘时目标柱子已确定，即避免了移动方向的选择。本次设计由于希望较好的演示产生式系统应用中带有回溯的推理过程，故未采用本原则。

2、和本问题的经典的递归方式解决方法相比，由于在移动盘子过程中故意设计了错误路径故本算法时间复杂度将劣于递归方式。

3、和本问题的经典的递归方式解决方法相比，由于在移动盘子过程中有选择的入栈故本算法的空间复杂度将大大优于递归方式。

4、本设计控 …… 此处隐藏：461字，全部文档内容请下载后查看。喜欢就下载吧 ……