poj 1077 解题报告

最近学人工智能，要学A*算法，就重新做这道题经典的8数码问题，传说不做这道题人生不完整呢我之前是用的广搜暴力搞的，不过太慢了，还要说说我的hash方法，我是用康托展开来hash的，这个东西是算一个排列在所有排列大小排多少，比如（1,2,3）有6个排列，321是最大的就是第六个。还有就是康托展开的逆运算，就是知道是第几大的，算出这个排列来；

康托展开：

Problem: 1077 User: 925695531Memory: 2404K Time: 547MSLanguage: C++ Result: Accepted
Problem: 1077 User: 925695531Memory: 6988K Time: 16MSLanguage: G++ Result: Accepted
Problem: 1077 User: 925695531Memory: 6988K Time: 0MSLanguage: G++ Result: Accepted注释的部分就是被改掉的
#include <iostream>#include <cstring>#include <queue>#include <stack>#include <cmath>using namespace std ;struct Node{    int  pre , h , step ;    char dir     ;    bool vis     ;} node[400000] ;struct cmp{    bool operator () ( int a , int b )    {        //return node[a].h + node[a].step > node[b].h + node[b].step ;        return node[a].h < node[b].h ;    }} ;int  fac[10] ;void  init() ;int   cantor( int s[] ) ;void  uncantor( int s[] , int num ) ;int   h( int s[]  ) ;bool  AStar( int s[] ) ;int  main(){    int  str[10] , State = 0 ;    char ch ;    init()  ;    for( int i = 0 ; i < 9 ; i ++ )    {        cin >> ch ;        if( ch == 'x' ) str[i] = 9 ;        else str[i] = ch - '0' ;    }    if( AStar( str ) )    {        stack < char > s ;        while( node[State].pre != -1 )        {            s.push( node[State].dir ) ;            State = node[State].pre   ;        }        while( !s.empty() )        {            cout << s.top() ;            s.pop() ;        }        cout << endl ;    }    else cout << "unsolvable" << endl ;    return 0 ;}void  init(){fac[0] = 1 ;for( int i = 1 ; i <= 9 ; i ++ )fac[i] = i * fac[i-1] ;}int  cantor( int s[] )                          //康托展开{    int  num = 0 , t ;    for( int i = 0 ; i < 9 ; i ++ )    {        t = 0 ;        for( int j = i + 1 ; j < 9 ; j ++ )            if( s[i] > s[j] ) t ++ ;        num += fac[9 - i - 1] * t ;    }    return num ;}void uncantor( int s[] , int num )              //逆向康托展开{int  j , t , r ;bool p[10] ;memset( p , 0 , sizeof( p ) ) ;for( int i = 0 ; i < 9 ; i ++ ){t = num / fac[9 - i - 1] + 1 ;num %= fac[9 - i - 1] ;r = 0 , j = 1 ;while( 1 ){if( !p[j] ) r ++ ;if( r == t ) break ;j ++ ;}s[i] = j ; p[j] = 1 ;}}int  h( int s[] )                      //估价函数{    int H = 0 ;    for( int i = 0 ; i < 9 ; i ++ )        //if( s[i] != 9 ) H += abs ( double ( ( s[i] - 1 ) / 3 - i / 3 ) ) +          //                   abs ( double ( ( s[i] - 1 ) % 3 - i % 3 ) ) ;        if( s[i] != 9 && i == s[i] - 1 ) H ++ ;    return H ;}bool AStar( int s[] )                  //A*{    int  str[9] , flag = 0 , i , t ;    memset( node , 0 , sizeof( node ) ) ;    priority_queue< int , vector<int> , cmp > q ;    int  temp = cantor( s )  ;    node[temp].step = 0      ;    node[temp].pre  = -1     ;    node[temp].h    = h( s ) ;    q.push( temp ) ;    while( !q.empty() )    {        temp = q.top() ;        q.pop()        ;        if( temp == 0 ) {            flag = 1 ;            break ;        }        if( node[temp].vis ) continue ;        uncantor( str , temp ) ;        for( i = 0 ; i < 9 ; i ++ ) if( str[i] == 9 ) break ;        if( i != 0 && i != 1 && i != 2 )        {swap( str[i] , str[i-3] ) ;t = cantor( str ) ;if( !node[t].pre ){node[t].pre  = temp                ;node[t].step = node[temp].step + 1 ;node[t].h    = h( str )            ;node[t].dir  = 'u'                 ;q.push( t ) ;}swap( str[i] , str[i-3] ) ;        }        if( i != 6 && i != 7 && i != 8 )        {swap( str[i] , str[i+3] ) ;t = cantor( str ) ;if( !node[t].pre ){node[t].pre  = temp                ;node[t].step = node[temp].step + 1 ;node[t].h    = h( str )            ;node[t].dir  = 'd'                 ;q.push( t ) ;}swap( str[i] , str[i+3] ) ;        }        if( i != 0 && i != 3 && i != 6 )        {swap( str[i] , str[i-1] ) ;t = cantor( str ) ;if( !node[t].pre ){node[t].pre  = temp                ;node[t].step = node[temp].step + 1 ;node[t].h    = h( str )            ;node[t].dir  = 'l'                 ;q.push( t ) ;}swap( str[i] , str[i-1] ) ;        }        if( i != 2 && i != 5 && i != 8 )        {swap( str[i] , str[i+1] ) ;t = cantor( str ) ;if( !node[t].pre ){node[t].pre  = temp                ;node[t].step = node[temp].step + 1 ;node[t].h    = h( str )            ;node[t].dir  = 'r'                 ;q.push( t ) ;}swap( str[i] , str[i+1] ) ;        }    }    return flag ;}