八数码C语言知识学习A算法详细代码

1、#include #include #include #include #include using namespace std;struct nodeint a33;int father;int gone;int fn;int x,y;int deep;vector store;int mx4=-1,0,1,0;int my4=0,-1,0,1;/ 存放矩阵/ 父节点的位置/ 是否遍历过 ,1为是 ,0 为否/ 评价函数的值/ 空格的坐标/ 节点深度/ 存放路径节点/ 上下左右移动数组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/pre 指向 storenum 的父节点位置/ 循环直到 pre 为 0,既初始节点int pre=storenum.father;bool test= true ;while (!pre)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 父节点位置pre=storepre.father;return true ;void print( int num)vector temp;int pre=storenum.father; temp.push_back(num);while (pre!=0)temp.push_back(pre);/ 打印路径 ,storenum 为目标节点/ 存放路径/ 从目

4、标节点回溯到初始节点pre=storepre.father;coutendl;cout数码移动步骤 *=0;m-)cout - 第 mm 步 - ：endl;for (int i=0;i3;i+)for (int j=0;j3;j+)coutstoretempm.aijcoutendl;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+)/ 当找到一个

5、值后 ,计算这个值位置与目标位置的距离差 ,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 ;if (test= false ) break ;if(test= false ) break ;fn_temp=fn_temp+storen

6、um.deep; / 加上节点深度return fn_temp;for (int i=0;i3;i+)for (int j=0;j3;j+)if (storenum.aij=0)storenum.x=i;storenum.y=j;intreturn ;main()cout A* 算法解决 8数码问题 endl;while (true )store.clear();/ 清空 storevector open;/ 建立 open 表int i,j,m,n,f;int temp;bool test;top=1;/ 当前节点在 store 的位置 ,初始节点在 store1int target9;in

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

8、ue ;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; / 输入目标状态 ,储存在 test= false ;while (test= false )f=0;for (i=0;i3;i+)for (j=0;jtemp;store0.

9、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= false ) break ;if (test= false )cout 输入重复 ,请重新输入 :endl;for (i=0;i9;i+) / 检查目标状态与初始状态是否匹配 test= false ;for (j=0;j9;j+)if (begini=targetj)test= true ;break ;if(test=

10、 false ) break ;if (test= 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,Count

11、2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);double d;/ 获取时间 Count1store1.father=0;store1.gone=0;store1.deep=0;store1.fn=get_fn(1);/ 初始化参数/ 初始节点的父节点为 0if(check(1) / 判断初始状态与目标状态是否相同 print(1);/system(pause);/return 0;coutendl;continue ;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)top+;store.push_bac

13、k(storemin);storetop.father=min;storetop.gone=0;storetop.deep=storemin.deep+1;/ 当变换后的空格坐标在矩阵中时/ 把 storemin 压入 store 中成为新增节/ 新增节点的父节点为 min/ 新增节点未被访问/ 新增节点的深度为父节点深度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);/ 交换空格与相邻数字/ 移动后的空格坐标/ 移动后的 fn 值/把top压入open表中/ 检查是否到达目标/system(pause);/return 0;break ;if (search(top)= false ) / 检查新增节点是否被访问过 ,若访问过 ,则删 除此节点top-;store.pop_back();ope