八数码C语言A算法详细代码.doc

《八数码C语言A算法详细代码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#include#include#includeusingnamespacestd;structnode{inta[3][3];//存放矩阵intfather;//父节点的位置intgone;//是否遍历过,1为是,0为否intfn;//评价函数的值intx,y;//空格的坐标intdeep;//节点深度};vectorstore;//存放路径节点intmx[4]={-1,0,1,0};i

2、ntmy[4]={0,-1,0,1};//上下左右移动数组inttop;//当前节点在store中的位置boolcheck(intnum)//判断store[num]节点与目标节点是否相同,目标节点储存在store[0]中{for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(store[num].a[i][j]!=store[0].a[i][j])returnfalse;}}returntrue;}boolsearch(intnum)//判断store[num]节点是否已经扩展过,没有

3、扩展返回true{intpre=store[num].father;//pre指向store[num]的父节点位置booltest=true;while(!pre){//循环直到pre为0,既初始节点for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(store[pre].a[i][j]!=store[num].a[i][j]){test=false;break;}}if(test==false)break;}if(test==true)returnfalse;pre=store[pr

4、e].father;//pre继续指向store[pre]父节点位置}returntrue;}voidprint(intnum)//打印路径,store[num]为目标节点{vectortemp;//存放路径intpre=store[num].father;temp.push_back(num);while(pre!=0){//从目标节点回溯到初始节点temp.push_back(pre);pre=store[pre].father;}cout<

5、*****"<=0;m--){cout<<"---第"<

6、ore[num]的评价函数值{intfn_temp=0;//评价函数值booltest=true;for(inti=0;i<3;i++){//当找到一个值后,计算这个值位置与目标位置的距离差,test置为false后继续寻找下一个值for(intj=0;j<3;j++){test=true;for(intk=0;k<3;k++){for(intl=0;l<3;l++){if((store[num].x!=i

7、

8、store[num].y!=j)&&store[num].a[i][j]==store[0].a[k][l])

9、{//寻值时排除空格位fn_temp=fn_temp+abs(i-k)+abs(j-l);test=false;}if(test==false)break;}if(test==false)break;}}}fn_temp=fn_temp+store[num].deep;//加上节点深度returnfn_temp;}voidkongxy(intnum)//获得空格坐标{for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(store[num].a[i][j]==0){store[num].

10、x=i;store[num].y=j;}}}return;}intmain(){cout<<"-----------A*算法解决8数码问题------------"<open;//建立open表inti,j,m,n,f;intm