xhSong's Blog

八数码是经典的搜索问题这已经是众所周知的 。

今天一天就做了这一个问题，感觉挺有收获的，于是想写点心得。

先来看下题目：

http://acm.pku.edu.cn/JudgeOnline/problem?id=1077

最先想到的是直接BFS，这也是最简单的想法。但一开始就遇到了一个公共的问题（为什么说是公共的问题呢。因为不管你用什么方式的搜索都会遇到的）——如何判重。最简单的就是直接将棋盘转化成一个9位的十进制数。但这用什么数据结构呢？数组，10^9！这个内存是不允许的；用set，这个时间是不允许的。后面听勇哥说，全排是有完美的hash函数的，于是在网上找到这个——http://bbs3.chinaunix.net/viewthread.php?tid=1283459，这上面解释得很清楚。于是按照上面的hash方法写了个单向的BFS，附：

#include <cstdio>
#include <cstring>

struct node {
    int pre; //上一个节点和如何变换的信息
	int p; // x即9的下标
    char ch[10];//用于记录棋盘信息
}st[400000];
//队列数组 ，9！= 362880

bool vis[400000];//判重数组

int perm[] = {1,1,2,6,24,120,720,5040,40320};//n！
int d[] = { -1 , -3, 1, 3};//四个方向的下标变换
bool move[][4] = {0,0,1,1, 1,0,1,1, 1,0,0,1, 0,1,1,1, 1,1,1,1, 1,1,0,1, 0,1,1,0, 1,1,1,0, 1,1,0,0};
//各个位置的可行变换

int hash(char x[])//用逆序数和变进制进行hash
{
    int h = 0;
    for(int i = 1;i<9;i++){
        int count = 0;
        for(int j=0;j<i;j++)
            if(x[j] > x[i])count ++;
        h += count * perm[i];
    }
    return h;
}

bool end (char x[])//判断是否到目标状态
{
    for(char i = 0;i<9;i++){
        if(x[i] != i + '1') return false;
    }
    return true;
}

int BFS(char *num,int p)
{
    int left ,right;
    left = right = 1;
    memset(vis,0,sizeof(vis));
    strcpy(st[right].ch,num);
    st[right].p = p;
    st[right ++].pre = 0;
    vis[hash(st[left].ch)] = 1;
    while(left < right){
        int p1 ,p2 ;
        p1 = st[left].p;
        for(int i = 0 ;i<4;i++)if(move[p1][i]){
            p2 = st[right].p = p1 + d[i];
            strcpy(st[right].ch,st[left].ch);
            char tp = st[right].ch[p2] ;
            st[right].ch[p2] = st[right].ch[p1] ;
            st[right].ch[p1] = tp ;
            st[right].pre = left << 2 | i;//将上一个节点的下标和变换规则压进一个数字
            if(end(st[right].ch)) return st[right].pre;
            int key = hash(st[right].ch);
            if( ! vis[key] ) { vis[key] = 1 ; right ++;}
        }
        left ++;
    }
    return -1;
}


int main()
{
    char num[10] ,der[]="lurd",step[100];
    int p ;
    for(int i =0 ;i<9;){
        num[i] = getchar();
        if(num[i] == 'x') { num[i] = '9' ; p = i; }//将x转化成'9'，这样便于hash，和判结束
        if(num[i]<='9' && num[i]>='1') i++;
    }
    num[9] = '\0';
    int i = 0;
    if(!end(num)){
        int k = BFS(num,p);
        if( k == -1)  printf("unsolvable");
        else {
            while(k){
                step[ ++ i] = der[k&3];
                k = st[k>>2].pre;
            }
            for(;i>0;i--) putchar(step[i]);
            puts("");
        }
    }
    return 0;
}

