a*算法
这里用八数码问题做样例：
1.康托展开判重
2.openlist存待拓展的状态，closelist存已拓展的状态，len1表示openlist(简称ol)的长度（不真实），len2表示closelis（简称cl）t的真实长度，real存openlist的真实长度。
visit[i]表示i状态是否被转移过，inclose[i]表示i状态是否在closelist中。
3.对于h(i)函数，用各个数字到目标状态的曼哈顿距离之和来求。
4.a*的具体步骤：
a.初始状态为from，则在ol中加入from,将ol[1].g=0,ol[1].p=-1(寻找答案路径的终点||其实可以不用)，ol[1].h=0(可为任意值)
b.重复一下步骤直至real=0
(1).取出ol[i]中ol[i].g+ol[i].h且inclose[i]=0最小的状态i;
(2).拓展i的状态
如果visit[j]==0,则拓展j并计算其g值，h值
如果visit[j]==1同时inclose[j]==1,跳过
如果visit[j]==1同时inclose[j]==0,则更新j的g值
(3).将i加入到cl中,并将inclose[i]赋值成1,如果i是目标状态则输出i的g值,跳出
c.如果real=0,则没有答案.
d.结束.
5.对于大佬来说inclose数组其实可以用堆优化代价.蒟蒻在这里就不加以介绍了。
6.代码（努力构建中......）
期望的得分：tle 0
#include<cmath> #include<cstdio> #include<iostream> using namespace std; struct tonod{ int g,h,k; long long n; }ol[4000000],cl[1000000]; struct pair{ int x,y; }w[10]; int visit[1000000],len1=1,len2=0,real=1; bool ic[4000000]; long long from; long long bas[10]={1,1,2,6,24,120,720,5040,40320,362880},a[9]={1,10,100,1000,10000,100000,1000000,10000000,100000000}; int cantor(long long x) { int wei[10]; for(int i=1;i<=9;i++) wei[i]=x/a[9-i]%10; int ans=0; for(int i=1;i<=9;i++) { int tmp=0; for(int j=i+1;j<=9;j++) if(wei[j]<wei[i]) tmp++; ans+=tmp*bas[9-i]; } return ans; } int geth(long long x) { int h=0,top=1; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) { h+=abs(w[x/a[9-top]%10].x-i)+abs(w[x/a[9-top]%10].y-j); top++; } return h; } void up(int k) { int xx=ol[k].k; if(xx-3<1) return; long long x=ol[k].n; int wei=x/a[9-(xx-3)]%10; x=x-wei*a[9-(xx-3)]+wei*a[9-xx]; int tmp=cantor(x); if(visit[tmp]==0) { len1++; real++; visit[tmp]=len1; tonod c; c.k=xx-3; c.n=x; c.g=ol[k].g+1; c.h=geth(x); ol[len1]=c; } else if(!ic[tmp]) { int tmp1=visit[tmp]; if(ol[tmp1].g>ol[k].g+1) ol[tmp1].g=ol[k].g+1; } } void down(int k) { int xx=ol[k].k; if(xx+3>9) return; long long x=ol[k].n; int wei=x/a[9-(xx+3)]%10; x=x-wei*a[9-(xx+3)]+wei*a[9-xx]; int tmp=cantor(x); if(visit[tmp]==0) { len1++; real++; visit[tmp]=len1; tonod c; c.k=xx+3; c.n=x; c.g=ol[k].g+1; c.h=geth(x); ol[len1]=c; } else if(!ic[tmp]) { int tmp1=visit[tmp]; if(ol[tmp1].g>ol[k].g+1) ol[tmp1].g=ol[k].g+1; } } void left(int k) { int xx=ol[k].k; if(xx==1||xx==4||xx==7) return; long long x=ol[k].n; int wei=x/a[9-(xx-1)]%10; x=x-wei*a[9-(xx-1)]+wei*a[9-xx]; int tmp=cantor(x); if(visit[tmp]==0) { len1++; real++; visit[tmp]=len1; tonod c; c.k=xx-1; c.n=x; c.g=ol[k].g+1; c.h=geth(x); ol[len1]=c; } else if(!ic[tmp]) { int tmp1=visit[tmp]; if(ol[tmp1].g>ol[k].g+1) ol[tmp1].g=ol[k].g+1; } } void right(int k) { int xx=ol[k].k; if(xx==3||xx==6||xx==9) return; long long x=ol[k].n; int wei=x/a[9-(xx+1)]%10; x=x-wei*a[9-(xx+1)]+wei*a[9-xx]; int tmp=cantor(x); if(visit[tmp]==0) { len1++; real++; visit[tmp]=len1; tonod c; c.k=xx+1; c.n=x; c.g=ol[k].g+1; c.h=geth(x); ol[len1]=c; } else if(!ic[tmp]) { int tmp1=visit[tmp]; if(ol[tmp1].g>ol[k].g+1) ol[tmp1].g=ol[k].g+1; } } int main() { scanf("%lld",&from); w[1].x=1;w[1].y=1;w[2].x=2;w[2].y=1;w[3].x=3;w[3].y=1; w[8].x=1;w[8].y=2;w[0].x=2;w[0].y=2;w[4].x=3;w[4].y=2; w[7].x=1;w[7].y=3;w[6].x=2;w[6].y=3;w[5].x=3;w[5].y=3; tonod r; r.g=0;r.h=0;r.n=from; int wei[10]; int k; for(int i=1;i<=9;i++) { wei[i]=from/a[9-i]%10; if(wei[i]==0) { k=i; break; } } r.k=k; ol[1]=r; visit[cantor(from)]=1; while(real!=0) { int minn=99999999,tmp; for(int i=1;i<=len1;i++) if(ol[i].h+ol[i].g<=minn&&!ic[cantor(ol[i].n)]) { tmp=i; minn=ol[i].h+ol[i].g; } up(tmp); down(tmp); left(tmp); right(tmp); cl[++len2]=ol[tmp]; ic[cantor(ol[tmp].n)]=1; real--; if(cl[len2].n==123804765) { printf("%d",cl[len2].g); return 0; } } printf("No Answer!"); }
所以进行dfs优化（状态判重减少，康托展开代价减少，剪枝增加，搜索减少）期望：100
具体思路：
（1）枚举搜索深度k
（2）对于深度为k的进行dfs（剪枝用估价函数的值加上g值，若大于深度k则剪掉）
（3）第一次出的答案即为最优解。
1 #include<cmath>// a* by 八重 樱 2 #include<cstdio> 3 #include<iostream> 4 using namespace std; 5 int ans1=0,num[4][4]; 6 int X,Y; 7 int dx[4]={0,1,-1,0};//横坐标移动 8 int dy[4]={1,0,0,-1};//纵坐标移动 9 int fx[11]={0,1,1,1,2,3,3,3,2};//目标状态的横坐标 10 int fy[11]={0,1,2,3,3,3,2,1,1};//目标状态的纵坐标 11 int geth()//曼哈顿距离求估价函数 12 { 13 int ans=0; 14 for(int i=1;i<=3;i++) 15 for(int j=1;j<=3;j++) 16 if(num[i][j]) 17 ans+=abs(i-fx[num[i][j]])+abs(j-fy[num[i][j]]); 18 return ans; 19 } 20 void dfs(int k,int a,int b,int g)//完美的深搜 k枚举的深度 21 { 22 int h=geth(); 23 if(!h) 24 { 25 ans1=g; 26 return; 27 } 28 if(h+g>k||ans1||g==k)//剪枝 29 return; 30 for(int i=0;i<4;i++) 31 { 32 int c=dx[i]+a; 33 int d=dy[i]+b; 34 if(c>=1&&d>=1&&c<=3&&d<=3) 35 { 36 swap(num[a][b],num[c][d]); 37 dfs(k,c,d,g+1); 38 swap(num[a][b],num[c][d]); 39 } 40 } 41 } 42 int main() 43 { 44 for(int i=1;i<=3;i++) 45 for(int j=1;j<=3;j++) 46 { 47 char s; 48 scanf("%c",&s); 49 num[i][j]=s-'0'; 50 if(!num[i][j]) 51 X=i,Y=j; 52 } 53 for(int k=1;k<=10000;k++) 54 { 55 dfs(k,X,Y,0); 56 if(ans1) 57 { 58 printf("%d",ans1); 59 return 0; 60 } 61 } 62 }
OVER,By Yae Sakura.
