采用A算法解决八数码问题.doc

《采用A算法解决八数码问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.专业整理.人工智能实验一报告题目：采用A*算法解决八数码问题姓名：张博涵学号：081110317专业：信息与计算科学提交日期：2014-05-22.学习帮手..专业整理.目录1问题描述11.1待解决问题的解释11.2问题的搜索形式描述11.3解决方案介绍（原理）22算法介绍32.1A*搜索算法一般介绍32.2算法伪代码33算法实现43.1实验环境与问题规模43.2数据结构43.3实验结果53.4系统中间及最终输出结果54参考文献65附录—源代码及其注释6.学习帮手..专业整理.1问题描述所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8的八块正方形数码牌

2、任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是，在3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如下图1-1所示：初始状态中间状态目标状态图1-1八数码问题的求解过程1.1待解决问题的解释首先，八数码问题包括一个初始状态(START)和目标状态(END)，所谓解决八数码问题就是在两个状态间寻找一系列可过渡状态：（START>STAT

3、E1>STATE2>...>END）这个状态是否存在就是我们要解决的第一个问题：Q1：每一个状态及每一次操作的表示方法？有许多表示方法，比如一个3*3的八数码盘可以压缩成一个int值表示，但不适用于15puzzle或大于8的puzzle问题。如果对空间要求很高，应该还可以再压缩。本文采用一个int表示的方法。表示方法如下：由于int的表示范围大于1e9，所以我们取一个int的低9位，为了方便寻找空格的位置，int的个位我们用来放空格的位置（19）。而前8.学习帮手..专业整理.位，按照行从上到下，列从左到右的顺序依次记录对应位置上的数字。1.2问题的搜索形式描述八数码问

4、题形式化描述：初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字。把3×3的棋盘按从左到右，从上到下的顺序写成一个一维向量。我们可以设定初始状态：<1,5,2,4,0,3,6,7,8>后继函数：按照某种规则移动数字得到的新向量。例如：<1,5,2,4,0,3,6,7,8>®<1,0,2,4,5,3,6,7,8>目标测试：新向量是都是目标状态。即<1,2,3,4,5,6,7,8,0>是目标状态？路径耗散函数：每次移动代价为1，每执行一条规则后总代价加1。1.3解决方案介绍（原理）该问题是一个搜索问题。它是一种状态到另一种状态的变换。要解决这个问题，必须

5、先把问题转化为数字描述。由于八数码是一个3*3的矩阵，但在算法中不实用矩阵，而是将这个矩阵转化为一个一维数组，使用这个一维数组来表示八数码，但是移动时要遵守相关规则。(1)可用如下形式的规则来表示数字通过空格进行移动：→.学习帮手..专业整理.(2)共24条移动规则，对应与每个位置的移动规则。(3)搜索顺序举例：<1>优先移动行数小的棋子(数字)<2>同一行中优先移动列数大的棋子(4)约束规则：不使离开既定位置的数字数增加八数码的节点扩展应当遵循棋子的移动规则

6、。按规则，每一次可以将一个与空格相邻的棋子移动到空格中，实际上也可以看做空格的相反方向移动。空格的移动方向可以是上下左右，当然不能出边界。棋子的位置，也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化，在不移出边界的条件下，空格向右，下，左，上移动后，新位置是原位置分别加上1,3，-1，-3。在这里，空格可以用任意数字表示。操作本文用urdl分别表示空格的向上向右向下向左四个操作。图的搜索策略：经分析，8数码问题的搜索策略共有：1.广度优先搜索、2.深度优先搜索、3.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，等等。其中广度优先搜索法是可采纳的，有界

7、深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。本实验采用启发式A*搜索算法来实现。2算法介绍问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。.学习帮手..专业整理.启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提高了