如果目标也已知的话,用双向BFS能很大提高速度

单向时,是 b^len的扩展。

双向的话,2*b^(len/2)  快了很多,特别是分支因子b较大时

至于实现上,网上有些做法是用两个队列,交替节点搜索 ×,如下面的伪代码:
    while(!empty()){

            扩展正向一个节点

           遇到反向已经扩展的return

        扩展反向一个节点      

            遇到正向已经扩展的return      

      }

但这种做法是有问题的,如下面的图:


S-T的最短路,交替节点搜索(一次正向节点,一次反向节点)时

Step 1 : S –> 1 , 2

Step 2 : T –> 3 , 4

Step 3 : 1 –> 5

Step 4 : 3 –> 5   返回最短路为4,错误的,事实是3S-2-4-T


 

我想,正确做法的是交替逐层搜索,保证了不会先遇到非最优解就跳出,而是检查完该层所有节点,得到最优值
也即如果该层搜索遇到了对方已经访问过的,那么已经搜索过的层数就是答案了,可以跳出了,以后不会更优的了。
当某一边队列空时就无解了。

 

优化:提供速度的关键在于使状态扩展得少一些,所以优先选择队列长度较少的去扩展,保持两边队列长度平衡。这比较适合于两边的扩展情况不同时,一边扩展得快,一边扩展得慢。如果两边扩展情况一样时,加了后效果不大,不过加了也没事。

无向图时,两边扩展情况类似。有向图时,注意反向的扩展是反过来 x->y(如NOIP2002G2字串变换)




Code

void gao(vector<int> &from , vector<int> &to , Hash &hash){
    to.clear();
    
for(vector<int>::iterator it = from.begin() ; it != from.end() ; it++)
{
        利用hash判重,扩展
*
it            
    }

}

int bibfs(int start , int dest){
    
if(start == dest)
//注意要先判相等
        return 0;
    }


    Hash bfs , rbfs;
    bfs[start] 
= 0;
    rbfs[dest] 
= 0
;

    vector
<int> Q[2] , rQ[2]; //用vector做队列,方便遍历

    int cur = 0 , rcur = 0;
    Q[cur].push_back(start);
    rQ[rcur].push_back(dest);

    
for(int step = 1 ; step <= limit && !Q[cur].empty() && !rQ[rcur].empty();  step++)
{
        
//cout<<step<<endl;

        if(Q[cur].size() <= rQ[rcur].size()){//优先扩展队列长度小的
            gao(Q[cur],Q[cur^1],bfs);
            cur 
^= 1
;
            
for(vector<int>::iterator it = Q[cur].begin() ; it != Q[cur].end() ; it++)
{
                
if(rbfs.find(*it) != rbfs.end())
{
                    
return
 step;
                }

            }

        }
else{
            gao(rQ[rcur],rQ[rcur
^1
],bfs);
            rcur 
^= 1
;
            
for(vector<int>::iterator it = rQ[rcur].begin() ; it != rQ[rcur].end() ; it++)
{
                
if(bfs.find(*it) != bfs.end())
{
                    
return
 step;
                }

            }

        }

    }

    
return -1;
}



 

我用这种做法,做了几道题,都没错,速度还行。

按难度递增:
 

hdu 1195

NOIP2002G2字串变换   注意反向的扩展是反过来

ZOJ 1505

ZOJ 3467

/*
    3维中,求点(x0,y0,z0)到(x1,y1,z1)不超过步字典序最小的路径
    一步能跳(x,y,z)  组合一下有!*8 = 48种
    48^6太大了
    双向BFS 2*48^3

    参照watashi的代码写的
    STL真神奇
    vector重载了比较运算符的
    typedef map<Point , vector<Point> > Hash;

    一层一层,这样才保证正确解
    这里由于两边结构差不多,所以判断队列长度的优化效果不大
    细节较多
    我写得较挫
*/

struct Point{
    
int x , y , z;
    Point()
{}
    Point(
int x,int y , int z):x(x),y(y),z(z){}

    
bool operator < (const Point &B)const{
        
if(x != B.x){
            
return x < B.x;
        }
else if(y != B.y){
            
return y < B.y;        
        }
else{
            
return z < B.z;
        }

    }

    
bool operator == (const Point &B)const{
        
return x == B.x && y == B.y && z == B.z;
    }

    Point 
operator +(const Point &B)const{
        
return Point(x+B.x , y+B.y, z+B.z);
    }

}
;

typedef map
<Point , vector<Point> > Hash;
vector
<Point> dir;

