学步园

转自http://www.cppblog.com/Yuan/archive/2011/02/23/140553.html  有个地方觉得不合适，修改了下~~

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

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

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

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

            扩展正向一个节点

           遇到反向已经扩展的return

        扩展反向一个节点      

            遇到正向已经扩展的return      

      }

但这种做法是有问题的，如下面的图：

求S-T的最短路，交替节点搜索（一次正向节点，一次反向节点）时

Step 1 : S –> 1 ,

Step 2 : T –> 3 ,

Step3 ：S->2

Step4： T->4

Step 5 : 1 –> 5

Step 6: 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;