人工智能实验 A搜索n数码.doc

1、人工智能实验报告题目：用 A*搜索求解 n 数码问题姓名： 班级：学号：学院：计算机科学与信息专业：计算机科学与技术指导教师： 日期：2011 年 12 月 6 日2一、实验目的：熟悉和掌握深度搜索，宽度搜索，启发式搜索的定义、估价函数和算法过程，并利用深度搜索，宽度搜索，A*算法求解 8 数码难题，理解求解流程和搜索顺序。二、实验原理：1、A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择 f 值最小的节点作为扩展节点。因此， f 是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点 n 的估价函数值为两个分量：从起始节点到节点 n 的代

2、价以及从节点 n 到达目标节点的代价。2、深度优先搜索(breadth-first search)的定义：首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后 n 步，而且保持 n 尽可能小。3、宽度优先搜索(breadth-first search)的定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search).三、实验内容：1 以 8 数码为例实际求解 A*算法。2 画出 A*算法

3、求解框图。3 分析估价函数对搜索算法的影响。4 分析 A*算法的特点。5 宽度求 8 数码6 深度求 8 数码四、实验描述及要求：4.1 维护搜索图的 A*算法（1）创建一个搜索图 G，只包含开始节点 n0。把 n0放到 OPEN 表中。（2）创建 CLOSED 表：初始为空。（3）如果 OPEN 表空，算法以失败退出。（4）选 OPEN 表中的首节点，从 OPEN 表中移走，放到 CLOSED 表中。称该节点为n。（5）如果 n 是目标节点，算法以成功退出：通过跟踪沿着图 G 中从 n 指向 n0 的指针获得解。（6）扩展节点 n，产生后继集合 M，M 不包含图 G 中 n 的祖先。把 M

4、的成员作为 n的后继安装到图 G 中。把 M 的成员放到 OPEN 表中。（7）建立从 M 的没有在 G 中出现过的成员到 n 的指针。对 M 的已经在 OPEN 表或CLOSED 表中的每个成员 m，如果目前发现的到达 m 的最佳路径经过 n，则把它的指针改为指向 n。对 M 的每个已经在 CLOSED 表中的成员，修改它在图 G 中的所有子孙的指针，使得它们沿着目前发现的最好路径指向它们的祖先。 （通过建立从儿子指向父亲的指针维护搜索树 Tr）3（8）按 f值递增的顺序重排序 OPEN 表。（9）转步骤（3） 。4.2 启发式搜索构造搜索树：局部搜索树：2 5 83 4 61 7 2 5

5、8 2 5 83 4 6 3 41 7 1 7 62 5 8 2 5 83 4 6 3 61 7 1 3 72 8 2 5 8 2 5 83 5 6 3 6 3 61 4 7 1 4 7 1 4 74.3 实验要求（1）分别实现固定数码排列和随机生成数码的排列两种情形（2）能正确演示 A*算法搜索的步骤，指示每一步的数码排列状态（3）按照实验报告要求书写并上交实验报告4.4 实验环境VC+6.0Win7 系统635245664五、实验步骤：、开始演示。进入 N 数码难题演示程序，可选 8 数码或者 15 数码，点击“选择数码”按钮确定。第一次启动后，点击两次“缺省”或者“随机”按钮，才会出现图

6、片。、点击“缺省棋局” ，会产生一个固定的初始节点。点击“随机生成” ，会产生任意排列的初始节点。、算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单步运行”则每次执行一步求解流程。 “运行速度”可自由调节。、观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15 数码难题” ，点击“选择数码”确定选择；运行 15 数码难题演示实例。、算法流程的任一时刻的相关状态,以算法流程高亮、open 表、close 表、节点静态图、当前扩展节点移动图等 5 种形式在按钮上方同步显示,便于深入学习理解 A*算法。、根据程序运行过程画出 A*算法框图。六、实验结果：1、

