搜索（二）——双向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<=300
int 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;
	else
		return 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 while

	printf("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