void init(int x ,int y , int z){
    
int d[] = {x, y, z};
    sort(d,d
+3);
    dir.clear();
    
do{
        
for(int mask = 0 ; mask < 8 ; mask ++){
            
int nx = (mask & 1? d[0] : -d[0];
            
int ny = (mask & 2? d[1] : -d[1];
            
int nz = (mask & 4? d[2] : -d[2];
            dir.push_back(Point(nx,ny,nz));
        }

    }
while(next_permutation(d,d+3));
}


void gao(vector<Point> &from , vector<Point> &to , Hash &bfs){
    to.clear();
    
int len = bfs[*from.begin()].size();
    
for(vector<Point>::iterator it = from.begin() ; it != from.end() ; it++){
        Hash::iterator  preIt 
= bfs.find(*it);
        
for(int k = 0 ; k < 48 ; k++){
            Point next 
= *it + dir[k];
            Hash::iterator  nextIt 
= bfs.find(next);
            
if(nextIt == bfs.end()){
                bfs[next] 
= preIt->second;
                to.push_back(next);
            }
else if(!(nextIt->second.front() == next || nextIt->second.back() == next) //注意需要判断这个,因为长度=len的可能是之前的
                && nextIt->second.size() == len && nextIt->second > preIt->second){
                nextIt
->second = preIt->second;
            }

        }

    }

}


void bibfs(vector<Point> &ans , Point &start , Point &dest){
    
if(start == dest){
        ans.push_back(start);
        
return;
    }


    Hash bfs , rbfs;
    bfs[start].push_back(start);
    rbfs[dest].push_back(dest);

    vector
<Point> Q[2] , rQ[2];    
    
//for(int i = 0 ; i < 2 ; i ++){
    
//    Q[i].reserve(1000);
    
//    rQ[i].reserve(1000);
    
//}
    int cur = 0 , rcur = 0;
    Q[cur].push_back(start);
    rQ[rcur].push_back(dest);
    
for(int step = 0 ; ans.empty() && !Q[cur].empty() && step < 6 ; step++){
        
if(Q[cur].size() <= rQ[cur].size()){
            gao(Q[cur],Q[cur
^1],bfs);
            cur 
^= 1;
            
//chk
            for(int i = 0 ; i < Q[cur].size() ; i++){
                Point 
&val = Q[cur][i];
                Hash::iterator fit 
= bfs.find(val);
                Hash::iterator rfit 
= rbfs.find(val);
                
if(rfit != rbfs.end()){
                    vector
<Point> tmp = fit->second;                    
                    tmp.insert(tmp.end() , rfit
->second.begin(), rfit->second.end());
                    
if(ans.empty() || tmp < ans){
                        ans 
= tmp;
                    }

                }

                fit
->second.push_back(val);//push                
            }

        }
 else {
            gao(rQ[rcur],rQ[rcur
^1],rbfs);
            rcur 
^= 1;
            
//chk
            for(int i = 0 ; i < rQ[rcur].size() ; i++){
                Point 
&val = rQ[rcur][i];
                Hash::iterator rfit 
= rbfs.find(val);
                Hash::iterator fit 
= bfs.find(val);
                
if(fit != bfs.end()){
                    vector
<Point> tmp = rfit->second;                                    
                    tmp.insert(tmp.begin() , fit
->second.begin() , fit->second.end());
                    
if(ans.empty() || tmp < ans){
                        ans 
= tmp;
                    }

                }

                rfit
->second.insert(rfit->second.begin(),val);//push
            }

        }
        
    }
    
}


int main()
{
    
//freopen("in","r",stdin);
    
//freopen("out","w",stdout);

    
int x0,y0,z0,x1,y1,z1,x,y,z;
    
while(~scanf("%d%d%d%d%d%d%d%d%d",&x0,&y0,&z0,&x1,&y1,&z1,&x,&y,&z)){

        init(x,y,z);

        vector
<Point> ans;
        Point start(x0,y0,z0) , dest(x1,y1,z1);
        bibfs(ans , start , dest);

        printf(
"To get from (%d,%d,%d) to (%d,%d,%d) takes " , x0,y0,z0,x1,y1,z1);
        
if(ans.empty()){
            printf(
"more than 6 3D knight moves (%d,%d,%d).\n",x,y,z);
        }
else{
            printf(
"%d 3D knight moves (%d,%d,%d): ",ans.size()-1,x,y,z);
            
for(int i = 0 ; i < ans.size() ; i++){
                
if(i)printf(" => ");
                printf(
"(%d,%d,%d)",ans[i].x,ans[i].y,ans[i].z);
            }

            puts(
".");
        }
    
    }

    
return 0;
}


Poj 3131

/*
    如图所示,问从初始状态变化到目标状态,不超过步
    规模比较大
    状态总数为:*6^8   1个为E,其余格子每个种可能
    我这里用了enum,这样编码会直观点吧
    用二进制编码,每三位bit代表一个格子

    状态很多,要用双向BFS,优先选择队列长度小的扩展,否则会超时
    还有注意判重时,用了Hash,节点要用静态数组!!!
    之前每次都make_pair()就超时了!!!
    map判重也超时了
*/


enum Board {RBW, BRW, RWB, WRB, BWR, WBR, E};//0,1,
const int MAXN = 500007;

struct Node{
    
int pos;
    
short val;
    Node 
*next;
}
;
Node nodes[MAXN
*20] , *pN;

struct Hash{

    Node
* hash[MAXN];
    vector
<int> vt;

    
void init(){
        
for(vector<int>::iterator it = vt.begin() ; it != vt.end() ; it++){
            hash[
*it] = NULL;
        }

        vt.clear();
    }

    
void add(int pos , short val){
        
int mod = pos % MAXN;
        
if(hash[mod] == NULL){
            vt.push_back(mod);
        }

        pN
->pos = pos;
        pN
->val = val;
        pN
->next = hash[mod];
        hash[mod] 
= pN++;
        
//assert(pN < nodes + MAXN*20);
    }

    
short find(int pos){
        
int loc = pos % MAXN;
        Node 
*= hash[loc];
        
while(p != NULL ){
            
if(p->pos == pos){
                
return p->val;
            }

            p 
= p->next;
        }

        
return -1;
    }

}
;

Hash bfs , rbfs;

int bin[10];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
Board change[
6][4= {
    
{RWB, WBR, RWB, WBR},
    
{BWR, WRB, BWR, WRB},
    
{RBW, BWR, RBW, BWR},
    
{WBR, BRW, WBR, BRW},
    
{BRW, RWB, BRW, RWB},
    
{WRB, RBW, WRB, RBW}
}
;

#define iset(val,pos,x)  (val ^=  val & bin[pos] , val |= x << 3*(pos) )
#define get(val,pos)  ((val >> 3*(pos) ) & 7)

inline 
bool out(int x , int y){
    
return x < 0 || x >= 3 || y < 0 || y >= 3;
}


void gao(vector<int> &from , vector<int> &to , Hash &hash){
    to.clear();
    
for(vector<int>::iterator it = from.begin() ;  it != from.end() ; it++){
        
int &board = *it;
        
int pos , x , y , step = hash.find(board);
        
for(int i = 0 ;i  < 9 ;  i++){
            
if(get(board,i) == E){
                pos 
= i;
                y 
= i / 3;
                x 
= i % 3;
                
break;
            }

        }

        
for(int k = 0 ; k < 4 ; k ++){
            
int xx = x + dx[k];
            
int yy = y + dy[k];
            
if(out(xx,yy)){
                
continue;
            }

            
int next = board;
            
int nextPos = yy * 3 + xx , val = get(next, nextPos);
            iset(next,pos,change[val][k]);
            iset(next,nextPos,E);
            
if(hash.find(next) == -1){
                hash.add(next,step
+1);
                to.push_back(next);
            }

        }

    }

}

int bibfs(int &start , int dest[2]){

    vector
<int> Q[2] , rQ[2];
    
int cur = 0 , rcur = 0;

    pN 
= nodes;
    bfs.init();
    rbfs.init();

    bfs.add(start,
0);
    Q[cur].push_back(start);

    
int pos = 0;
    
while(get(dest[0], pos) != E){
        pos
++;
    }


    
for(int mask = 0 ; mask < (1<<9) ; mask++){        
        
if((mask>>pos) & 1){
            
continue;
        }

        
int next = 0;//init 0 !!!
        for(int i = 0 ;i < 9 ; i ++){
            iset(next, i, 
get(dest[(mask>>i)&1], i) );
        }

        
if(next == start){
            
return 0;
        }

        rbfs.add(next,
0);
        rQ[rcur].push_back(next);
    }


    
for(int step = 1 ; step <= 30 ; step++){
        
if(Q[cur].size() <= rQ[rcur].size()){//
            gao(Q[cur],Q[cur^1],bfs);
            cur 
^= 1;
            
for(vector<int>::iterator it = Q[cur].begin() ; it != Q[cur].end() ; it++){
                
if(rbfs.find(*it) != -1){
                    
return step;
                }

            }

        }
else{
            gao(rQ[rcur],rQ[rcur
^1],rbfs);
            rcur 
^= 1;
            
for(vector<int>::iterator it = rQ[rcur].begin() ; it != rQ[rcur].end() ; it++){
                
if(bfs.find(*it) != -1){
                    
return step;
                }

            }

        }

    }

    
return -1;
}
 

int main()
{
    
//freopen("in","r",stdin);
    
//freopen("out","w",stdout);
    bin[0= 7;
    
for(int pos = 1 ; pos < 9 ; pos++){
        bin[pos] 
= bin[pos-1]<<3;
    }

    
for(int x,y;scanf("%d%d",&x,&y) , x != 0;){
        x
--;
        y
--;
        
int dest[2] , start = 0;
        
for(int i = 0; i < 3 ; i ++){
            
for(int j = 0 ; j < 3 ; j++){
                
char ch;
                scanf(
" %c",&ch);
                
if(ch == 'W'){
                    iset(dest[
0],3*i+j,RBW);
                    iset(dest[
1],3*i+j,BRW);
                }
else if(ch == 'B'){
                    iset(dest[
0],3*i+j,RWB);
                    iset(dest[
1],3*i+j,WRB);
                }
else if(ch == 'R'){
                    iset(dest[
0],3*i+j,BWR);
                    iset(dest[
1],3*i+j,WBR);
                }
else{
                    iset(dest[
0],3*i+j,E);
                    iset(dest[
1],3*i+j,E);
                }

            }

        }

        iset(start, 
3*y+x, E);
        cout
<<bibfs(start , dest)<<endl;
    }

    
return 0;
}



CII 3010
双向bfs很快,能排第3
用变进制判重会快点...