在知道初状态（输入）和末状态（12345678x）的情况下还可以用双向BFS，无论从空间还是从时间的复杂度来说，双向BFS都是比单向BFS都优。单向的BFS的时间和空间都是k^n级的，k是一个状态分支的个数，这里理论是 k = 4，实际上2到3之间，n是迭代的层数，双向BFS的时间和空间的复杂度都是k^(n/2)级的。就是双向BFS的代码复杂度要高一些。在poj上单向BFS是4104K 266MS 2067B，双向BFS是1280K 16MS 2589B

附：双向BFS代码

#include <cstdio>
#include <cstring>
#define M 400000
struct node {
    int pre,p；
	int key; //这个节点状态对应的hash值
    char ch[10];
}st[2][M];

bool vis[2][M];

int perm[] = {1,1,2,6,24,120,720,5040,40320};
int d[] = { -1 , -3, 1, 3};
bool move[][4] = {0,0,1,1, 1,0,1,1, 1,0,0,1, 0,1,1,1, 1,1,1,1, 1,1,0,1, 0,1,1,0, 1,1,1,0, 1,1,0,0};

int hash(char x[])
{
    int h = 0;
    for(int i = 1;i<9;i++){
        int count = 0;
        for(int j=0;j<i;j++)
            if(x[j] > x[i])count ++;
        h += count * perm[i];
    }
    return h;
}

int BFS(char *num,int p)
{
    int l[2] ,r[2] ,key;
    l[0] = l[1] = r[0] = r[1] = 1;
    memset(vis,0,sizeof(vis));

    strcpy(st[0][r[0]].ch,num);
    st[0][r[0]].p = p;
    st[0][r[0]].pre = 0;
    key = hash(st[0][l[0]].ch);
    vis[0][key] = 1;
    st[0][r[0] ++].key = key;

    strcpy(st[1][r[1]].ch,"123456789");
    st[1][r[1]].p = 8;
    st[1][r[1]].pre = 0;
    key = hash(st[1][l[1]].ch);
    vis[1][key] = 1;
    st[1][r[1] ++].key = key;

    while(l[0] < r[0] && l[1]<r[1]){
        int p1 ,p2 ,now = (r[0] - l[0] > r[1] - l[1]);//将节点少的一边进行扩展
        p1 = st[now][l[now]].p;
        for(int i = 0 ;i<4;i++)if(move[p1][i]){
            p2 = st[now][r[now]].p = p1 + d[i];
            strcpy(st[now][r[now]].ch,st[now][l[now]].ch);
            char tp = st[now][r[now]].ch[p2] ;
            st[now][r[now]].ch[p2] = st[now][r[now]].ch[p1] ;
            st[now][r[now]].ch[p1] = tp ;
            st[now][r[now]].pre = l[now] << 2 | i;
            key = hash(st[now][r[now]].ch);
            st[now][r[now]].key = key;
            if( ! vis[now][key] ) { vis[now][key] = 1 ; r[now] ++;}
            if( vis[1-now][key]) return key;//检测当前扩展的状态在另一边是否已出现，
        }
        l[now] ++;
    }
    return -1;
}


int main()
{
    char num[10] ,der[]="lurd",step[100];
    int p ;
    for(int i =0 ;i<9;){
        num[i] = getchar();
        if(num[i] == 'x') { num[i] = '9' ; p = i; }
        if(num[i]<='9' && num[i]>='1') i++;
    }
    num[9] = '\0';
    int i = 0;
    int k = BFS(num,p);
    if( k == -1)  printf("unsolvable\n");
    else {
        int p = 1;
        while(st[0][p].key != k) p++;
        p = st[0][p].pre ;
        while(p){
            step[ ++ i] = der[p&3];
            p = st[0][p>>2].pre;
        }
        for(;i>0;i--) putchar(step[i]);
        p = 1;
        while(st[1][p].key != k) p++;
        p = st[1][p].pre;
        while(p){
            putchar(der[((p & 3) + 2)%4]);
            p = st[1][p>>2].pre;
        }
        puts("");
    }
    return 0;
}

