搜索（二）——双向BFS

参考这篇文章，以下前部分为转载：http://www.cppblog.com/Yuan/archive/2011/02/23/140553.aspx

大牛，谢谢！不是你，我还在用交替节点搜索呢:{? ——应该用交替层次搜索

?

如果目标也已知的话，用双向BFS能很大提高速度。
单向时，是 b^len的扩展。双向的话，2*b^(len/2)? 快了很多，特别是分支因子b较大时
至于实现上，网上有些做法是用两个队列，交替节点搜索 ×，如下面的伪代码：
??? while(!empty()){
??????????? 扩展正向一个节点
??????????? 遇到反向已经扩展的return
??????????? 扩展反向一个节点?????
??????????? 遇到正向已经扩展的return?????
??? }
但这种做法是有问题的，如下面的图：

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

?

while(1):

S > 1
T > 3

while(2):

S -> 5

T -> 4

?

while(3):

1 -> 5

3 -> 5?? 返回最短路为4，错误的，事实是3，S-2-4-T

我想，正确做法的是交替逐层搜索，保证了不会先遇到非最优解就跳出，而是检查完该层所有节点，得到最优值。
也即如果该层搜索遇到了对方已经访问过的，那么已经搜索过的层数就是答案了，可以跳出了，以后不会更优的了。
当某一边队列空时就无解了。
?
优化：提供速度的关键在于使状态扩展得少一些，所以优先选择队列长度较少的去扩展，保持两边队列长度平衡。这比较适合于两边的扩展情况不同时，一边扩展得快，一边扩展得慢。如果两边扩展情况一样时，加了后效果不大，不过加了也没事。
无向图时，两边扩展情况类似。有向图时，注意反向的扩展是反过来的 x->y（如NOIP2002G2字串变换）

例题：

POJ1915

#include <stdio.h>#include <stdlib.h>#include <queue>#include <iostream>using namespace std;int l; //4<=l<=300int sx,sy,tx,ty;int a[305][305];//正向搜索层次int b[305][305];//反向搜索层次struct point{int x,y;};struct point dir[]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};bool check(int x,int y){if(x>=0 && x<l && y>=0 && y<l)return true;elsereturn false;}void dbfs(){memset(a,-1,sizeof(a));memset(b,-1,sizeof(b));a[sx][sy]=0;b[tx][ty]=0;queue<point> forQ,backQ;point p1,p2;p1.x=sx;p1.y=sy;p2.x=tx;p2.y=ty;forQ.push(p1);backQ.push(p2);//正反向队列至少还有一个可以扩展while(forQ.empty()==false || backQ.empty()==false){//优化：优先扩展元素少的队列（如果只有一个队列非空，则扩展非空队列）int forSize=forQ.size();int backSize=backQ.size();if(backSize==0 || forSize<backSize){//扩展正向队列一层int i;for(i=0;i<forSize;i++){point cur=forQ.front();forQ.pop();if(b[cur.x][cur.y]!=-1){printf("%d\n",a[cur.x][cur.y]+b[cur.x][cur.y]);return;}int j;for(j=0;j<8;j++){if(check(cur.x+dir[j].x, cur.y+dir[j].y)){point next={cur.x+dir[j].x, cur.y+dir[j].y};//!注意struct的创建方式if(a[next.x][next.y]!=-1)//以前已经正向扩展过continue;a[next.x][next.y]=a[cur.x][cur.y]+1;forQ.push(next);}}}}else{//扩展反向队列一层int i;for(i=0;i<backSize;i++){point cur=backQ.front();backQ.pop();if(a[cur.x][cur.y]!=-1){printf("%d\n",a[cur.x][cur.y]+b[cur.x][cur.y]);return;}int j;for(j=0;j<8;j++){if(check(cur.x+dir[j].x, cur.y+dir[j].y)){point next={cur.x+dir[j].x, cur.y+dir[j].y};if(b[next.x][next.y]!=-1)continue;b[next.x][next.y]=b[cur.x][cur.y]+1;backQ.push(next);}}}}}//end whileprintf("0");}int main(void){int time;scanf("%d",&time);while(time-->0){scanf("%d%d%d%d%d\n",&l,&sx,&sy,&tx,&ty);dbfs();}return 0;}

poj 1077 ：Eight

?

?

?