如果目標也已知的話，用雙向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，錯誤的，事實是3，S-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，節點要用靜態數組?。。?br>    之前每次都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 *p = 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
用變進制判重會快點...