人工智能A星算法(C++)

1、#include<iostream>#include<deque>#include<algorithm>#include<iterator>usingnamespacestd;#defineM3classMatrixNode/public:intm;/intd;/intp;/intf;/f=d+pintplaceMM;/intplacetrueMM;/intkong_x;/intkong_y;/定义MatrixNode类在位个数深度牌与其目标位置直接步数之和，估价函数当前矩阵目标矩阵空位的横坐标空位的纵坐标初始矩阵查找在位数坐标差绝对值之和找出空

2、格的横坐标找出空格的纵坐标判断是否有解,奇偶性相同空格上移空格下移空格左移空格右移移动后更新状态ilist,MatrixNodeM_Matrix);/目标矩阵public:MatrixNode();MatrixNodestart(MatrixNodeM_Matrix);/intTruePlace(MatrixNodeT_place);/intp_place(MatrixNodeP_place);/intf_kongx(MatrixNodefind_kongx);/intf_kongy(MatrixNodefind_kongy);/boolsolved(MatrixNodeM_Matrix);/

3、则有解，否则无解MatrixNodeup_move(MatrixNodeM_Matrix);/MatrixNodedown_move(MatrixNodeM_Matrix);/MatrixNodeleft_move(MatrixNodeM_Matrix);/MatrixNoderight_move(MatrixNodeM_Matrix);/MatrixNodeupdata_m(MatrixNodeM_Matrix);/MatrixNodeparents(deque<MatrixNode>/找到该节点的父亲;/=MatrixNode:MatrixNode()placetrue00=1

4、;placetrue01=2;placetrue02=3;placetrue10=8;placetrue11=-1;placetrue12=4;placetrue20=7;placetrue21=6;placetrue22=5;/MatrixNodeMatrixNode:start(MatrixNodeM_Matrix)/cout<<"请按如下格式输入初始矩阵(空位用0表示)："<<endl;cout<<"123n456n708"<<endl;cout<<"八数码的初始状态如下:&qu

5、ot;<<endl;for(inta=0;a<M;a+)for(intb=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_Matrix.f=M_Matrix.f-1;returnM_Matrix;/boolsolved(MatrixNodeM_Matrix)/intnum8;inttarget8;inta=0;intb=0;for(intm=0;m<M;m+)for(intn

6、=0;n<M;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+)for(j=i+1;j<8;j+)初始矩阵初始更新时深度多加判断是否可解不考虑空格if(numj<numi)count_num+;if(targetj<targeti)count_target+;num%2if(count_nu

7、m%2=0&&count_target%2=0)|(count1&&count_target%2=1)returntrue;elsereturnfalse;查找在位查找在位/intMatrixNode:TruePlace(MatrixNodeT_place)/数T_place.m=0;intNumT_place=0;for(inti=0;i<M;i+)for(intj=0;j<M;j+)if(T_place.placeij=placetrueij)T_place.m=T_place.m+1;NumT_place=NumT_place+1;return

8、NumT_place;/坐标差的绝intMatrixNode:p_place(MatrixNodeP_place)/对值之和P_place.p=0;intnum=0;for(intPa=0;Pa<M;Pa+)for(intPb=0;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.

9、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.p

10、lacePaPb=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;i<M;i+)for(intj=0;j<M;j+)if(find_kongx.placeij=0)num=i;returnnum;/intMatrixNode:f_kongy(MatrixNodefind_kongy)/坐标intnum;for(inti=0;i<M;i+)for(intj=0;j

11、<M;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.kong_x-1up_m.kong_y=num;up_m=up_m.

12、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.updata_m(up_m);returnup_m;/Matrix

13、NodeMatrixNode: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_yup_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;/MatrixNodeMatrixNode:right_move(MatrixNo

14、deM_Matrix)/空格右移intnum;MatrixNodeup_m=M_Matrix;num=up_m.placeup_m.kong_xup_m.kong_y;up_m.placeup_m.kong_xup_m.kong_yup_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;/MatrixNodeMatrixNode:updata_m(MatrixNodeM_Matrix)/移动后更新状态MatrixNodeup_m=M

15、_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;/深度加1up_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(deque<MatrixNode>ilist,MatrixNodeM_Matrix)/MatrixNodeM_Matr

16、ix1=ilist.front();MatrixNodeup_m;intm;up_m=M_Matrix1.up_move(M_Matrix1);m=0;for(inta1=0;a1<M;a1+)for(intb1=0;b1<M;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;a2<M;a2+)for(intb2=0;b2<M;b2+)if(up_m.placea2b2=M_Matrix.pla

17、cea2b2)m+;if(m=9)returntrue;up_m=M_Matrix1.left_move(M_Matrix1);m=0;for(inta3=0;a3<M;a3+)for(intb3=0;b3<M;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;a4<M;a4+)for(intb4=0;b4<M;b4+)if(up_m.placea4b4=M_Matrix.placea4b4)

18、m+;if(m=9)returntrue;elsereturnfalse;输出输出/voidprintMatrix(constMatrixNodeMatrix)/矩阵for(inti=0;i<M;i+)for(intj=0;j<M;j+)cout<<Matrix.placeij<<","cout<<endl;cout<<endl;/boolless_f(constMatrixNodeM_Matrix1,constMatrixNodeM_Matrix2)returnM_Matrix1.f<M_Matrix2.f

19、;检查检查/boollookout(deque<MatrixNode>ilist,MatrixNodeM_Matrix)/新生成的节点是否已扩展deque<MatrixNode>:iteratorVi=ilist.begin();inti,j,m;while(Vi!=ilist.end()m=0;for(i=0;i<M;i+)for(j=0;j<M;j+)if(*Vi).placeij=M_Matrix.placeij)m+;if(m=9)returntrue;/不是新扩展的Vi+;returnfalse;/是新扩展的/=voidmain()intstep=

20、0;MatrixNodemat;MatrixNodemat_trn;MatrixNodemat_trn1;MatrixNodemat_trn2;MatrixNodemat_trn3;MatrixNodemat_trn4;MatrixNodeparent;mat=mat.start(mat);deque<MatrixNode>openlist;openlist.push_front(mat);deque<MatrixNode>closedlist;if(solved(mat)=false)cout<<"无法找到路径!"<<end

21、l;return;mat_trn=openlist.front();/访问第一个元素while(mat_trn.m!=8)closedlist.push_front(mat_trn);openlist.pop_front();/删除第一个元素/向上移mat_trn1=mat_trn;if(mat_trn1.f_kongx(mat_trn1)>=1)mat_trn1=mat_trn1.up_move(mat_trn1);if(lookout(openlist,mat_trn1)=false&&lookout(closedlist,mat_trn1)=false)/检查新节点

22、是否已扩展openlist.push_front(mat_trn1);/向下移mat_trn2=mat_trn;if(mat_trn2.f_kongx(mat_trn2)<=1)mat_trn2=mat_trn2.down_move(mat_trn2);if(lookout(openlist,mat_trn2)=false&&lookout(closedlist,mat_trn2)=false)/检查新节点是否已扩展openlist.push_front(mat_trn2);/向左移mat_trn3=mat_trn;if(mat_trn3.f_kongy(mat_trn3)>=1)mat_trn3=mat_trn3.left_move(mat_trn3);if(lookout(openlist,mat_trn3)=false&&lookout(closedli