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

人工智能实验报告 题目：用A*搜索求解n数码问题姓名： 班级：学号：学院：计算机科学与信息专业：计算机科学与技术指导教师： 日期：2011年12月6日一、实验目的： 熟悉和掌握深度搜索，宽度搜索，启发式搜索的定义、估价函数和算法过程，并利用深度搜索，宽度搜索，A*算法求解8数码难题，理解求解流程和搜索顺序。二、实验原理： 1、A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。 2、深度优先搜索(breadth-first search)的定义：首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能小。 3、宽度优先搜索(breadth-first search)的定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search).三、实验内容：1 以8数码为例实际求解A*算法。2 画出A*算法求解框图。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的成员作为n的后继安装到图G中。把M的成员放到OPEN表中。（7）建立从M的没有在G中出现过的成员到n的指针。对M的已经在OPEN表或CLOSED表中的每个成员m，如果目前发现的到达m的最佳路径经过n，则把它的指针改为指向n。对M的每个已经在CLOSED表中的成员，修改它在图G中的所有子孙的指针，使得它们沿着目前发现的最好路径指向它们的祖先。（通过建立从儿子指向父亲的指针维护搜索树Tr）（8）按f值递增的顺序重排序OPEN表。（9）转步骤（3）。4.2 启发式搜索构造搜索树：局部搜索树：62 5 83 4 6 1 7 52 5 8 2 5 863 4 6 3 41 7 1 7 6462 5 8 2 5 83 4 6 3 6 1 7 1 3 732 8 2 5 8 2 5 8523 5 6 3 6 3 61 4 7 1 4 7 1 4 74.3 实验要求（1）分别实现固定数码排列和随机生成数码的排列两种情形（2）能正确演示A*算法搜索的步骤，指示每一步的数码排列状态（3）按照实验报告要求书写并上交实验报告4.4 实验环境VC+6.0Win7系统五、实验步骤：、 开始演示。进入N数码难题演示程序，可选8数码或者15数码，点击“选择数码”按钮确定。第一次启动后，点击两次“缺省”或者“随机”按钮，才会出现图片。、 点击“缺省棋局”，会产生一个固定的初始节点。点击“随机生成”，会产生任意排列的初始节点。、 算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单步运行”则每次执行一步求解流程。“运行速度”可自由调节。、 观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15数码难题”，点击“选择数码”确定选择；运行15数码难题演示实例。、 算法流程的任一时刻的相关状态,以算法流程高亮、open表、close表、节点静态图、当前扩展节点移动图等5种形式在按钮上方同步显示,便于深入学习理解A*算法。、 根据程序运行过程画出A*算法框图。六、实验结果：1、A*算法求8数码：2、 宽度求8数码 ： 3、深度求8数码七、实验总结：A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。通过本实验， 我熟悉和掌握了深度搜索，宽度搜索，启发式搜索的定义、估价函数和算法过程，并利用深度搜索，宽度搜索，A*算法求解了8数码难题，理解了求解流程和搜索顺序。实验过程中巩固了所学的知识，通过实验也提高了自己的编程和思维能力，收获很多。八、源程序代码：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*=h时才向下拓展/重复以前动作为非法操作23#include#include#include /异常处理class MatrixNodepublic: int w; /不在位 int h; /牌与其目标位置直接步数之和 int g; /已经走的步数 int m; /在位的数字个数 int p; /牌与其目标位置直接步数之和 int f; /h+g int place33; /当前矩阵 int placetrue33; /正确矩阵 int 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 printMatrix(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 right_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; placetrue10 = 8; placetrue11 = -1; placetrue12 = 4; placetrue20 = 7; placetrue21 = 6; placetrue22 = 5; for(int a = 0;a = 2;a+) /给矩阵赋值 for(int b = 0;b = 2;b+ ) placeab = 0; for(int ax = 0;ax = 2;ax+) /给零矩阵赋值 for(int by = 0;by = 2;by+ ) zeroplaceaxby = 0; for(int Pa = 0;Pa = 2;Pa+) /找出矩阵空格的横纵坐标 for(int Pb = 0;Pb = 2;Pb+) if(placePaPb = 0) kong_x = Pa; kong_y = Pb; g = 0; /步数gh = 0;f = h + g; /f值/-MatrixNode MatrixNode:fuzhi(MatrixNode M_Matrix) /给第一个矩阵赋值 for(int a = 0;a = 2;a+) /给矩阵赋值 for(int b = 0;b = 2;b+ ) cout请输入坐标为:(a,bM_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(MatrixNode 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 = T_place.placetrueTaTb) T_place.m = T_place.m + 1;NumT_place = NumT_place + 1; return NumT_place;/- int MatrixNode:N_TruePlace(MatrixNode N_place ) / 查找在不位数 int NumN_place = 0; N_place.w = 0; for(int Na = 0;Na = 2;Na+)for(int Nb = 0;Nb = 2;Nb+ )if( N_place.placeNaNb != N_place.placetrueNaNb) N_place.w = N_place.w + 1;NumN_place = NumN_place + 1; N_place.w = N_place.w - 1; / 空位也不在位，需要减去 NumN_place = NumN_place - 1; return NumN_place; /- int MatrixNode:p_place(MatrixNode P_place) /牌与其目标位置直接步数之和(坐标差之和为距离) P_place.p = 0; int num = 0; for(int Pa = 0;Pa = 2;Pa+) for(int Pb = 0;Pb = 2;Pb+) /for(int Pc = 1;Pc = 8;Pc+) if(P_place.placePaPb = 1) P_place.p = P_place.p+ (abs(Pa - 0)+abs(Pb - 0); if(P_place.placePaPb = 2) P_place.p = P_place.p+ (abs(Pa - 0)+abs(Pb - 1); if(P_place.placePaPb = 3) P_place.p = P_place.p+ (abs(Pa - 0)+abs(Pb - 2); if(P_place.placePaPb = 4) P_place.p = P_place.p+ (abs(Pa - 1)+abs(Pb - 2); if(P_place.placePaPb = 5) P_place.p = P_place.p+ (abs(Pa - 2)+abs(Pb - 2); if(P_place.placePaPb = 6) P_place.p = P_place.p+ (abs(Pa - 2)+abs(Pb - 1); if(P_place.placePaPb = 7) P_place.p = P_place.p+ (abs(Pa - 2)+abs(Pb - 0); if(P_place.placePaPb = 8) P_place.p = P_place.p+ (abs(Pa - 1)+abs(Pb - 0); num = P_place.p; return num; /- int MatrixNode:f_kongx(MatrixNode find_kongx) /返回空格横坐标 int num = 0; for(int Pa = 0;Pa = 2;Pa+) for(int Pb = 0;Pb = 2;Pb+) if(find_kongx.placePaPb = 0) num = Pa; return num; /- int MatrixNode:f_kongy(MatrixNode find_kongy) /返回空格纵坐标 int num = 0; for(int Pa = 0;Pa = 2;Pa+) for(int Pb = 0;Pb = 2;Pb+) if(find_kongy.placePaPb = 0) num = Pb; return num; /- MatrixNode MatrixNode:updata_m(MatrixNode M_Matrix) /移动后更新状态 MatrixNode up_m = M_Matrix; up_m.m = up_m.TruePlace(up_m); / 查找在位数 up_m.w = up_m.N_TruePlace(up_m); / 查找不在位数 up_m.p = up_m.p_place(up_m); /距离和 up_m.kong_x = up_m.f_kongx(up_m); /找出空位的x坐标 up_m.kong_y = up_m.f_kongy(up_m); /找出空位的y坐标 up_m.h = up_m.p; up_m.g = up_m.g + 1; /步数 up_m.f = up_m.h + up_m.g; /f值 return up_m; /- MatrixNode MatrixNode:up_move(MatrixNode M_Matrix) /空格向上移动一格 int x = 0; int num = 0; MatrixNode up_m = M_Matrix; MatrixNode updata_m = M_Matrix; x = M_Matrix.kong_x - 1; if(x 0) for(int xx = 0;xx = 2;xx+) for(int yy = 0;yy 2) for(int xx = 0;xx = 2;xx+) for(int yy = 0;yy = 2;yy+) up_m.placexxyy = 0; return up_m; num = up_m.placeup_m.kong_xup_m.kong_y; up_m.placeup_m.kong_xup_m.kong_y = up_m.placeup_m.kong_x + 1up_m.kong_y ; up_m.placeup_m.kong_x + 1up_m.kong_y = num; updata_m = MatrixNode:updata_m(up_m); return updata_m; /- MatrixNode MatrixNode:left_move(MatrixNode M_Matrix) /空格向左移动一格 int y = 0; int num = 0; MatrixNode up_m = M_Matrix; MatrixNode updata_m = M_Matrix; y = M_Matrix.kong_y - 1; if(y 0) for(int xx = 0;xx = 2;xx+) for(int yy = 0;yy 2 ) for(int xx = 0;xx = 2;xx+) for(int yy = 0;yy = 2;yy+) up_m.placexxyy = 0; return up_m; num = up_m.placeup_m.kong_xup_m.kong_y; up_m.placeup_m.kong_xup_m.kong_y = up_m.placeup_m.kong_x up_m.kong_y + 1 ; up_m.placeup_m.kong_x up_m.kong_y + 1 = num; updata_m = MatrixNode:updata_m(up_m); return updata_m; /-/- void MatrixNode:printMatrix(const int Pri_Matrix3 ) /输出矩阵 for(int a = 0;a = 2;a+) for(int b = 0;b = 2;b+ ) coutPri_Matrixab; cout , ; coutendl; coutlink; delete front; front = next;/-void Queue:add(MatrixNode Matrix) /入队 Node *p = new Node; p-data = Matrix; p-link = NULL; if(front = NULL) front = p; rear = p; else rear-link = p; rear = p; num = num + 1;/-MatrixNode Queue:putout() /出队MatrixNode mat;Node *next;if(num = 0) /若队空则报错 cout无法出队data;next = front-link;delete front;front = next;num = num -1;return mat; /-bool Queue:lookover(MatrixNode Matrix) /查看是否有相同项 Node *next; next = front; while(next != NULL) / mat_jug(MatrixNode M_Matrix1,MatrixNode M_Matrix2) if(Matrix.mat_jug(Matrix,next-data) = true) return true; next = next-link; return false;/=/=void main() MatrixNode mat1; int h0;/储存线性耗散值 MatrixNode mat_trn; Queue Q1;/未拓展但需拓展的矩阵类 Queue Q2;/拓展过的节点 Queue Q3;/储存路径 Node *next1; Node *next2; mat1 = mat1.fuzhi(mat1); h0 = mat1.h; Q1.add(mat1); next1 = Q1.front; Q2.add(mat1); Q3.add(mat1); while(Q1.num != 0) /-向上移 mat_trn = Q1.front-data; mat_trn = mat_trn.up_move(mat_trn); if(mat_trn.PlaceAndZero(mat_trn) = false) if(Q2.lookover(mat_trn) = false) Q2.add(mat_trn); if(mat_trn.PlaceAndZero(mat_trn) = false) if(mat_trn.h = h0) if(Q1.lookover(mat_trn) = false)if(mat_trn.h data.m = 8) break; /若全在位则跳出循环 /-向下移 mat_trn = Q1.front-data; mat_trn = mat_trn.down_move(mat_trn); if(mat_trn.PlaceAndZero(mat_trn) = false) if(Q2.lookover(mat_trn) = false) Q2.add(mat_trn); if(mat_trn.PlaceAndZero(mat_trn) = false) if(mat_trn.h = h0) if(Q1.lookover(mat_trn) = false) if(mat_trn.h data.m = 8) break; /-向左移 mat_trn = Q1.front-data; mat_trn = mat_trn.left_move(mat_trn); if(mat_trn.PlaceAndZero(mat_trn) = false) if(Q2.lookover(mat_trn) = false) Q2.add(mat_trn); if(mat_trn.PlaceAndZero(mat_trn) = false) if(mat_trn.h = h0) if(Q1.lookover(mat_trn) = false) if(mat_trn.h data.m = 8) break; /-向右移 mat_trn = Q1.front-data; mat_trn = mat_trn.right_move(mat_trn); if(mat_trn.PlaceAndZero(mat_trn) = false) if(Q2.lookover(mat_trn) = false) Q