这道题目还可以用A*来写，原来看过这方面的书籍，还没用自己动手写过A*，于是尝试着写了写。这里用搜索树的深度做g(s)，用但前状态各个字符和目标状态这个字符的哈密尔顿距离之和做f(s)，这里做了个比较危险的假设：我把路径压缩在一个long long 中，一个变换只有4种可能，用2个bit就能保存了，大家都知道long long 占64个bit，所以最多可以存32个变化，也就是说，一个long long 只能保存一天短于32的路径（不知道这样描述是否清楚）。我假设，对于任何状态，变到目标状态至多的步数不会超过32步（无解的状态除外），就像3阶魔方被证明20+步一定能被搞定一样，（如果哪个神牛能证明一下就好了……）。

同样这里也贴出代码（就不注释了，如果有没理解的发邮件给我吧，hustsxh@gmail.com）：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>

struct node {
    long long path;
    char ch[10];
    int g,f,p;
    bool operator <(const node & a)const{
        return f>a.f || f==a.f &&  g > a.g;
    }
};

bool vis[400000];

int perm[] = {1,1,2,6,24,120,720,5040,40320};
int d[] = { -1 , -3, 1, 3};
bool move[][4] = {0,0,1,1, 1,0,1,1, 1,0,0,1, 0,1,1,1, 1,1,1,1, 1,1,0,1, 0,1,1,0, 1,1,1,0, 1,1,0,0};

int hash(char x[])
{
    int h = 0;
    for(int i = 1;i<9;i++){
        int count = 0;
        for(int j=0;j<i;j++)
            if(x[j] > x[i])count ++;
        h += count * perm[i];
    }
    return h;
}

bool end (char x[])
{
    for(char i = 0;i<9;i++){
        if(x[i] != i + '1') return false;
    }
    return true;
}

int h(char x[])
{
    int h = 0;
    for(int i=0;i<9;i++){
        h += abs( '1' + i -x[i]);
    }
    return h;
}

int Astar(char num[],int p,long long & path)
{
    memset(vis,0,sizeof(vis));
    std::priority_queue <node> c;
    node start ;
    strcpy(start.ch,num);
    start.path = 0;
    start.p = p;
    start.g = 0;
    start.f = start.g + h(start.ch);
    vis[hash(start.ch)] = 1;
    c.push(start);
    while(!c.empty()){
        node next, pre = c.top();
        c.pop();
        for(int i = 0;i<4;i++)if(move[pre.p][i]){
            next.p = pre.p + d[i];
            next.g = pre.g + 1;
            strcpy(next.ch,pre.ch);
            next.ch[pre.p] = next.ch[next.p];
            next.ch[next.p] = '9';
            next.path = pre.path<<2 | i;
            next.f = h(next.ch) + next.g ;
            if(end(next.ch)) { path = next.path ; return next.g;}
            int key = hash(next.ch);
            if(!vis[key]) { vis[key] = 1; c.push(next); }
        }
    }
    return -1;
}

int main()
{
    char num[10] ,der[]="lurd",step[100];
    int p ;
    for(int i =0 ;i<9;){
        num[i] = getchar();
        if(num[i] == 'x') { num[i] = '9' ; p = i; }
        if(num[i]<='9' && num[i]>='1') i++;
    }
    num[9] = '\0';
    int i = 0;
    if(!end(num)){
        long long path ;
        int k = Astar(num,p,path);
        if( k==-1) printf("unsolvable\n");
        else {
            for(int i = k-1;i>=0;--i) {
                step[i] = der[path&3];
                path = path >>2;
            }
            step[k] = '\0';
            puts(step);
        }
    }
    return 0;
}

 估计是我写得不够优，在poj的的各个参数是1012K 47MS 2459B

 从八数码中学到了一个精妙、完美的hash，第一次写双向BFS，第一次写A*，而且交了三份代码三份代码都是1Y的，很hanppy，在此留下一笔，作为成长的痕迹……