http://poj.org/problem?id=1077
今天看了A*搜索算法，听说牛逼的很，不过关键还是在于它的评估函数，估计也不一定每题都能这么容易想吧
思路是在一个外国游戏网站上看到的，感觉百度到的也都一般http://theory.stanford.edu/~amitp/GameProgramming/
就代码来说吧，s，存储所有所搜到的结点的信息，包括空格位置，深度及评估值，这里不给出h是因为h一直在变，b存储开始结点信息，visited存储是否访问到，接下来方向，答案，heap是为了提速而写的堆实现的优先队列，nali是为了区别出是否入队
整个过程：1，开始结点初始化，入队列并判断是否为目标，是就输出，结束
2，取出队中优先级即f最小的结点 ，进行扩展
3，各个可扩展出来的结点，先求哈希值，判重，如果重复，并还在队列中，就保留优先级较小的那个
4，如果没重复就入队
5，判断是否为目标，是就输出，结束；否则回到2
代码
#include<stdio.h> #include<stdlib.h> #include<string.h> #define SIZE 400000 struct node { char str[10]; int k;//空格位置 int g,f;//深度及估价 int fa,fx;//父节点及方向 }s[400000],b; int visited[400000],dir[4]={-3,3,-1,1},ans[400000],found;//0上1下2左3右, int f[8]={1, 2, 6, 24, 120, 720, 5040, 40320}; int heap[400000],hlength,nali[400000];//nali中存储在哪里，0表示没在队里，1表示在队列里 char end[10]={"123456780"}; void down(int p)//删除后向下调整 { int a,q=p*2; a=heap[p];//保存当前结点的值 while(q<=hlength) { if(q<hlength&&s[heap[q]].f>s[heap[q+1]].f)//选择两个子结点中的一个最小的 q++; if(s[heap[q]].f>=s[a].f)//如果子结点比当前结点大，就结束 break; else { heap[p]=heap[q]; p=q;q=p*2; } } heap[p]=a;//还原原来的点 } int min() { int r=heap[1]; heap[1]=heap[hlength--]; down(1); return r; } void up(int p)//插入后向上调整 { int q=p/2,a;//q是父节点 a=heap[p]; while(q>0&&s[a].f<s[heap[q]].f)// { heap[p]=heap[q];//如果父节点结点比当前结点大就交换 p=q;q=p/2; } heap[p]=a;//还原原来的点 } void insert(int a) { heap[++hlength]=a; up(hlength); } int hx(char str[])//计算h(x)函数值，计算当前状态下还未达到正确位置的个数 { int i=0,j=0; for(;i<9;i++) if(str[i]!=end[i]) j++; return j; } int get(char str[]) //计算全排列哈希值 { int i, j; int ret = 0, cnt; for(i = 1; i < 9; ++i) { cnt = 0; for(j = 0; j < i; ++j) if(str[j] > str[i]) cnt++; ret += cnt*f[i-1]; } return ret; } void print(int x)//若发现可完成，则利用父节点逐个输出 { int top; //printf("find "); top=0; while (x!=s[x].fa) { top++; ans[top]=s[x].fx; x=s[x].fa; } while (top!=0) { switch (ans[top]) { case 0:printf("u");break; case 1:printf("d");break; case 2:printf("l");break; case 3:printf("r");break; default:break; } top--; } printf(" "); } void abfs() { int x=min();//min（）函数取最小的那个 int h,g,k,i,hash; char a[10],temp; nali[x]=0; if(strcmp(s[x].str,end)==0) {print(x);found=1;return ;} for(i=0;i<4;i++) { if(i==0&&s[x].k<3)continue; if(i==1&&s[x].k>5)continue; if(i==2&&s[x].k%3==0)continue; if(i==3&&s[x].k%3==2)continue; k=s[x].k+dir[i]; if(k<0||k>8)continue; strcpy(a,s[x].str); temp=a[k]; a[k]=a[s[x].k]; a[s[x].k]=temp; hash=get(a);/*取哈希值*/ h=hx(a); /*求对应的估价*/ g=s[x].g+1; if(visited[hash]==1) { if(nali[hash]==1&&s[hash].f>(h+g)) {s[hash].f=h+g; s[hash].g=g; s[hash].k=k; s[hash].fx=i; s[hash].fa=x;}//当出现了还在队列中未出列的，保留f较小的那个 continue; } else if(visited[hash]==0) { strcpy(s[hash].str,a);/*不曾出现的情况下，记得进队*/ s[hash].f=h+g; s[hash].g=g; s[hash].k=k; s[hash].fx=i; s[hash].fa=x; insert(hash); visited[hash]=1; nali[hash]=1; } if(strcmp(s[hash].str,end)==0) { print(hash); found=1; return ; } } } int Astar() { int x=get(b.str),i=0; memset(visited,0,sizeof(visited));//初始化为0，未访问 memset(nali,0,sizeof(nali));//初始化为0，未访问 memset(heap,0,sizeof(heap)); hlength=0; s[x].fa=x;s[x].k=b.k;strcpy(s[x].str,b.str);s[x].g=0;s[x].f=7; insert(x); visited[x]=1; nali[x]=1; while(hlength!=0) { abfs(); if(found)return 1; } } int main() { int i,m,j; char a[100]; while(gets(a)!=NULL) { j=0; for(i=0;i<strlen(a);i++) { if(a[i]==' ')continue; if(a[i]=='x') { a[j]='0'; m=j; j++; }else a[j++]=a[i]; } a[j]=' '; strcpy(b.str,a); b.k=m; found=0;//标志变量初始化 //printf("m=%d %s ",b.k,b.str); Astar(); if(found==0) printf("unsolvable "); } //system("pause"); return 0; }