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

1、整理 #include #include #include #include #include using namespacestd; struct node int a33; int father; int gone; int fn; int x,y; int deep; ; / 存放矩阵 / 父节点的位置 / 是否遍历过 ,1 为是 ,0 为否 / 评价函数的值 / 空格的坐标 / 节点深度 vector store; / 存放路径节点 int mx4=-1,0,1,0; int my4=0,-1,0,1; / 上下左右移动数组 int top; /当前节点在 store 中的位置 boo

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

3、点 for(int i=0;i3;i+) for (int j=0;j3;j+) if(storepre.aij!=storenum.aij) test=false; break;整理 if (test= false) break; if(test= true) return false; pre=storepre.father; return true; coutendl; cout* 数码移动步骤 * =0;m-) cout-第vvmmvv 步-:endl; for(int i=0;i3;i+) for(int j=0;j3;j+) coutstoretempm.aij coutendl;

4、 mm+; coutendl; cout所需步数为:storenum.deependl; return; /返回 storenum的评价函数值 / 评价函数值 / 当找到一个值后 ,计算这个值位置与目标位置的距离差 后继续寻找下一个值/pre 继续指向 storepre 父节点位置 void prin t(i nt n um) vector temp; int pre=storenum.father; temp.push_back(num); while(pre!=0) temp.push_back(pre); pre=storepre.father; /打印路径,storenum 为目标节点

5、 / 存放路径 / 从目标节点回溯到初始节点 int get_fn(int num) int fn_temp=0; bool test=true; for(int i=0;i3;i+) ,test 置 为 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; i

6、f(test= false) break; if(test= false) break; fn_temp=fn_temp+storenum.deep; / 加上节点深度 return fn_temp; void kongxy(int 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; / 清空 store /建立 open 表 storemin储存 f

7、n 值最小的节点 /当前节点在 store 的位置，初始节点在 store1 int target9; int begin9; / 储存初始状态和目标状态 ,用于判断奇偶 int t1=0,t2=0; / 初始状态和目标状态的奇偶序数 node node_temp; store.push_back(node_temp); store.push_back(node_tempy/ 用于创建 store0 和 store1,以便下面使用 cout请输入初始数码棋盘状态，0代表空格： endl; /输入初始状态，储存在store1中 test=false; while(true) store.clea

8、r(); vector open; int i,j,m,n,f; int min; int temp; bool test; top=1; 整理 while(test=false) f=0; for(i=0;i3;i+) for(j=0;jtemp; store1.aij=temp; beginf+=temp; test=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) co

9、ut 输入重复 ，请重新输入 :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+=temp; test=true; for(i=0;i8;i+) / 检查是否有重复输入 ,若有则重新输入 for(j=i+1;j9;j+) if(targeti=targetj) test=false; break; if(test= f

10、alse) 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= false) cout 输入与初始状态不匹配 ,请重新输入 :endl; for(i=1;i=0;j+) if(beginibegini-j) if(begini-j!=0) t1

11、+; 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); QueryPerformanceCounter(&Count1)/;/ 获取时间 Count1 double d; store

12、1.father=0; store1.gone=0; store1.deep=0; store1.fn=get_fn(1); if(check(1) print(1); /system(pause); /return 0; coutendl; continue; /把初始状态在 store 中的位置数压入 open 表中/ 初始化参数 / 初始节点的父节点为 0 / 判断初始状态与目标状态是否相同 open.push_back(1); while(!open.empty() /当 open 表不为空时，开始寻找路径 if(check(top) break; min=top; 整理 / 检查新增

13、节点是否被访问过 ,若访问过 ,则删除移动 为 storetop 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&

14、amp;j=2) top+; store.push_back(storemin); / 当变换后的空格坐标在矩阵中时 ,开始 /把 storemin 压入 store 中成为新增节点，位置 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); open.push_back(top); if(check(top) print(top); /system(pause); /return 0; break; / 移动后的空格坐标 / 移动后的 fn 值 / 把 top 压入 open 表中 / if(search(top)=false) 整理 此节点 top-; store.po