人工智能A星算法

《人工智能A星算法》由会员分享，可在线阅读，更多相关《人工智能A星算法（9页珍藏版）》请在装配图网上搜索。

1、#include#include#include#includeusingnamespacestd;#defineM3classMatrixNodepublic:intm;intd;intp;intf;intplaceMM;intplacetrueMM;/intkong_x;intkong_y;/定义MatrixNode类/在位个数/深度/牌与其目标位置直接步数之和/f=d+p，估价函数/当前矩阵目标矩阵/空位的横坐标/空位的纵坐标public:MatrixNode();MatrixNodestart(MatrixNodeM_Matrix);intTruePlace(MatrixNodeT_p

2、lace);intp_place(MatrixNodeP_place);intf_kongx(MatrixNodefind_kongx);intf_kongy(MatrixNodefind_kongy);boolsolved(MatrixNodeM_Matrix);有解，否则无解MatrixNodeup_move(MatrixNodeM_Matrix);MatrixNodedown_move(MatrixNodeM_Matrix);MatrixNodeleft_move(MatrixNodeM_Matrix);MatrixNoderight_move(MatrixNodeM_Matrix);M

3、atrixNodeupdata_m(MatrixNodeM_Matrix);/初始矩阵/查找在位数/坐标差绝对值之和/找出空格的横坐标/找出空格的纵坐标/判断是否有解,奇偶性相同则/空格上移/空格下移/空格左移/空格右移/移动后更新状态MatrixNodeparents(dequeilist,MatrixNodeM_Matrix);该节点的父亲/找到;/=MatrixNode:MatrixNode()placetrue00=1;placetrue01=2;placetrue02=3;placetrue10=8;placetrue11=-1;placetrue12=4;/目标矩阵placetru

