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

1、#inelude <iostream>#inelude <time.h>#include <windows.h>#inelude <veetor>#inelude <emath> using namespaeestd;veetor <no de> store;/存放路径节点struet no deinta33;/存放矩阵intfather;/父节点的位置intgone;/是否遍历过,1为是,0为否intfn；/评价函数的值intx,y;/空格的坐标intdeep;/节点深度；int mx4=-1,0,1,0;int my4

2、=0,-1,0,1;/上下左右移动数组int top;/当前节点在store中的位置bool eheek( int num)/判断storenum节点与目标节点是否相同，目标节点储存在store0中for (int i=0;i<3;i+)for (int j=0；j<3;j+)if (storenum.aij!=store0.aij)return false ;return true ;bool seareh( int num)/判断storenum节点是否已经扩展过，没有扩展返回trueint pre=storenum.father;/pre 指向 storenum的父节点位置b

3、ool test= true ;while (!pre)/循环直到pre为0,既初始节点for (int i=0;i<3;i+)for ( int j=0;j<3;j+)if (storepre.aij!=storenum.aij)test= falsebreak;if (test= false ) break;/pre继续指向storepre父节点位置if (test= true ) return false pre=storepre.father;return true ;*“void print( int num)vectorv int > temp;int pre=s

4、torenum.father; temp.push_back (n um);while (pre!=0) temp.push_back(pre); pre=storepre.father;cout«e ndl;coutvv "* 数码移动步骤 int mm=1; / 步数/打印路径,storenum为目标节点/存放路径/从目标节点回溯到初始节点<<e ndl;for (int m=temp.size()_1;m>=0;m_)cout«"- 第"<<mm<<- : "<<endl;f

5、or (int i=0;i<3;i+)for (int j=0;j<3;j+) cout<<storetempm.aij<<cout«e ndl;mm+;cout«e ndl;coutvv"所需步数为："<<storenum.deep<<endl; return ;int get_fn( int num)int fn_temp=0; bool test= true ;for (int i=0;i<3;i+)/返回storenum的评价函数值/评价函数值/当找到一个值后，计算这个值位置与目标

6、位置的距离差，test置为false后继续寻找下一个值for (int j=0；j<3;j+)test= true ;for (int k=0;k<3;k+)for (int l=0;l<3;l+)if (storenum.x!=i|storenum.y!=j)&&storenum.aij=store0.akl) 寻值时排除空格位fn _temp=f n_temp+abs(i-k)+abs(j-l);test= false ;if (test= false ) break;if (test= false ) break;fn_temp=fn_temp+stor

7、enum.deep;/ 加上节点深度return fn_temp;/void kongxy( int num)for (int i=0;i<3;i+)/获得空格坐标for (int j=0;j<3;j+)if (storenum.aij=0)store n um.x=i;store n um.y=j; returnint main()cout«"A*算法解决8数码问题"<<endl;while (true )store.clear(); vector< int > open; int i,j,m,n,f;int min;int

8、temp;/ 清空 store/ 建立 open表storemin储存fn值最小的节点bool test;top=1;/当前节点在store的位置，初始节点在store1int target9;int begin9;/储存初始状态和目标状态，用于判断奇偶int t1=0,t2=0;/初始状态和目标状态的奇偶序数node no de_temp;store.push_back (no de_temp);store.push_back(node_temp);/ 用于创建 store0和 store1, 以便下面使用coutvv"请输入初始数码棋盘状态,0代表空格："<<

9、;endl; /输入初始状态，储存在store1 中test= false ;while (test= false )f=0;for (i=0;i<3;i+)for (j=0;j<3;j+)cin> >temp;store1.aij=temp;begi n f+=temp;test= true ;for (i=0;i<8;i+)/检查是否有重复输入，若有则重新输入for (j=i+1;j<9;j+)if (begini=beginj)test= false ;break;if (test= false ) break;if (test= false ) co

10、ut<< "输入重复,请重新输入:"<<endl;kongxy(1);/找岀空格的坐标coutvv"请输入目标数码棋盘状态,0代表空格："<<endl; /输入目标状态，储存在store0中test= false while (test= false )f=0;for (i=0;i<3;i+)for (j=0;j<3;j+)cin> >temp;store0.aij=temp;targetf+=temp;test= true ;for (i=0;i<8;i+)/检查是否有重复输入，若有则重

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

12、(test= false ) cout<< "输入与初始状态不匹配，请重新输入:"<<endl; for (i=1;i<9;i+)/判断奇偶序数是否相同，若不相同则无法找到路径for (j=1;i-j>=0;j+)if (begini>begini-j)if (begini-j!=0) t1+;for (i=1;i<9;i+)for (j=1;i-j>=0;j+)if (targeti>targeti-j)if (targeti-j!=0) t2+;if (!(t1%2=t2%2)cout«"无

13、法找到路径."<<endl;cout«e ndl;system("pause");/return 0;continue ;LARGEN TEGER Freg;LARGEN TEGER Cou nt1,Cou nt2;QueryPerforma nceFreque ncy(&Freg);QueryPerformanceCounter(&Count1);/ 获取时间 Count1double d;store1.father=0; store1.go ne=0; store1.deep=0; store1.fn=get_f n (1

14、);/初始化参数/初始节点的父节点为0if (check(1)prin t(1); system("pause");/return 0; cout«e ndl;continue ;/判断初始状态与目标状态是否相同ope n.push_back(1);/把初始状态在store中的位置数压入open表中while (!open.empty()/当open表不为空时,开始寻找路径if (check(top) break;mi n=top;int i_min=0;for (i=0;i<open.size();i+)/遍历open表中元素，找岀store中fn值最小的

15、节占八、if (storeopeni.fn<=storemin.fn&&storeopeni.gone=0)min=ope ni; i_mi n=i;store min .go ne=1;ope n.erase(ope n.begi n()+i_mi n);/把最小节点标记遍历过，并从open表中删除m=store min .x; n=storemi n.y;/空格坐标for (f=0;f<4;f+) i=m+mxf; j=n+myf;/上下左右移动空格移动if (i>=0&&i<=2&&j>=0&&

16、j<=2)/当变换后的空格坐标在矩阵中时，开始top+;store.push_back(store min );节点，位置为storetopstoretop.father=mi n;storetop.g on e=0;storetop.deep=storemi n.deep+1;/+1把storemin压入store中成为新增新增节点的父节点为min新增节点未被访问/新增节点的深度为父节点深度temp=storetop.am n;storetop.am n=storetop.aij;storetop.aij=temp;/交换空格与相邻数字storetop.x=i;storetop.y=j;storetop.f n=get_f n( top);/移动后的空格坐标移动后的fn值ope n.push_back(top); if (check(top)/把top压入open表中检查是否到达目标pr in t(top);system("pause");/return 0;break;if (search(top)= false )/检查新增节点是否被访问过，若访问过，则删除此节点top-;store.pop_back();ope n.pop_back();Query