人工智能实验报告

《人工智能实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.人工智能九宫格重移——搜索成员：赵春杰2009210665羊森2009210653黄鑫2009210周成兵2009210664王素娟2009210644...1.问题描述：八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状

2、态。2.九宫重移有无答案检查（逆序数）我们把每个9宫格横向展开，如第一个123456789，我们把左边数大于右边数的组数称为这个九宫格的逆序数，显然123456789的逆序数为0；考虑横向平移，那么逆序数的增量为2或0或-2；纵向平移，逆序数的增量为4或0或-4；但147258369的逆序数为奇数。所以147258369是无解的情况。由此也可以类推当将9宫格展开后，如果数据序列的逆序数为奇数，则此数据序列对应的九宫格是无解的。3.BFS算法队列：Queueopen=newQueue();存放待扩展的节点List：Listclosed=newList();存放已被

3、扩展过的节点ArrayListmap=newArrayList();//存放答案HashTale：Hashtabletable=newHashtable();构造哈希表以方便查找...3.1．BFS算法介绍广度优先搜索算法BFS基本思想：从图中某顶点v出发，逐层对节点进行拓展，并考察是否为目标节点，在第n层节点没有全部扩展并考察前，不对第n+1层节点进行扩展。对九宫重排问题，即构造广度优先搜索树，从初始状态，利用广度优先搜索算法逐步找到目标状态的节点。3.2．状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开始从左往右给九宫格标号0……8，字符串

4、now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。3.3．搜索树2831647512831647528314765283164752342836417523184765283167542831476528314765567893.4．算法步骤搜索：（1）把初始节点S0放入OPEN表。（2）如果OPEN表为空，则问题无解，退出。（3）把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。...（4）考察节点n是否为目标节点。若是，则求得了问题的解，退出。（5）若节点n不可扩展，则转第2步。（6）扩展节点n，将其子节点放入OPEN表的尾部，并

5、为每一个子节点都配置指向父节点的指针，然后转第2步。扩展fun()：（1）取open中第一个节点a加入到closed中（2）找到a[9]中值为9（空格）的位置i；（3）当open中元素个数不为0时，循环执行（3）到（）3.1从open中取出一个元素（状态），并加入到closed中，对这个状态扩展；3.2若空格在第2、3列,向左移动得到新状态；新状态不是目标状态，就加入open中；新状态是目标状态，就加入closed中，编号加1，结束算法；3.3若空格在第2、3行,向上移动得到新状态新状态不是目标状态，就加入open中，新状态是目标状态，就加入closed中，编号加1，结束算法；3.4若空格

6、在第1、2列,向右移动得到新状态新状态不是目标状态，就加入open中，新状态是目标状态，就加入closed中，编号加1，结束算法；3.5若空格在第1行,向下移动得到新状态新状态不是目标状态，就加入open中，新状态是目标状态，就加入closed中，编号加1，结束算法；...3.5．算法流程图输入初始状态SS和目标状态NN开始open空?YNn=0,初始节点送入open队列搜索失败，算法结束，从open中取出节点到closed中并编号加1扩展编号为n的节点，加入open中closed中是否有目标节点Y算法结束是否还有后续节点NNY...4.启发式A*算法队列：Queueopen=newQue

7、ue();存放待扩展的节点List：Listclosed=newList();存放已被扩展过的节点ArrayListmap=newArrayList();//存放答案HashTale：Hashtabletable=newHashtable();构造哈希表以方便查找sort排序4.1．算法介绍算法A不能保证当图中存在从起始节点到目标节点的最短路径时，一定能找到它，而A*中评估函数f*(n)=g*