4、e20=7;placetrue21=6;placetrue22=5;/MatrixNodeMatrixNode:start(MatrixNodeM_Matrix)/初始矩阵cout请按如下格式输入初始矩阵(空位用0表示)：endl;cout123n456n708endl;cout八数码的初始状态如下:endl;for(inta=0;aM;a+)for(intb=0;bM_Matrix.placeab;M_Matrix.d=0;M_Matrix=M_Matrix.updata_m(M_Matrix);M_Matrix.d=M_Matrix.d-1;/初始更新时深度多加1，应该减去M_Matrix

5、.f=M_Matrix.f-1;returnM_Matrix;/boolsolved(MatrixNodeM_Matrix)/判断是否可解intnum8;inttarget8;inta=0;intb=0;for(intm=0;mM;m+)for(intn=0;nM;n+)if(M_Matrix.placemn!=0)/不考虑空格numa+=M_Matrix.placemn;if(M_Matrix.placetruemn!=-1)targetb+=M_Matrix.placetruemn;inti,j;intcount_num=0,count_target=0;for(i=0;i(8-1);i+

6、)for(j=i+1;j8;j+)if(numjnumi)count_num+;if(targetjtargeti)count_target+;0&count_target%20)|(count_num%2if(count_num%21&count_target%2=1)returntrue;elsereturnfalse;/查找在位数/intMatrixNode:TruePlace(MatrixNodeT_place)T_place.m=0;intNumT_place=0;for(inti=0;iM;i+)for(intj=0;jM;j+)if(T_place.placeij=placetr

7、ueij)T_place.m=T_place.m+1;NumT_place=NumT_place+1;returnNumT_place;/intMatrixNode:p_place(MatrixNodeP_place)/坐标差的绝对值之和P_place.p=0;intnum=0;for(intPa=0;PaM;Pa+)for(intPb=0;PbM;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)+ab

8、s(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_p

9、lace.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;returnnum;/intMatrixNode:f_kongx(MatrixNodefind_kongx)intnum;for(inti=0;iM;i+)for(intj=0;jM;j+)if(find_kongx.placeij=0)num=i;returnnum;/intMatrixNode:f_kongy(MatrixNodefind_kongy)intnum;for(inti

10、=0;iM;i+)for(intj=0;jM;j+)if(find_kongy.placeij=0)num=j;returnnum;/MatrixNodeMatrixNode:up_move(MatrixNodeM_Matrix)intnum;的中间变量/返回空格横坐标/返回空格纵坐标/空格上移/num为交换MatrixNodeup_m=M_Matrix;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.k

11、ong_x-1up_m.kong_y=num;up_m=up_m.updata_m(up_m);returnup_m;/MatrixNodeMatrixNode:down_move(MatrixNodeM_Matrix)/空格下移intnum;MatrixNodeup_m=M_Matrix;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;up_m=up_m.

12、updata_m(up_m);returnup_m;/MatrixNodeMatrixNode:left_move(MatrixNodeM_Matrix)/空格左移intnum;MatrixNodeup_m=M_Matrix;num=up_m.placeup_m.kong_xup_m.kong_y;up_m.placeup_m.kong_xup_m.kong_y=up_m.placeup_m.kong_xup_m.kong_y-1;up_m.placeup_m.kong_xup_m.kong_y-1=num;up_m=up_m.updata_m(up_m);returnup_m;/Matrix

13、NodeMatrixNode:right_move(MatrixNodeM_Matrix)/空格右移intnum;MatrixNodeup_m=M_Matrix;num=up_m.placeup_m.kong_xup_m.kong_y;up_m.placeup_m.kong_xup_m.kong_y=up_m.placeup_m.kong_xup_m.kong_y+1;up_m.placeup_m.kong_xup_m.kong_y+1=num;up_m=up_m.updata_m(up_m);returnup_m;/移动后更新状态/查找在位数/距离和/深度加1/估价值/找出空格的横坐/找出空

14、格的纵坐MatrixNodeMatrixNode:updata_m(MatrixNodeM_Matrix)MatrixNodeup_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+up_m.d;up_m.kong_x=up_m.f_kongx(up_m);标up_m.kong_y=up_m.f_kongy(up_m);标returnup_m;/boolfather(dequeilist,MatrixNodeM_Matrix)/寻找父节点Matri

15、xNodeM_Matrix1=ilist.front();MatrixNodeup_m;intm;up_m=M_Matrix1.up_move(M_Matrix1);m=0;for(inta1=0;a1M;a1+)for(intb1=0;b1M;b1+)if(up_m.placea1b1=M_Matrix.placea1b1)m+;if(m=9)returntrue;up_m=M_Matrix1.down_move(M_Matrix1);m=0;for(inta2=0;a2M;a2+)for(intb2=0;b2M;b2+)if(up_m.placea2b2=M_Matrix.placea2b

16、2)m+;if(m=9)returntrue;up_m=M_Matrix1.left_move(M_Matrix1);m=0;for(inta3=0;a3M;a3+)for(intb3=0;b3M;b3+)/输出矩阵/检查新生成的if(up_m.placea3b3=M_Matrix.placea3b3)m+;if(m=9)returntrue;up_m=M_Matrix1.right_move(M_Matrix1);m=0;for(inta4=0;a4M;a4+)for(intb4=0;b4M;b4+)if(up_m.placea4b4=M_Matrix.placea4b4)m+;if(m=9

17、)returntrue;elsereturnfalse;/voidprintMatrix(constMatrixNodeMatrix)for(inti=0;iM;i+)for(intj=0;jM;j+)coutMatrix.placeij,;coutendl;coutendl;/boolless_f(constMatrixNodeM_Matrix1,constMatrixNodeM_Matrix2)returnM_Matrix1.fM_Matrix2.f;/boollookout(dequeilist,MatrixNodeM_Matrix)节点是否已扩展deque:iteratorVi=ili

18、st.begin();inti,j,m;while(Vi!=ilist.end()m=0;for(i=0;iM;i+)for(j=0;jM;j+)if(*Vi).placeij=M_Matrix.placeij)m+;/不是新扩展的/是新扩展的if(m=9)returntrue;Vi+;returnfalse;/=voidmain()intstep=0;MatrixNodemat;MatrixNodemat_trn;MatrixNodemat_trn1;MatrixNodemat_trn2;MatrixNodemat_trn3;MatrixNodemat_trn4;MatrixNodepare

19、nt;mat=mat.start(mat);dequeopenlist;openlist.push_front(mat);dequeclosedlist;if(solved(mat)=false)cout无法找到路径!=1)mat_trn1=mat_trn1.up_move(mat_trn1);if(lookout(openlist,mat_trn1)=false&lookout(closedlist,mat_trn1)false)/检查新节点是否已扩展openlist.push_front(mat_trn1);/向下移mat_trn2=mat_trn;if(mat_trn2.f_kongx(

20、mat_trn2)=1)mat_trn3=mat_trn3.left_move(mat_trn3);if(lookout(openlist,mat_trn3)=false&false)/检查新节点是否已扩展openlist.push_front(mat_trn3);/向右移mat_trn4=mat_trn;if(mat_trn4.f_kongy(mat_trn4)=1)mat_trn4=mat_trn4.right_move(mat_trn4);if(lookout(openlist,mat_trn4)=false&false)/检查新节点是否已扩展openlist.push_front(ma

21、t_trn4);lookout(closedlist,mat_trn3)lookout(closedlist,mat_trn4)sort(openlist.begin(),openlist.end(),less_f);mat_trn=openlist.front();cout最优路径如下：endl;printMatrix(mat_trn);deque:iteratorVi=closedlist.begin();while(Vi!=(closedlist.end()-1)函数中用到首元素，所以不应该是不等于end/输出路径/由于我的fatherif(father(closedlist,mat_trn)=true)parent=closedlist.front();printMatrix(parent);mat_trn=parent;step=step+1;Vi+;closedlist.pop_front();printMatrix(mat);step+;cout走的步数:stependl;文档可自行编辑修改内容，此文档部分内容来源于网络，如有侵权请告知删除，供参考，感谢您的支持）