八数码问题详解

1、v1.0可编辑可修改八数码问题详解（用bfs实现）八数码问题也称为九宫问题。在3X3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。如图:对这道题用bfs解决个人认为是个不错的方法，首先因为它有九个格子，那么便可以用state数组记录他的的九个格子的数值，

2、其中空格为0,后者由于它只有九个数，因此共有9!=362880种可能性，用bfs解决较快。下面给出bfs实现的三种代码（这里的三种指的是对是否访问过已知节点的三种判断方法）:1.8这样的数据，0作为判断依据简单于用数据作为判断依据if（si=0）break;x=i/3;y=i%3;z=i;/用hash避免同一状态的再次访问在讲这种方法之前建议读者先看一下算法导论中有关hash的介绍为了方便自己以后看的时候方便，先写一下有关hash的内容Hash表解决冲突三种hash函数：first:除法散列函数：h(k)=kmodm(m为所选的余数，最好选接近装载因子a=n/m,但又远离2的k次哥的质数)se

3、cond：乘法散列法函数：看图：具体代码实现下面有介绍third:全域散列函数h(k)=(ak+b)modp)modm(p>m且p和m都为质数)-1)/2;for(i=num=0;i<le;i+)num=num*10+si;k=(longlong)num;ss=(longlong)(A*(1LL<<w);r0=k*ss%(1LL<<w);ans=r0>>(w-p);returnans;.8这样的数据，0作为判断依据简单于用数据作为判断依据if(si=0)break;x=i/3;y=i%3;z=i;-1)/2;for(i=num=0;i<le

4、;i+)num=num*10+si;k=(longlong)num;ss=(longlong)(A*(1LL<<w);r0=k*ss%(1LL<<w);ans=r0>>(w-p);returnans;.8这样的数据，0作为判断依据简单于用数据作为判断依据if(si=0)break;x=i/3;y=i%3;z=i;stl集合避免重复访问同一状态.8这样的数据，0作为判断依据简单于用数据作为判断依据if(si=0)break;x=i/3;y=i%3;z=i;/记录空的格子的行标，列表，和所在位置，这里的位置按照从左到右从上到下依次递增for(i=0;i<4

5、;i+)/按照上，下，左，右四个方向进行搜索nx=x+deri0;ny=y+deri1;nz=nx*3+ny;if(nx>=0&&nx<3&&ny>=0&&ny<3)state&t=strear;memcpy(&t,&s,sizeof(s); /记录此时的状态即九个格子的数值tz=snz;tnz=sz;disrear=disfront+1;if(try_to_insert(rear)/判断strear这种状态是否已经出现过rear+;front+;return0;intmain(void)intncase,i,oj;scanf("%d",&ncase);while(ncase-)memset(head,0,sizeof(head);for(i=0;i<le;i+)scanf("%d”,&st1i);/按从左到右从上到下的顺序存储数据for(i=0;i<le;i+)scanf("%d",&am