八数码难题
一.广搜：
首先要考虑用什么存每一个状态
显然每个状态都用一个矩阵存是很麻烦的。
我们可以考虑将一个3*3的矩阵用一个字符串或long long 存。
每次扩展时再转化为矩阵。
另外一个问题是判重，对于已经搜过的状态，就不再扩展了。
10^9次方的bool数组会爆空间
可以考虑用hash
或者STL的map或set
//map 洛谷 8964ms #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<map> using namespace std; map<long long ,long long> m; long long s,que[10000010],head=1,tail=1; long long c[4][4]; long long zx[5]={0,0,0,1,-1}, zy[5]={0,1,-1,0,0}; int main() { scanf("%lld",&s); m[s]=0; que[head]=s; while(head<=tail) //广搜 { int x,y; long long u=que[head++]; //取出队首元素 long long uu=u; if(u==123804765) break; for(int i=1;i<=3;i++) //将long long型转化为矩阵 for(int j=1;j<=3;j++) { c[i][j]=uu%10; if(c[i][j]==0){ //标记空格 x=i; y=j; } uu/=10; } for(int i=1;i<=4;i++) { long long xx=x+zx[i],yy=y+zy[i]; //向四个方向搜索 if(1<=xx&&xx<=3&&1<=yy&&yy<=3) { swap(c[x][y],c[xx][yy]); long long l=0; for(int j=3;j>=1;j--) for(int k=3;k>=1;k--) l=l*10+c[j][k]; //将扩展状态转化为长整形 map < long long ,long long > :: iterator it = m.find(l) ; //判重 map中的find函数用于寻找象所对应的原象（键值），若查找失败，返回最后一个键值位置 if(it==m.end()){ m[l]=m[u]+1; que[++tail]=l; } swap(c[x][y],c[xx][yy]); } } } printf("%lld ",m[123804765]); return 0; }
//hash 洛谷 1080ms #pragma GCC optimize(3) #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int MOD=23333333; long long s,que[10000010],time[10000010],head=1,tail=1; long long c[4][4]; long long zx[5]={0,0,0,1,-1}, zy[5]={0,1,-1,0,0}; bool hashnum[100000000]; inline bool hash(long long s) { long long h=1,i=1; while(s) { i++; long long k=s%10; s/=10; h=(h*i*233+k)%MOD; } if(!hashnum[h]){ hashnum[h]=1; return 1; } else return 0; } int main() { scanf("%lld",&s); que[head]=s; while(head<=tail) { int x,y; long long u=que[head++]; long long uu=u;if(u==123804765) break; for(register int i=1;i<=3;i++) for(register int j=1;j<=3;j++) { c[i][j]=uu%10; if(c[i][j]==0){ x=i; y=j; } uu/=10; } for(register int i=1;i<=4;i++) { long long xx=x+zx[i],yy=y+zy[i]; if(1<=xx&&xx<=3&&1<=yy&&yy<=3) { swap(c[x][y],c[xx][yy]); long long l=0; for(int j=3;j>=1;j--) for(int k=3;k>=1;k--) l=l*10+c[j][k]; if(hash(l)){ que[++tail]=l; time[tail]=time[head-1]+1; } swap(c[x][y],c[xx][yy]); } } } printf("%lld ",time[head-1]); return 0; }
二、启发式搜索
估价函数：
close[i]=time[i]+cym[i]
time[i]是搜到当前状态已经用的时间
cym[i]表示每个数字到目标状态的曼哈顿距离之和/2
可以看出，close[i]是小于实际步数的，所以搜起来效率高些
//启发式搜索 420ms #pragma GCC optimize(3) #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> using namespace std; const int MOD=23333333; long long s,num; long long data[10000010]; int time[10000010]; int close[10000010]; struct cmp { bool operator()(int a,int b) { return close[a]>close[b]; } }; priority_queue<int,vector<int>,cmp> que; long long c[4][4]; long long zx[5]={0,0,0,1,-1}, zy[5]={0,1,-1,0,0}; bool hashnum[100000000]; inline bool hash(long long s) { long long h=1,i=1; while(s) { i++; long long k=s%10; s/=10; h=(h*i*233+k)%MOD; } if(!hashnum[h]){ hashnum[h]=1; return 1; } else return 0; } int de[9][2]={{2,2},{1,1},{1,2},{1,3},{2,3},{3,3},{3,2},{3,1},{2,1}}; inline int cym(long long tt) //个位数字的笛卡尔距离之和 { int nn[4][4]; for(register int i=0;i<3;i++) for(register int j=0;j<3;j++) { nn[3-i][3-j]=tt%10; tt/=10; } int mark=0; for(register int i=1;i<=3;i++) for(register int j=1;j<=3;j++) mark+=abs(i-de[nn[i][j]][0])+abs(j-de[nn[i][j]][1]); return mark>>1; } int main() { scanf("%lld",&s); data[++num]=s; close[num]=cym(s); que.push(num); int u; while(!que.empty()) { int x,y; u=que.top(); //每次取估价最小的元素 que.pop(); long long uu=data[u];if(uu==123804765) break; for(register int i=1;i<=3;i++) for(register int j=1;j<=3;j++) { c[i][j]=uu%10; if(c[i][j]==0){ x=i; y=j; } uu/=10; } for(register int i=1;i<=4;i++) { long long xx=x+zx[i],yy=y+zy[i]; if(1<=xx&&xx<=3&&1<=yy&&yy<=3) { swap(c[x][y],c[xx][yy]); long long l=0; for(int j=3;j>=1;j--) for(int k=3;k>=1;k--) l=l*10+c[j][k]; if(hash(l)){ data[++num]=l; time[num]=time[u]+1; close[num]=cym(l)+time[num]; //估价 que.push(num); } swap(c[x][y],c[xx][yy]); } } } printf("%lld ",time[u]); return 0; }