双向宽度搜索

双向宽度搜索

  从正反两个方向进行宽度优先搜搜，可以大大减少搜索量，提高搜索速度。

  从初始状态和目标状态两个方向同时进行扩展，如果两颗解答树在某个节点第一次发生重合，即可终止此搜索过程，则该节点所连接的两条路径所拼成的路径就是最优解。

搜索方式

通常有两种搜索方式

1.两个方向交替扩展

2.选择节点个数较少的那个方向先扩展

方法2只需要略加修改控制结构，每次while循环时只扩展正反两个方向中节点数目较少的那一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。

很明显，方法2优于方法1

code

int head[2],tail[2],ans;
struct s{int x,y;} q[2][maxn];//队列
int v[2][maxn][maxn];//记录访问节点的数组
int dis[2][maxn][maxn];//寻找最短路径时记录数组 
int dx[10],dy[10];//扩展方向
int expand(int k)//对k队列进行扩展
{
    int h,t,d,x,y;

    x=q[k][head[k]].x;
    y=q[k][head[k]].y;
    d=dis[k][x][y];
    for(int i=0;i<8;++i)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(judge()&&!v[k][nx][ny])
        {
            v[k][nx][ny]=1;
            tail[k]++;
            q[k][tail[k]].x=nx;
            q[k][tail[k]].y=ny;
            dis[k][nx][ny]=d+1;
            if(v[k^1][nx][ny])
            {
                ans=dis[k][nx][ny]+dis[k^1][nx][ny];
                return 1;//找到了 
            }
        }
    }
    return 0;
}
void BFS()
{
    q[0][1]
    //这里特判一下是不是起点等于终点
    if(judge()){ans=0; return;}
    q[0][1].x=startx; q[0][1].y=starty;
    q[1][1].x=endx; q[1][1].y=endy;
    v[0][q[0][1].x][q[0][1].y]=1;
    v[1][q[1][1].x][q[1][1].y]=1;
    tail[0]=head[0]=tail[1]=head[1]=1;
    while(head[0]<=tail[0]&&head[1]<=tail[1])
    {
        if(tail[0]-head[0]<tail[1]-head[1])
        {
            expand(0);
            head[0]++;
        }
        else
        {
            expand(1);
            head[1]++;
        }
        //方法二，择优扩展 
    }
    return;
}

这种包装的暴力也就我这种不会正解蒟蒻用吧