《人工智能A星算法(C++).doc》由会员分享，可在线阅读，更多相关《人工智能A星算法(C++).doc（11页珍藏版）》请在三一文库上搜索。
1、#in clude<iostream> #in clude<deque> #i nclude<algorithm> #in clude<iterator> using n amespace std; #defi ne M 3class MatrixNode/ 定义 MatrixNode 类public:int m;/在位个数int d;/深度in t p;/牌与其目标位置直接步数之和int f;/f=d+p，估价函数in t placeMM;/当前矩阵in t placetrueMM; /目标矩阵int kon g_x;/空位的横坐标/int k
2、on g_y;/空位的纵坐标/public:MatrixNode();MatrixNode start(MatrixNode M_Matrix);/初始矩阵int TruePlace(MatrixNode T_place );/查找在位数int p_place(MatrixNode P_place);/坐标差绝对值之和in t f_kon gx(MatrixNode fin d_kon gx);/找出空格的横坐标int f_kongy(MatrixNode find_kongy);/找出空格的纵坐标bool solved(MatrixNode M_Matrix);/判断是否有解，奇偶性相同则有
3、解，否则无解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);/移动后更新状态MatrixNode parents(deque<MatrixNode> ilist,MatrixNod
4、e M_Matrix);/ 找到该节点的父亲;/MatrixNode:MatrixNode()/ 目标矩阵placetrueOO = 1;placetrue01 = 2;placetrue02 = 3;placetrue10 = 8;placetrue11 = -1;placetrue12 = 4;placetrue20 = 7;placetrue21 = 6;placetrue22 = 5;/MatrixNode MatrixNode:start(MatrixNode M_Matrix)/ 初始矩阵cout<<"请按如下格式输入初始矩阵(空位用0表示)："&l
5、t;<endl;cout<<"1 2 3n4 5 6n7 0 8"<<endl;cout<<"八数码的初始状态如下:"<< endl;for(int a = 0;a < M;a+)for(i nt b = 0;b < M;b+ )cin >>M_Matrix.placeab;M_Matrix.d = 0;M_Matrix = M_Matrix.updata_m( M_Matrix );M_Matrix.d=M_Matrix.d-1;/初始更新时深度多加1，应该减去M_Matri
6、x.f=M_Matrix.f-1;return M_Matrix;/bool solved(MatrixNode M_Matrix)/ 判断是否可解int num8;int target8;int a=0;int b=0;for(int m = 0;m < M;m+)for(i nt n = 0;n < M; n+ )if(M_Matrix.placem n != 0)/ 不考虑空格nu ma+=M_Matrix.placem n;if(M_Matrix.placetruemn != -1) targetb+=M_Matrix.placetruem n;int i,j;int co
7、unt_num = 0,co un t_target = 0;for (i = 0;i < (8-1);i+)for (j = i+1;j < 8;j+)if(nu mj < nu mi)count_nu m+;if(targetj<targeti)coun t_target+;if(cou nt_nu m%21&&cou nt_target%2 = 1) return true;else0&&cou nt_target%20)|(cou nt_n um%2return false;/int MatrixNode:TruePlace(Ma
8、trixNode T_place ) T_place.m = 0;int NumT_place = 0;/查找在位数for(int i = 0;i < M;i+) for(i nt j = 0;j < M;j+ )if( T_place.placeij = placetrueij) T_place.m = T_place.m + 1; NumT_place = NumT_place + 1; return NumT_place;/int MatrixNode:p_place(MatrixNode P_place)之和/坐标差的绝对值P_place.p = 0;int num = 0
9、;for(int Pa = 0;Pa < M;Pa+)for(i nt Pb = O;Pb < M;Pb+)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.placePa
10、Pb = 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);/返回空格横坐标/返回空格纵坐标/空格上移/num 为交换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
11、- 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;for(int i = 0;i < M;i+)for(i nt j = 0;j < M;j+)if(find_kon gx.placeij = 0)num = i; return num;/int MatrixNode:f_kongy(MatrixNode fin
12、d_kongy)int num;for(int i = 0;i < M;i+)for(i nt j = 0;j < M;j+)if(fin d_ko ngy.placeij = 0)num = j; return num;/MatrixNode MatrixNode:up_move(MatrixNode M_Matrix) int num;的中间变量MatrixNode up_m = M_Matri x;num = up_m.placeup_m.k on g_xup_m.k on g_y;up_m.placeup_m.k on g_xup_m.k on g_y= up_m.plac
13、eup_m.k ong_x -1up_m.ko ng_y ；up_m.placeup_m.k ong_x - 1up_m.k ong_y = num;up_m = up_m.updata_m(up_m);return up_m;/MatrixNode MatrixNode:down_move(MatrixNode M_Matrix)/ 空格下移int num;MatrixNode up_m = M_Matrix;num = up_m.placeup_m.k on g_xup_m.k on g_y;up_m.placeup_m.k on g_xup_m.k on g_y=up_m.placeup
14、_m.k ong_x+1up_m.ko ng_y ;up_m.placeup_m.k ong_x + 1up_m.k ong_y = num;up_m = up_m.updata_m(up_m);return up_m;/MatrixNode MatrixNode:left_move(MatrixNode M_Matrix)/ 空格左移int num;MatrixNode up_m = M_Matrix;num = up_m.placeup_m.k on g_xup_m.k on g_y;up_m.placeup_m.k on g_xup_m.k on g_y=up_m.placeup_m.k
15、 ong_x up_m.k ong_y - 1 ;up_m.placeup_m.k ong_x up_m.k ong_y - 1 = num;up_m = up_m.updata_m(up_m);return up_m;/MatrixNode MatrixNode:right_move(MatrixNode M_Matrix)/ 空格右移int num;MatrixNode up_m = M_Matrix;num = up_m.placeup_m.k on g_xup_m.k on g_y;up_m.placeup_m.k on g_xup_m.k on g_y=up_m.placeup_m.
16、k ong_x up_m.k ong_y + 1 ;up_m.placeup_m.k ong_x up_m.k ong_y + 1 = num;up_m = up_m.updata_m(up_m); return up_m;/MatrixNode MatrixNode:updata_m(MatrixNode M_Matrix) MatrixNode up_m = M_Matrix;/移动后更新状态/up_m.m = up_m.TruePlace(up_m);up_m.p = up_m.p_place(up_m);up_m.d = M_Matrix.d+1;up_m.f = up_m.p + u
17、p_m.d;up_m.k ong_x = up_m.f_k on gx(up_m);up_m.k ong_y = up_m.f_k on gy(up_m);return up_m;/查找在位数/距离和/深度加1/估价值/找出空格的横坐/找出空格的纵坐bool father(deque<MatrixNode> ilist,MatrixNode M_Matrix) / 寻找父节点MatrixNode M_Matrix1 = ilist.fro nt();MatrixNode up_m;int m;up_m = M_Matrix1.up_move(M_Matrix1);m = 0;for
18、(i nt a1 = 0;a1 < M;a1+)for(i nt b1 = 0;b1 < M;b1+ )if(up_m.placea1b1 = M_Matrix.placea1b1)m+;if(m = 9)return true;up_m=M_Matrix1.down_move(M_Matrix1);m = 0;for(i nt a2 = 0;a2 < M;a2+)for(i nt b2 = 0;b2 < M;b2+ )if(up_m.placea2b2 = M_Matrix.placea2b2)m+;if(m = 9)return true;up_m=M_Matrix
19、1.left_move(M_Matrix1);m = 0;for(int a3 = 0;a3 < M;a3+)for(i nt b3 = 0;b3 < M;b3+ )II输出矩阵/检查新生成的if(up_m.placea3b3 = M_Matrix.placea3b3) m+;if(m = 9)return true;up_m=M_Matrix1.right_move(M_Matrix1);m = 0;for(i nt a4 = 0;a4 < M;a4+)for(i nt b4 = 0;b4 < M;b4+ )if(up_m.placea4b4 = M_Matrix.p
20、lacea4b4) m+;if(m = 9)return true;elsereturn false;/void prin tMatrix(c onst MatrixNode Matrix)for(int i = 0;i < M;i+)for(i nt j = 0;j < M;j+ )cout<<Matrix.placeij<<","cout<<e ndl;cout<<e ndl;/bool less_f(co nst MatrixNode M_Matrix1, const MatrixNode M_Matrix2
21、) return M_Matrix1.f < M_Matrix2.f;/bool lookout(deque<MatrixNode> ilist, MatrixNode M_Matrix)节点是否已扩展deque<MatrixNode>:iterator Vi = ilist.begi n();int i,j,m;while(Vi != ilist.e nd()m=0;for(i = 0;i < M;i+)for(j = 0;j < M;j+ )if(*Vi).placeij = M_Matrix.placeij)m+;if(m = 9)return
22、true;II不是新扩展的Vi+;return false;II是新扩展的IIvoid mai n()int step = 0;MatrixNode mat;MatrixNode mat_trn;MatrixNode mat_trn1;MatrixNode mat_trn2;MatrixNode mat_trn3;MatrixNode mat_trn4;MatrixNode pare nt;mat = mat.start(mat);deque<MatrixNode> ope nlist;ope nlist.push_fr on t(mat);deque<MatrixNode&
23、gt; closedlist;if(solved(mat) = false)cout<<"无法找到路径!"<<endl;return;mat_trn=openlist.front();/ 访问第一个元素while(mat_trn.m != 8)closedlist.push_fro nt(mat_tr n);openlist.pop_front();/ 删除第一个元素II向上移mat_trn1 = mat_trn;if(mat_tr n1.f_k on gx(mat_tr n1) >= 1)mat_trn1 = mat_trn1.up_move
24、(mat_trn1);if(lookout(ope nlist,mat_tr n1)= false &&lookout(closedlist,mat_tr n1)false)II检查新节点是否已扩展ope nlist.push_fr on t(mat_tr n1);II向下移mat_trn2 = mat_trn;if(mat_trn2.f_kongx(mat_trn2) <= 1)mat_tr n2 = mat_tr n2.dow n_mo ve(mat_tr n2);if(lookout(ope nlist,mat_tr n2)false && Iook
25、out(closedlist,mat_trn2)false)/检查新节点是否已扩展ope nlist.push_fr on t(mat_tr n2);/向左移mat_trn3 =mat_trn;if(mat_trn3.f_ko ngy(mat_trn3) >= 1) mat_trn3 = mat_trn3.left_move(mat_trn3);if(lookout(ope nlist,mat_tr n3)=false &&false)/检查新节点是否已扩展ope nlist.push_fr on t(mat_tr n3);II向右移mat_trn4 = mat_trn;
26、if(mat_tr n4.f_kon gy(mat_tr n4) <= 1)mat_trn4 = mat_trn4.right_move(mat_trn4);if(lookout(ope nlist,mat_tr n4)=false &&false)II检查新节点是否已扩展ope nlist.push_fr on t(mat_tr n4);sort(ope nlist.begi n() ,ope nlist.e nd(),less_f); mat_trn=ope nlist.fr on t();cout<<"最优路径如下："<<
27、e ndl;prin tMatrix(mat_trn);deque<MatrixNode>:iterator Vi = closedlist.begi n(); while(Vi != (closedlist.e nd()-1)函数中用到首元素，所以不应该是不等于endif(father(closedlist,mat_tr n) = true)pare nt = closedlist.fr on t();prin tMatrix(pare nt);mat_tr n = pare nt;step = step+1;Vi+;closedlist.pop_fr on t();prin tMatrix(mat);step+;lookout(closedlist,mat_tr n3)lookout(closedlist,mat_tr n4)II输出路径II由于我的fathercout<<"走的步数:"<<step<<endl;