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

1、#include<iostream>#include<deque>#include<algorithm>#include<iterator>usingnamespacestd;#defineM3classMatrixNodepublic:intm;intd;intp;intf;intplaceMM;intplacetrueMM;intkong_x;intkong_y;/定義MatrixNode類/在位個數(shù)深度/牌與其目標位置直接步數(shù)之和/f=d+p，估價函數(shù)/當前矩陣目標矩陣/空位的橫坐標空位的縱坐標/public:MatrixNode();Ma

2、trixNodestart(MatrixNodeM_Matrix);intTruePlace(MatrixNodeT_place);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(Ma

3、trixNodeM_Matrix);MatrixNoderight_move(MatrixNodeM_Matrix);MatrixNodeupdata_m(MatrixNodeM_Matrix);/初始矩陣/查找在位數(shù)/坐標差絕對值之和找出空格的橫坐標/找出空格的縱坐標判斷是否有解，奇偶性相同則/空格上移/空格下移/空格左移/空格右移/移動后更新狀態(tài)MatrixNodeparents(deque<MatrixNode>ilist,MatrixNodeM_Matrix);該節(jié)點的父親找到；:MatrixNode:MatrixNode()placetrue00=1;placetrue0

4、1=2;placetrue02=3;placetrue10=8;placetrue11=-1;placetrue12=4;/目標矩陣placetrue20=7;placetrue21=6;placetrue22=5;/MatrixNodeMatrixNode:start(MatrixNodeM_Matrix)/初始矩陣cout<<"請按如下格式輸入初始矩陣(空位用。表示)："<<endl;cout<<"123n456n708"<<endl;cout<<"八數(shù)碼的初始狀態(tài)如下："

5、;<<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,應(yīng)該減去M_Matrix.f=M_Matrix.f-1;returnM_Matrix;/boolsolved(MatrixNodeM_Matrix)/判斷是否可解intnum8;inttarget8;inta=0;intb=0;for(intm=0;m<

6、M;m+)for(intn=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+;0)|(count_num%2/查找在位數(shù)i

7、f(count_num%2=0&&count_target%2=1&&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;returnNumT_plac

8、e;/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.p+(abs(Pa

9、-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);/返回空格橫坐標/返回空格縱坐標/空格上移/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-0);i

10、f(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;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

11、=0;j<M;j+)if(find_kongy.placeij=0)num=j;returnnum;/MatrixNodeMatrixNode:up_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

12、(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;/MatrixNodeMatr

13、ixNode: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;/MatrixNodeMatrixNode:right_move(MatrixNodeM_Mat

14、rix)/空格右移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;/移動后更新狀態(tài)/查找在位數(shù)/距離和深度加1/估價值找出空格的橫坐找出空格的縱坐MatrixNodeMatrixNode:updata_m(MatrixNode

15、M_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(deque<MatrixNode>ilist,MatrixNodeM_Matrix)/尋找父節(jié)點MatrixNodeM_Matrix1=ilist.front()

16、;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.placea2b2)m+;if(m=9)

17、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)m+;if(m=9)returnt

18、rue;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;/boollookout(deque

19、<MatrixNode>ilist,MatrixNodeM_Matrix)/檢查新生成的節(jié)點是否已擴展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=0;MatrixNodemat;Matri

20、xNodemat_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<<"無法找到路徑！!"<<endl;return;)mat_trn=op

21、enlist.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)/檢查新節(jié)點是否已擴展openlist.push_f

22、ront(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)/檢查新節(jié)點是否已擴展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&&false)/檢查新節(jié)點