从“八数码”走进搜索
八数码是经典的搜索问题这已经是众所周知的 。
今天一天就做了这一个问题，感觉挺有收获的，于是想写点心得。
先来看下题目：
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，在此留下一笔，作为成长的痕迹……
2009年10月07日 05:44
让我想起了Linux内核的BFS补丁，BFS=Brain Fuck Scheduler
2023年4月21日 20:44
Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general public interest. ekhan.in ekhan is a initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general public interest.