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

1、#include<iostream>#include<deque>#include<algorithm>#include<iterator>usingnamespacestd;#defineM3classMatrixNodepublic:intm;intd;intp;intf;intplaceMM;intplacetrueMM;intkong_x;intkong_y;/定義MatrixNode類/在位個(gè)數(shù)深度/牌與其目標(biāo)位置直接步數(shù)之和/f=d+p，估價(jià)函數(shù)/當(dāng)前矩陣目標(biāo)矩陣/空位的橫坐標(biāo)空位的縱坐標(biāo)/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ù)/坐標(biāo)差絕對值之和找出空格的橫坐標(biāo)/找出空格的縱坐標(biāo)判斷是否有解，奇偶性相同則/空格上移/空格下移/空格左移/空格右移/移動后更新狀態(tài)MatrixNodeparents(deque<MatrixNode>ilist,MatrixNodeM_Matrix);該節(jié)點(diǎn)的父親找到；:MatrixNode:MatrixNode()placetrue00=1;placetrue0

4、1=2;placetrue02=3;placetrue10=8;placetrue11=-1;placetrue12=4;/目標(biāo)矩陣/初始矩陣"<<endl;/初始更新時(shí)深度多加判斷是否可解/不考慮空格placetrue20=7;placetrue21=6;placetrue22=5;/MatrixNodeMatrixNode:start(MatrixNodeM_Matrix)cout<<"請按如下格式輸入初始矩陣(空位用0表示):cout<<"123n456n708"<<endl;cout<<

5、"八數(shù)碼的初始狀態(tài)如下："<<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;

6、m<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ù)if

7、(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_place

8、;/intMatrixNode:p_place(MatrixNodeP_place)/坐標(biāo)差的絕對值之和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);/返回空格橫坐標(biāo)/返回空格縱坐標(biāo)/空格上移/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);if

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

13、xNode: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_Matr

14、ix)/空格右移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/估價(jià)值找出空格的橫坐找出空格的縱坐MatrixNodeMatrixNode:updata_m(MatrixNodeM

15、_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é)點(diǎn)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)r

17、eturntrue;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(

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

19、(deque<MatrixNode>ilist,MatrixNodeM_Matrix)節(jié)點(diǎn)是否已擴(kuò)展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;/不是新擴(kuò)展的Vi+;)returnfalse;是新擴(kuò)展的)=voidmain()intstep=0;MatrixNodemat;Matrix

20、Nodemat_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=ope

21、nlist.front();/訪問第個(gè)元素while(mat_trn.m!=8)closedlist.push_front(mat_trn);openlist.pop_front();/刪除第一個(gè)元素/向上移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é)點(diǎn)是否已擴(kuò)展openlist.push_fr

22、ont(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é)點(diǎn)是否已擴(kuò)展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é)點(diǎn)