7、A*算法求 8 数码：562、宽度求 8 数码 ： 73、深度求 8 数码8七、实验总结：A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择 f 值最小的节点作为扩展节点。因此，f 是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点 n 的估价函数值为两个分量：从起始节点到节点n 的代价以及从节点 n 到达目标节点的代价。通过本实验， 我熟悉和掌握了深度搜索，宽度搜索，启发式搜索的定义、估价函数和算法过程，并利用深度搜索，宽度搜索，A* 算法求解了 8 数码难题，理解了求解流程和搜索顺序。实验过程中巩固了所学的知识，通过实验也提高了自己的

8、编程和思维能力，收获很多。9八、源程序代码：1、A*算法/用 A*算法实现八数码问题/ 如：2 8 3 1 2 3 /0-2 行，0-2 列/ 1 6 4 -8 4/ 7 5 7 6 5/A*算法，即设 h 为在位的数字个数，只有当 h*#include#include /异常处理class MatrixNodepublic: int w; /不在位int h; /牌与其目标位置直接步数之和int g; /已经走的步数int m; /在位的数字个数int p; /牌与其目标位置直接步数之和int f; /h+gint place33; /当前矩阵int placetrue33; /正确矩阵in

9、t zeroplace33; /全 0 矩阵，移动时若为全零矩阵则移动无效int kong_x; /空位的横坐标int kong_y; /空位的纵坐标/-public:MatrixNode();MatrixNode fuzhi(MatrixNode M_Matrix); /给第一个矩阵赋值；int TruePlace(MatrixNode T_place ); / 查找在位数int N_TruePlace(MatrixNode N_place ); / 查找在不位数int p_place(MatrixNode P_place); /牌与其目标位置直接步数之和( 坐标差之和为距离)void pr

10、intMatrix(const int Pri_Matrix3 );/输出矩阵int f_kongx(MatrixNode find_kongx); /找出空位的 x 坐标int f_kongy(MatrixNode find_kongy); /找出空位的 y 坐标MatrixNode up_move(MatrixNode M_Matrix); /空格向上移动一格MatrixNode down_move(MatrixNode M_Matrix); /空格向下移动一格MatrixNode left_move(MatrixNode M_Matrix); /空格向左移动一格MatrixNode ri

11、ght_move(MatrixNode M_Matrix); /空格向右移动一格MatrixNode updata_m(MatrixNode M_Matrix); /移动后更新状态bool PlaceAndZero(MatrixNode M_Matrix);/判断矩阵是否为零矩阵bool mat_jug(MatrixNode M_Matrix1,MatrixNode M_Matrix2); /判断节点中的矩阵是否相同;/=MatrixNode:MatrixNode() /构造函数placetrue00 = 1; /标准矩阵placetrue01 = 2;placetrue02 = 3;plac

12、etrue10 = 8;placetrue11 = -1;placetrue12 = 4;placetrue20 = 7;placetrue21 = 6;placetrue22 = 5;10for(int a = 0;a M_Matrix.placeab;coutendl;M_Matrix = M_Matrix.updata_m( M_Matrix);M_Matrix.f = M_Matrix.f - 1;/ 更新状态时步数加一多余，故减去M_Matrix.g = M_Matrix.g - 1;return M_Matrix;/-bool MatrixNode:PlaceAndZero(Mat

13、rixNode M_Matrix) /判断矩阵是否为零矩阵for(int a = 0;a = 2;a+) /给矩阵赋值for(int b = 0;b = 2;b+ )if(M_Matrix.placeab != 0 ) return false; return true;/-bool MatrixNode:mat_jug(MatrixNode M_Matrix1,MatrixNode M_Matrix2) /判断节点中的矩阵是否相同for(int a = 0;a = 2;a+) /给矩阵赋值for(int b = 0;b = 2;b+ )if(M_Matrix1.placeab != M_Matrix2.placeab ) return false; return true;/-int MatrixNode:TruePlace(MatrixNode T_place ) / 查找在位数T_place.m = 0;int NumT_place = 0;for(int Ta = 0;Ta = 2;Ta+)for(int Tb = 0;Tb = 2;Tb+ )if( T_place.placeTaTb =