A*算法求八数码问题总结 最近在PKU的ACM上做了八数码问题，将经验总结以下： （1） 用A*算法， 估价函数选“Hamilton距离”比选用“在错误方各内的数字数目”强很多。 （2）A*算法的关键是要能够使“找到耗费最小的节点”和“判断是否子节点已经存在”的算法的效率尽可能高，为此，网上不少资料建议采用Binary Heap或Hash table等数据结构，然而单独使用任何一种数据结构，都有一定的缺陷，将Heap和Hash联合起来使用，应该可以提高不少效率。具体如下： 1。建一张Hash表，存放没一个节点的具体信息，如当前状态、父节点在表中的位置等。 2。open表中存放着一些节点，这些节点不同于Hash表中的节点，可以将它理解为是Hash表中节点的索引，它只包含节点的估价和节点在Hash表中的位置，这些节点按估价排列成堆（Heap）。 3。没必要再建一个closed表。 这样，程序的流程就可以写成： 初始化Hash表和open表；  将根节点放入Hash表和open表；  found = false;  while(open表不空) {      从open表中得到耗费最低的节点的索引cur;  // O(1)      从open表中删除耗费最低的节点;  // O(logN)      for 每个cur的子节点now do {           if ( now 是目标节点 ) {                   打印输出;                   found = true;                   结束搜索;           }           if( now 不在Hashtable中 ) {  // O(1)                将now插入Hashtable中;  // O(1)                将now的索引放入open表中;  // O(logN)           } else if( now比Hashtable中的节点优 ) {                  if( 原节点在open表中 ) {  // O(N)                     用now替代原来节点;  // O(1)                     在open中push_heap来更新open表的顺序;  // O(logN)                 }           }       }   }   if( !found ) 输出 "无解"; 可以看到，虽然查找open表中已存在的节点仍然为O(N)， 但是当now已存在时，now比open表中节点优的概率是很小的，事先用O(1)的时间判断，就可以避免用O(N)的时间来查找，从而提高了效率（这很像是CPU的Cache的工作原理）。 具体程序如下： #include <vector>#include <string>#include <iostream>#include <algorithm>#include <cassert>using namespace std;struct OpenNode{ int cost, point; OpenNode(){} OpenNode( int cost, int point ){  this->cost = cost;  this->point = point; }};bool operator<( const OpenNode& a, const OpenNode& b ){ return a.cost > b.cost;}bool operator==(const OpenNode& a, int c){ return a.point == c;} struct HashNode{ char state[3][3]; int g, h, par, dir,x,y; bool used; HashNode(){  used=false; }}; int dx[] = { -1,0,1,0 },dy[] = { 0,1,0,-1 };  // u r d l const int HASH_SIZE = 39999;HashNode List[HASH_SIZE];int factorial[] = {1,1,2,6,24,120,720,5040,40320};/*int hash( char state[3][3] ){int ret = 0;char *p, *q;for(p=&state[0][0];p<=&state[2][2];p++){int cnt = 0;for(q=&state[0][0]; q<p; q++) if( *q<*p ) cnt++;ret += factorial[&state[2][2]-p]*(*p-cnt);}return ret;}*/bool eq( char a[3][3], char b[3][3] ){ for(int i=0;i<3;i++)  for(int j=0;j<3;j++) if( a[i][j]!=b[i][j] ) return false;  return true;}int hash( char state[3][3] ){ char* p = &state[0][0]; int ret = p[0] * 7 + p[1] * 17 + p[2] * 47 + p[3] * 117 + p[4] * 217 + p[5]   * 977 + p[6] * 1299 + p[7] * 5971 + p[8] * 7779; ret %= HASH_SIZE; while( List[ret].used && !eq(List[ret].state , state) )   ret= (ret+1) % HASH_SIZE; return ret;}int h( char state[3][3] ){ int ret = 0; for(int x=0;x<3;x++)  for(int y=0;y<3;y++) if( state[x][y]!=0 )   ret += abs((state[x][y]-1)/3-x) +abs((state[x][y]-1)%3-y);  return ret;}void output( int i ){ string res; while(List[i].dir>=0){  res+= List[i].dir==0?'u':List[i].dir==1?'r':List[i].dir==2?'d':'l';  i = List[i].par; } reverse( res.begin(), res.end() ); cout<<res<<endl;}bool solvable( char state[3][3] ){  int t = 0;  for(char* i=&state[0][0];i<&state[2][2];i++)    for(char* j=i+1;j<=&state[2][2];j++)      if(*i!=0 && *j!=0 && *i>*j) t++;  if(t%2) return false;  return true;}vector<OpenNode> open;int main(){ string init; getline( cin, init ); HashNode now; int cnt=0; for(int i=0;i<init.size();i++) {  if(init[i] == 'x') {   now.state[cnt/3][cnt%3] = 0;   now.x = cnt /3;   now.y = cnt %3;   cnt++;  } else if(init[i]!=' ') {   now.state[cnt/3][cnt%3] = init[i] - '0';   cnt++;  } } if( !solvable(now.state) ) {   cout<<"unsolvable"<<endl;   return 0; } now.g = 0; now.h = h(now.state); now.par = -1; now.dir = -1; now.used = true; int i = hash(now.state); List[i] = now; open.push_back(OpenNode(now.g+now.h,i)); while(!open.empty()){  int cur = open.front().point;  pop_heap( open.begin(), open.end() );  open.erase( open.end()-1 );  for(int i=0;i<4;i++){   now = List[cur];   int x = now.x+dx[i];   int y = now.y+dy[i];   if(x<0||x>2||y<0||y>2) continue;   swap( now.state[x][y], now.state[now.x][now.y] );   now.x = x;   now.y = y;   now.h = h( now.state );   now.g++;   now.par = cur;   now.dir = i;      int hashcode = hash( now.state );   if( now.h == 0 ){    List[hashcode] = now;    output( hashcode );    return 0;   } else if( !List[hashcode].used ){    List[hashcode] = now;    open.push_back( OpenNode(now.h+now.g,hashcode) );    push_heap( open.begin(), open.end() );   } else if( List[hashcode].g+List[hashcode].h > now.g+now.h ){    List[hashcode] = now;    vector<OpenNode>::iterator it = find( open.begin(), open.end(), hashcode );    if(it==open.end()) continue;    push_heap( open.begin(), it+1 );   }  } } cout<<"unsolvable"<<endl; return 0;}

评论