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

1、.#include#include#include#include#includeusing namespace std;struct nodeint a33; /存放矩阵int father; /父节点的位置 int gone; /是否遍历过,1为是,0为否int fn; /评价函数的值int x,y; /空格的坐标int deep; /节点深度 ;vector store; /存放路径节点int mx4=-1,0,1,0;int my4=0,-1,0,1; /上下左右移动数组int top; /当前节点在store中的位置bool check(int num) /判断storenum节点与

2、目标节点是否相同,目标节点储存在store0中 for(int i=0;i3;i+)for(int j=0;j3;j+)if(storenum.aij!=store0.aij)return false;return true; bool search(int num) /判断storenum节点是否已经扩展过 ,没有扩展返回true int pre=storenum.father; /pre指向storenum的父节点位置 bool test=true;while(!pre) /循环直到pre为0,既初始节点 for(int i=0;i3;i+)for (int j=0;j3;j+)if(st

3、orepre.aij!=storenum.aij)test=false;break;if(test=false) break;if(test=true) return false;pre=storepre.father; /pre继续指向storepre父节点位置 return true;void print(int num) /打印路径,storenum为目标节点 vector temp; /存放路径 int pre=storenum.father;temp.push_back(num);while(pre!=0) /从目标节点回溯到初始节点 temp.push_back(pre);pre=

4、storepre.father;coutendl;cout*数码移动步骤*=0;m-)cout-第mm步-：endl;for(int i=0;i3;i+)for(int j=0;j3;j+)coutstoretempm.aij ;coutendl;mm+;coutendl;cout所需步数为: storenum.deependl; return;int get_fn(int num) /返回storenum的评价函数值 int fn_temp=0; /评价函数值 bool test=true;for(int i=0;i3;i+) /当找到一个值后,计算这个值位置与目标位置的距离差,test置为

5、false后继续寻找下一个值 for(int j=0;j3;j+)test=true;for(int k=0;k3;k+)for(int l=0;l3;l+)if(storenum.x!=i|storenum.y!=j)&storenum.aij=store0.akl) /寻值时排除空格位 fn_temp=fn_temp+abs(i-k)+abs(j-l);test=false;if(test=false) break;if(test=false) break;fn_temp=fn_temp+storenum.deep; /加上节点深度 return fn_temp;void kongxy(i

6、nt num) /获得空格坐标 for(int i=0;i3;i+)for(int j=0;j3;j+)if(storenum.aij=0)storenum.x=i;storenum.y=j;return;int main()cout-A*算法解决8数码问题-endl;while(true)store.clear(); /清空store vector open; /建立open表 int i,j,m,n,f;int min; /storemin储存fn值最小的节点 int temp;bool test;top=1; /当前节点在store的位置,初始节点在store1 int target9;

7、 int begin9; /储存初始状态和目标状态,用于判断奇偶 int t1=0,t2=0; /初始状态和目标状态的奇偶序数 node node_temp; store.push_back(node_temp);store.push_back(node_temp); /用于创建store0和store1,以便下面使用 cout请输入初始数码棋盘状态,0代表空格：endl; /输入初始状态,储存在store1中 test=false;while(test=false)f=0;for(i=0;i3;i+)for(j=0;jtemp;store1.aij=temp;beginf+=temp;tes

8、t=true;for(i=0;i8;i+) /检查是否有重复输入,若有则重新输入 for(j=i+1;j9;j+)if(begini=beginj)test=false;break; if(test=false) break;if(test=false) cout输入重复,请重新输入:endl; kongxy(1); /找出空格的坐标 cout请输入目标数码棋盘状态,0代表空格： endl; /输入目标状态,储存在store0中 test=false;while(test=false)f=0;for(i=0;i3;i+)for(j=0;jtemp;store0.aij=temp;targetf

9、+=temp;test=true;for(i=0;i8;i+) /检查是否有重复输入,若有则重新输入 for(j=i+1;j9;j+)if(targeti=targetj)test=false;break; if(test=false) break;if(test=false)cout输入重复,请重新输入:endl;continue; /若重复,重新输入 for(i=0;i9;i+) /检查目标状态与初始状态是否匹配 test=false;for(j=0;j9;j+)if(begini=targetj)test=true;break; if(test=false) break;if(test=

10、false) cout输入与初始状态不匹配,请重新输入:endl; for(i=1;i=0;j+)if(beginibegini-j)if(begini-j!=0) t1+;for(i=1;i=0;j+)if(targetitargeti-j)if(targeti-j!=0) t2+;if(!(t1%2=t2%2)cout无法找到路径.endl;coutendl;/system(pause);/return 0;continue;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);Que

11、ryPerformanceCounter(&Count1);/获取时间Count1double d;store1.father=0; /初始化参数 store1.gone=0;store1.deep=0; /初始节点的父节点为0 store1.fn=get_fn(1);if(check(1) /判断初始状态与目标状态是否相同 print(1);/system(pause);/return 0;coutendl;continue;open.push_back(1); /把初始状态在store中的位置数压入open表中 while(!open.empty() /当open表不为空时,开始寻找路径

12、if(check(top) break;min=top;int i_min=0;for(i=0;iopen.size();i+) /遍历open表中元素,找出store中fn值最小的节点 if(storeopeni.fn=storemin.fn&storeopeni.gone=0)min=openi;i_min=i;storemin.gone=1; open.erase(open.begin()+i_min); /把最小节点标记遍历过,并从open表中删除m=storemin.x; n=storemin.y; /空格坐标 for(f=0;f=0&i=0&j=2) /当变换后的空格坐标在矩阵中时

13、,开始移动 top+;store.push_back(storemin); /把storemin压入store中成为新增节点,位置为storetop storetop.father=min; /新增节点的父节点为min storetop.gone=0; /新增节点未被访问 storetop.deep=storemin.deep+1; /新增节点的深度为父节点深度+1 temp=storetop.amn; /交换空格与相邻数字 storetop.amn=storetop.aij;storetop.aij=temp;storetop.x=i; /移动后的空格坐标 storetop.y=j;storetop.fn=get_fn(top); /移动后的fn值 open.push_back(top); /把top压入open表中 if(check(top) /检查是否到达目标 print(top);/system(pause);/return 0;break;if(search(top)=false) /检查新增节点是否被访问过,若访问过,则删除此节点 top-;store