原来粗略的考虑，h函数选各个数码离目标位置的最短距离的和，原则上是可行的，但启发性不大，举个简单例子： {2,1,3, 8,0,4, 7,6,5} 和目标状态只差1和2的位置交换一下就对了，h函数给出的估计值只有2，实际上却差得太远，如果你小时候有玩过这样的‘数字拼盘’游戏，就会知道，像这样的是没有解的，至少那时候的感觉是这样，就算有解，也需要移很多次。 基于这样的h函数，感觉启发性不够，在海量搜索的时候效果不是很好，像有的CASE，搜到OPEN表+CLOSE表共好几万的结点了还在不停的搜。可见八数码问题有难有易，虽然9!只有三十多万，也比较难搜。 今天写的程序： #include <iostream.h>struct Snode{ int key; int map[9]; int g,f; int last;public: Snode(){key=0;} void TransformIn(const int *d); void TransformOut(int *d);};void Snode::TransformIn(const int *d){ key=0; for(int i=0;i<9;++i)  key=key*9+(map[i]=d[i]);}void Snode::TransformOut(int *d){ for(int i=0;i<9;++i) {  d[i]=map[i]; }}int spath[9][9]={{0},{0,1,2,1,2,3,2,3,4},{1,0,1,2,1,2,3,2,3},{2,1,0,3,2,1,4,3,2},{3,2,1,2,1,0,3,2,1},{4,3,2,3,2,1,2,1,0},{3,2,3,2,1,2,1,0,1},{2,3,4,1,2,3,0,1,2},{1,2,3,0,1,2,1,2,3}};#define MAX_OPEN_LEN 50000#define MAX_CLOSE_LEN 50000Snode OPEN[MAX_OPEN_LEN];int op=0;Snode CLOSE[MAX_CLOSE_LEN];int cp=0;int hFunction(const Snode &node){ int h=0; for(int i=0;i<9;++i) {  h+=spath[node.map[i]][i]; } return h;}inline void swapn(int &a,int &b){ int tmp=a; a=b; b=tmp;}int Astar(const int *d){ static int dp[4]={-3,-1,1,3}; //int data[9]; op=1; cp=0; OPEN[0].TransformIn(d); OPEN[0].g=0; OPEN[0].f=hFunction(OPEN[0]); OPEN[0].last=-1;//root node while(op>0)//OPEN Table not empty {  int i,min,zero,pos,j;  for(min=0,i=1;i<op;++i)//Choose a best  {   if(OPEN[i].f<OPEN[min].f)    min=i;  }  if(OPEN[min].key==54682916)  {   CLOSE[cp++]=OPEN[min];   return 1;  }  //OPEN[min].TransformOut(data);  for(zero=0;zero<9;++zero)  {   if(OPEN[min].map[zero]==0)    break;  }  for(i=0;i<4;++i)  {   if((zero==3 || zero==6) && i==1)    continue;   if((zero==2 || zero==5) && i==2)    continue;   pos=zero+dp[i];   if(pos<0 || pos>8)    continue;   swapn(OPEN[min].map[zero],OPEN[min].map[pos]);   Snode child;   child.TransformIn(OPEN[min].map);   child.g=OPEN[min].g+1;   child.f=child.g+hFunction(child);   child.last=OPEN[min].key;   for(j=0;j<cp;++j)   {    if(CLOSE[j].key==child.key)     break;   }   if(j==cp)//got a new node   {    OPEN[op++]=child;   }   swapn(OPEN[min].map[zero],OPEN[min].map[pos]);  }  CLOSE[cp++]=OPEN[min];// Insert to CLOSE Table  ostream& operator<<(ostream& out,Snode &node);  //cout<<OPEN[min];  cout<<endl<<op<<" "<<cp<<endl;  OPEN[min]=OPEN[--op]; // Delete from OPEN Table } return 0;}ostream& operator<<(ostream& out,Snode &node){ int data[9]; node.TransformOut(data); for(int i=0;i<3;++i) {  for(int j=0;j<3;++j)   out<<data[i*3+j];  out<<endl; } out<<"g="<<node.g<<endl    <<"f="<<node.f<<endl<<endl; return out;}void OutputSolution(){ cout<<"Succeed!\n";}int main(void){ int map[9]={ 2, 8, 3, 1, 0, 4, 7, 6, 5 };//{1,3,4,2,8,6,5,7,0};//{6,4,7,8,5,0,3,2,1};//{1,2,3,4,5,6,7,8,0};//{2,8,3,1,0,4,7,6,5};//{1,3,4,0,6,2,8,7,5}; if(Astar(map))  OutputSolution(); else  cout<<"no solution!\n"; return 0;} 现在想到的改进的地方就是把CLOSE表做成哈希表，因为当CLOSE表很大的时候花在它身上的查找会很费时，h函数还要改进。 另外今天找到一篇文章，讲如何判定‘八数码问题’是否有解的一个简单方法，非常巧妙，源处不能复制，无法转载。 判别方法是：将八数码的一个结点表示成一个数组a[9]，空格用0表示，设函数p(x)定义为：x数所在位置前面的数比x小的数的个数，其中0空格不算在之内，那设目标状态为b[9]，那r=sigma(p(x)) sigma()表示取所有的x:1-8并求和，那对于初始状态a[9]，t=sigma(p(x))，如果r和t同为奇数或者同为偶数，那么该状态有解，否则无解。 具体证明我不写了，是考虑到四种移动方法对sigma(p(x))的影响，左移和右移是不会影响它的值的，更不会影响奇偶性，如果是上移或者下移就会影响： 上移，一次上移会使一个元素向前跳两个数字的位置，设这两个数字为a1,a2，不妨设a1<a2，移的这个数字设为a0，那无非只有以下三次情况：1，a0<a1<a2，考虑它们三者的p(x)值，p(a0)不变，p(a1)++，p(a2)++，总体增加了22，a1<a0<a2，p(a0)--,p(a1)不变,p(a2)++，总体不变3，a1<a2<a0，p(a0)-=2,p(a1),p(a2)不变，总体减小了2 综合起来的结论就是不会影响sigma(p(x))的奇偶性。

评论